Editorial for DMOPC '21 Contest 9 P1 - Board Numbers

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: Riolku

For this subtask, we are given one sum, call it . Let the two hidden numbers be and .

Then satisfying the following inequalities guarantees a valid pair:

Notice that for all , there is exactly one corresponding , and that no other is valid, so the answer is .

For this subtask, we are given two sums. The solution to this subtask is similar to the first.

Let our two sums be and . Consider choosing the middle hidden number . As long as we choose we are given exactly one valid configuration: , so this time, our answer is .

Observe that the value of the first hidden number completely determines the whole array. Also, a hidden number can never be larger than the sum of it and its pair, since they must both be positive. As such, we can brute force all up to possible numbers for the first hidden number, and check that the rest of the array is positive (since the rest of the array is forced).

There exists a binary search optimization to the subtask solution. Basically, observe that the possible values for the first element is a continuous interval. If a check fails, then we should look higher if we are at an odd index, and lower if we are at an even index. These results should become obvious after reading the below solution.

The binary search solution isn't that fun, so let's talk about a linear solution instead.

Let be the value of the first hidden number. Then the second hidden number is . The third is . The fourth is .

Every hidden number is a function of , either or . The first hidden number can be considered .

We can obtain these polynomials by walking through the array. If the polynomial is , then must be at most . If the polynomial is , then must be at least .

We can use a lo and hi variable to keep track of the lowest and highest possible , updating as we go, and then output at the end. Be careful to avoid integer overflow.