← All solutions

Solved by 72 teams.

First solved after 69 minutes.

Shortest judge solution: 1366 bytes.

The solution consists of two parts. First, we need to understand what the condition of “each unit square has the two evaluations coincide” actually means. It turns out that it means that there are some values r_i for 1 ≤ i ≤ n and c_j for 1 ≤ j ≤ m such that h(i, j) = r_i + c_j. This is not hard to prove (or guess).

Now, let’s construct a bipartite graph where we have an edge between x and y if the point (x, y) is one of the points for which we have the height provided. A connected component in this graph determines a set of rows and columns; and we need to assign r_i and c_j values to all those rows and columns in a way that matches the points in this component. First, let’s assign in any way that makes the point heights match up; we’ll worry about making sure that all heights are positive and minimizing the height in (t_x, t_y) later.

How to deal with this graph? Notice that we can assign one value arbitrarily – if we increase all the c_j and decrease all the r_i by the same value, the resulting heights will not change, and so the first assignment can be arbitrary. Once we assign one c_j value, all other values will be forced, so we can continue assigning them by BFS or DFS. If we arrive at a contradiction, we can immediately answer impossible. If not, we store the values we found.

Now, the requirement of all heights being non-negative is equivalent to us being able to choose non-negative r_is and c_js. One direction is obvious. The other direction follows from the adjustment above – we can move the minimum r_i to zero, and if now the minimum c_j is negative, then the height at (i, j) is negative. So, we’ll be seeking a solution with non-negative r_i and c_j that minimizes the height at (t_x, t_y).

Now, to minimize the height at (t_x, t_y), we have to consider several cases.

• If (t_x, t_y) is an element of some component, we’ve already assigned a height to it, and we cannot change it. Done.
• If row t_x is an element of some component, and the column t_y is an element of a different component, we want to minimize r_tx in the first component, and c_ty in the second. This means bringing the minimum r_i in the first component to zero, and the minimum c_j in the second component to zero.
• If either row t_x or column t_y is not the element of any component, we can just set the relevant r_tx or c_ty to zero.