codeforces-scrape

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

254.md (3345B)


      1 Source: https://codeforces.com/blog/entry/6085
      2 
      3 [254A - Cards with Numbers](/contest/254/problem/A "Codeforces Round 155 (Div. 2)")
      4 
      5 For each *x* from 1 to 5000 store a list *L*(*x*) of such indexes *i* that *a**i* = *x*. Then just check that all lists have even size and output the elements of each list in pairs.
      6 
      7 [254B - Jury Size](/contest/254/problem/B "Codeforces Round 155 (Div. 2)")
      8 
      9 One of the possible solutions is: for each Olympiad find the period of the preparation. This can be done by iterating the days back from the day of the Olympiad. For each day *d* of the preparation add *p**i* to the number of distinct jury members that have to work on problems on day *d*. Then the answer is maximum calculated sum over all days. Be careful with the year 2012.
     10 
     11 [254C - Anagram](/contest/254/problem/C "Codeforces Round 155 (Div. 2)")
     12 
     13 Lets denote the number of character *x* in *s* by *C**s*(*x*). Similarly *C**t*(*x*) is defined. Then the minimum number of changes required to get anagram of *t* from *s* is equal to ![](https://espresso.codeforces.com/a945f421fd5032c2f688e74ead02eee1ab2ac016.png). Now we need to obtain lexicographically minimum solution. Lets iterate through the positions in *s* from the left to the right. For a fixed position, look through all characters from 'a' to 'z' and for each character decide whether the optimal answer can contain this character in that position. If it can, put this character in that position and continue with the next position. To check if the given character is suitable quickly, we maintain the values *C**s*(*x*) and *C**t*(*x*) while iterating through positions.
     14 
     15 [254D - Rats](/contest/254/problem/D "Codeforces Round 155 (Div. 2)")
     16 
     17 Choose arbitrary rat (for say, the leftmost of the upmost). It's cell should be cleared. Make a BFS that never goes further than *d* from this cell (we will call such a BFS by d-BFS). It will visit approximately 2*d*2 cells in the worst case. So, we have to blow the first grenade in one of the visited cells. Lets check every visited cell as a candidate. Make a d-BFS from the candidate cell. Some cells with the rats will not be visited. That means that they should be cleared by the second grenade. Choose arbitrary cell with a rat that was not cleared by the first grenade. Make a d-BFS from it. All cells visited by this BFS are candidates to blow the second grenade. Lets check every such cell. Checking a cell again means making a d-BFS from it. If this BFS visits all cells that were not cleared by the first grenade, that we have found a solution. As every d-BFS visits at most 2*d*2, the overall number of steps is approximately 8*d*6.
     18 
     19 [254E - Dormitory](/contest/254/problem/E "Codeforces Round 155 (Div. 2)")
     20 
     21 The problem can be solved by dynamic programming: denote as *D*(*n*, *r*) the maximum rating that we can achieve in the first *n* days with the condition that we have *r* kilos of food remaining from the day *n* - 1. It is obvious that if we decide to feed *k* friends on some day, the better way is to feed *k* friends with the lowest *f**j* (of course we consider only friends that live with Vasya on that day). So we need to sort all available students in the order of increasing *f**j* and try to feed 0, 1, 2, \ldots first students in this order. We have 4002 states and 400 transitions from each state.