A. New Rock Paper Scissors
The O(n2) 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(n2m2) time complexity, by running BFS nm times on the grid.
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 2b - 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(n2 + m).
- As a exercise, try solving it in O(nlgn + m).
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 ansu be the minimum sum of cells in block u, in the optimal merging plan for this block, so the answer to the problem is ansroot. Let v1, v2, ..., vk be the children of vertex u. The last merge operation in this block, merges v1, ..., vp with vp + 1... vk, 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(n3) solution. For each block u, let's define dpi, j as the minimum sum of cells in blocks vi, ..., vj, after merging them into one sub-square. So ansu equals to dp1, k. For each i and j, we should choose the last move, i.e. choose some p, (i ≤ p < j), and update dpi, j from dpi, p and dpp + 1, j. The details of it are just some boring calculations.
To improve this solution to O(n2), we just need to see that in the optimal solution, dp[i][j] will be updated from p = i or p = j - 1.