Editorial for DMOPC '20 Contest 4 P1 - Missing Numbers
Submitting an official solution before solving the problem yourself is a bannable offence.
Note that the sum of all numbers from to is , which we will denote as . To avoid overcounting, we will only count pairs with .
We can loop over all pairs of numbers and check if .
To speed the previous solution up, note that there is at most one valid for each . Thus, we can loop all and check if there is a such that and .
For full marks, note that the average of all valid pairs must be constant since their sum is constant. We can compute the required average of , find the pair with the required average and minimal (intuitively closest to the average), and imagine "expanding" the pair to repeatedly until either or . The number of pairs can thus be computed with a simple subtraction.
Can you solve the problem if Jennifer erases numbers in general instead of just ?