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

Subtask 1

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

Then satisfying the following inequalities guarantees a valid pair:

\displaystyle a, b \ge 1 \displaystyle a + b = S

Notice that for all 1 \le a < S, there is exactly one corresponding b, and that no other a is valid, so the answer is S - 1.

Subtask 2

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

Let our two sums be S and T. Consider choosing the middle hidden number b. As long as we choose 1 \le b < \min(S, T) we are given exactly one valid configuration: a = S - b, c = T - b, so this time, our answer is \min(S, T) - 1.

Subtask 3

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 10 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).

Subtask 4

There exists a binary search optimization to the subtask 3 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 x be the value of the first hidden number. Then the second hidden number is a_1 - x. The third is a_2 - (a_1 - x) = x - (a_1 - a_2). The fourth is (a_3 - a_2 + a_1) - x.

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

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

We can use a lo and hi variable to keep track of the lowest and highest possible x, updating as we go, and then output \max(0, hi - lo + 1) at the end. Be careful to avoid integer overflow.


There are no comments at the moment.