codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

41.md (1968B)


      1 Source: https://codeforces.com/blog/entry/1620
      2 
      3 I wrote this post to help my friend , Iman Movahhedi , complete [this one](//www.codeforces.com/blog/entry/1492).
      4 
      5 Round #40 was my first contest here in Codeforces and I feel I fell in love with CF just after that.  
      6 
      7 ---
      8 
      9 **A-Translation:** ([C# code](http://pastebin.com/YmxXqAAS))
     10 
     11 Many languages have built-in reverse() function for strings. we can reverse one of the strings and check if it's equal to the other one , or we can check it manually. I prefer the second.
     12 
     13 ---
     14 
     15 **B-Martian Dollar:**([C# code](http://pastebin.com/EP3KPzUf))
     16 
     17 Since number of days is very small (2 × 103) we can just iterate over all possibilities of buy-day and sell-day. This will take θ (*n*2) time which is OK.
     18 
     19 ---
     20 
     21 **C-Email Address:** ([C++ code](http://pastebin.com/mfbkckEU))
     22 
     23 The first letter of the input string can not be part of an "at" or a "dot" so we start from the second character. Greedily put "." wherever you reached "dot" and put "@" the first time you reached "at". This will take θ(*n*) time , where *n* is the length of input.
     24 
     25 ---
     26 
     27 **D-Pawn:**
     28 
     29 For each cell of the table store *k* + 1 values. Where *i*th value is the maximum number of peas the pawn can take while he is at that cell and this number mod *k* + 1 is *i*.
     30 
     31 This makes a *O*(*n*2 × *m* × *k*) dynamic programming which fits perfectly in the time.
     32 
     33 ---
     34 
     35 **E-3-cycles:** ([C++ code](http://pastebin.com/Z90p9BAm))
     36 
     37 The road map with most edges is a complete bipartite graph with equal number of vertices on each side. (Prove it by yourself :D ). We can make such a graph by putting the first ![](https://espresso.codeforces.com/bd56e4088ce870395869fbe86fa16543528abd86.png) vertices on one side and the other ![](https://espresso.codeforces.com/ede3a3124231fc0d4b89bc003e97033c6ea0a17c.png) on the other side.For sure , number of edges is ![](https://espresso.codeforces.com/6e1e68e75001260e10fce2a4bf6604d7200fc728.png).