A. New Rock Paper Scissors

The O(n²) solution is straight forward, although it can be solved in O(n) but it was not required. Even the O(n) seems easier to implement, but some cases might be missed. That's why the easiest problem of the contest turned out to be a little tricky. You see both kind of solutions in the scoreboard.

B. Bayan Health Bracelet

In this problems you had to find the first condition that is met. If carefully implemented one can get accepted with no hassle.

C. Grid History

The following two statements should hold for a valid grid:

• If the board is checkered, two cells have the same parity, if and only if they are colored the same.
• Let x be the value of a cell, and y be the value of the first cell with greater value than x. The length of the shortest path from x to y among the cells with value greater than or equal to x, is not greater than y - x.
• two greatest values of the board must differ by one.

Checking the first statement can be trivially done in O(nm). The second statement needs to be checked for every cell x on the grid, leading to an overall O(n²m²) time complexity, by running BFS nm times on the grid.

D. Towers

Here is a good explanation by W4yneb0t, that gives a good perception on the solution.

The visible surface is at least the sum of the highest towers in each column, plus the highest towers in each row, plus the top surfaces.

For each k, you want to minimize the number of columns and rows that contain a tower taller than k. Put the k highest towers in the smallest (by perimeter) rectangle that can contain them. This rectangle is either a square, or has sides that differ by 1, or has one side length equal to min(n, m). So, this is the lower bound for the area, and since we can actually do that for all k at the same time, it's also the upper bound.

To calculate the number of ways, let's say you have the number of ways to pack the tallest ab towers in an a × b rectangle, with a ≤ b, and want to calculate the number of ways to pack the (a + 1)b tallest in an (a + 1) × b rectangle. You can extend the rectangle in either 2 or 4 directions (4 when a = b < min(n, m), 2 otherwise), and arrange b towers along the side in 2^b - 1 ways.

E. Water Barrels

At time zero, the water reaches the first barrel. Now assume that we already know the first k barrels that water reached them. Take the lowest pipe going out of these barrels, say it's located at height h. So all of these k barrels will be watered to height h, unless they are already reached height h. So with these information, we can calculate the time that water reaches k + 1-th barrel. The whole algorithm runs in O(n² + m).

• As a exercise, try solving it in O(nlgn + m).

F. Merge

Let's have a bottom-up definition of a block. At first, each single black cell is called a block.

A set of blocks are called diagonally-shaped, if each two consecutive blocks touch each other at their corners. It can be easily seen that they will indeed look like a diagonal. Now consider a maximal diagonal-shaped set of blocks on the grid; We call their square-hull a block too; And we call those blocks, children of the new big block. According to this definition, if the answer isn't -1, the whole grid must be a block.

Here are some facts about the blocks:

• Black cells in each block can be merged into a single sub-square on the grid.
• Not every merge-able sub-square is called a block.
• Each block has a unique diagonal direction, which can be used to decompose it to it's children.
• Diagonal direction of each block is opposite of it's children's diagonal direction.

Now let's make a tree, using our blocks and the children definition we had. Notice that the whole grid is the root.

Let ans_u be the minimum sum of cells in block u, in the optimal merging plan for this block, so the answer to the problem is ans_root. Let v₁, v₂, ..., v_k be the children of vertex u. The last merge operation in this block, merges v₁, ..., v_p with v_p + 1... v_k, for some p.

• It can be proven that in optimal solution, one of these parts is merged completely before the other one starts merging. in fact, the bigger part should be merged first. Why?

At this point we have an O(n³) solution. For each block u, let's define dp_i, j as the minimum sum of cells in blocks v_i, ..., v_j, after merging them into one sub-square. So ans_u equals to dp_1, k. For each i and j, we should choose the last move, i.e. choose some p, (i ≤ p < j), and update dp_i, j from dp_i, p and dp_{p + 1, j}. The details of it are just some boring calculations.

To improve this solution to O(n²), we just need to see that in the optimal solution, dp[i][j] will be updated from p = i or p = j - 1.

..

Special thanks goes to havaliza, mR.ilchi, haas and mruxim for preparing the problems and the editorials. Hope you enjoyed the problems.