codeforces-scrape

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

273.md (3168B)


      1 Source: https://codeforces.com/blog/entry/6625
      2 
      3 [272A - Dima and Friends](/contest/272/problem/A "Codeforces Round 167 (Div. 2)")
      4 
      5 We will bruteforce number of fingers that will be show Dima, then if total sum of fingers = 1 modulo (n+1), Dima will clean the room. So we should increase answer if the remaining part after division by (n+1) is not 1.
      6 
      7 [272B - Dima and Sequence](/contest/272/problem/B "Codeforces Round 167 (Div. 2)")  
      8 First of all — f(i) is number of ones in binary presentation of number. We will repair all numbers to functions of them. Now we have to find number of pairs of equal numbers. Lets Q[i] — number of numbers with i bits, the answer will be sum of values Q[i]*(Q[i]-1)/2 for all i.
      9 
     10 [273A - Dima and Staircase](/contest/273/problem/A "Codeforces Round 167 (Div. 1)")  
     11 Lets L will be the answer after last block, last block was (w1, h1), next block is (w2, h2). Next answer will be max(L+h1, A[w2]), where A — given array. At the beggining we can suppose that L = 0, w1 = 0, h1 = 0.
     12 
     13 [273B - Dima and Two Sequences](/contest/273/problem/B "Codeforces Round 167 (Div. 1)")  
     14 Not hard to understand that answer will be (number of numbers with first coordinate = 1)! * (number of numbers with first coordinate = 2)! * ... * (number of numbers with first coordinate = 10^9)!/(2^(number of such i = 1..n, that Ai=Bi)). The only problem was to divide number with non prime modulo, it can be easely done if we will count number of prime mulpiplies=2 in all factorials. Then we can simply substract number that we need and multiply answer for some power of 2.
     15 
     16 [273C - Dima and Horses](/contest/273/problem/C "Codeforces Round 167 (Div. 1)")  
     17 Not hard to understand that we have undirected graph. Lets color all vetexes in one color. Then we will find some vertex that is incorrect. We will change color of this vertex, and repeat our search, while it is possible. After every move number of bad edges will be decrease by 1 or 2, so our cycle will end in not more then M operations. So solutions always exists and we need to change some vertex not more then M times, so we will take queue of bad vertexes and simply make all operations of changes.
     18 
     19 [273D - Dima and Figure](/contest/273/problem/D "Codeforces Round 167 (Div. 1)")  
     20 Good picture is connected figure that saticfy next condition: most left coordinates in every row of figure vere we have some cells will be almost-ternary, we have the same situation with right side, but here we have another sign. So it is not hard to write dp[i][j1][j2][m1][m2] numbr of figures printed of field size i*m, where last row contain all cells from j1 to j2, the most left coordinate will be m1, the most right coordinate will be m2. But it is not enough. We have to rewrite it in way that m1 will mean — was there some rows j and j+1 that most left coordinate if row j is bigger then most left coordinate in j+1. So now it is not hard to write solution with coplexity O(n*m*m*m*m). But we should optimize transfer to O(1), is can be done using precalculations of sums on some rectangels.
     21 
     22 [273E - Dima and Game](/contest/273/problem/E "Codeforces Round 167 (Div. 1)")  
     23 will be added soon.