Codeforces Round #355 (Div. 2) Editorial

Revision en9, by Wild_Hamster, 2016-06-01 22:49:36

677A - Vanya and Fence

For each friend we can check, if his height is more than h. If it is, then his width is 2, else 1.

Complexity O(n).

Code

677B - Vanya and Food Processor

The solution, that does same thing, as in the problem statement will fail with TL, because if the height of each piece of potato will be 109 and smashing speed will be 1, then for each piece we will do 109 operations.

With each new piece of potato ai we will smash the potato till a[i] MOD k, so we will waste a[i] / k seconds on it. If we can not put this piece of potato after that, we will waste 1 more second to smash everything, that inside, else just put this piece. We will get an answer same as we could get with actions from the statement.

Complexity O(n).

Code

677C - Vanya and Label

We can transform our word in binary notation, we can do it easily, because 64 = 26. Move through the bits of this number: if bit is equal to 0, then we can have 3 different optinos of this bit in our pair of words: 0&1, 1&0, 0&0, else we can have only one option: 1&1. So the result will be 3nullbits, where nullbits — is amount of zero bits.

Complexity O(|s|).

Code

677D - Vanya and Treasure

We can make dynamic programming dp[col][row], where dp[col][row] is minimal time, that we have waste to open the chest in the cell (col, row). For the cells of color 1: dp[x][y] = x + y. For each next color color we can look over all cells of color color - 1 and all cells of color color, then for each cell of color color with coordinates (x1, y1) and for each cell with color color - 1 and coordinates (x2, y2) dp[x1][y1] = dp[x2][y2] + abs(x1 - x2) + abs(y1 - y2).

But complexity of this solution is O(n2·m2), what is not enough.

We can do such improvement: let cnt[x] be the amount of cells of color x, then when cnt[colorcnt[color - 1] ≥ n·m, we can do bfs from cells of color color - 1 to cells of color color.

Then we will have complexity O(n·m·sqrt(n·m)).

Proof

Code

There also exists solution with 2D segment tree:

Code

677E - Vanya and Balloons

For each cell (x, y) take the maximum possible cross with center in this cell, that doesn't contains zeros. To do it fast, we can make arrays of partial sums for all possible 8 directions, in which each cell will contain the number of non-zero balloons in each direction. For example, if we want to know, how many non-zero balloons are right to cell (x, y), we can create an array p[x][y], where p[x][y] = p[x][y - 1] + 1 if a[x][y]! = 0 else p[x][y] = 0

So now we can for each cell (x, y) we can find the maximum size of cross with the centre in this cell, that will not contain zeros.

We can compare product for crosses with centers in the cells (x, y) and radius r using logarythms. For example, if we need to compare 2 crosses with values x1·x2·...·xn and y1·y2·...·ym, we can compare log(x1·x2·...·xn) and log(y1·y2·...·yn), what will be equivalent to comparing log(x1) + log(x2) + ... + log(xn) and log(y1) + log(y2) + ... + log(ym).

We can also use partial sum arrays to find value log(x1) + log(x2) + ... + log(xn) for each cross, so we can find the product of the values in each cross for O(1) time.

Complexity O(n2).

Code
Tags editorial, 355

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en9 English Wild_Hamster 2016-06-01 22:49:36 111
ru6 Russian Wild_Hamster 2016-06-01 22:47:18 133
en8 English Wild_Hamster 2016-06-01 22:22:10 196
ru5 Russian Wild_Hamster 2016-06-01 22:20:00 194
ru4 Russian Wild_Hamster 2016-06-01 22:16:49 4042 Мелкая правка: 'oiler/spoiler
en7 English Wild_Hamster 2016-06-01 22:14:18 4026
ru3 Russian Wild_Hamster 2016-06-01 22:07:19 11918
en6 English Wild_Hamster 2016-06-01 22:03:29 11650
en5 English Wild_Hamster 2016-06-01 21:50:43 95
ru2 Russian Wild_Hamster 2016-06-01 21:48:47 11 Мелкая правка: 'высоты$a_i%k$, тогда ' -
en4 English Wild_Hamster 2016-06-01 21:47:02 4 Tiny change: 'till $a[i] MOD k$, so we ' -> 'till $a[i]$ $MOD$ $k$, so we '
en3 English Wild_Hamster 2016-06-01 21:44:36 10
ru1 Russian Wild_Hamster 2016-06-01 21:43:50 3370 Первая редакция перевода на Русский
en2 English Wild_Hamster 2016-06-01 21:40:41 97
en1 English Wild_Hamster 2016-06-01 21:39:09 3178 Initial revision (published)