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).
677B - Ваня и кухонный комбайн
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).
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|).
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[color] * cnt[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)).
There also exists solution with 2D segment tree:
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).
