## Editorial for DMOPC '20 Contest 4 P1 - Missing Numbers

**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:

Note that the sum of all numbers from to is , which we will denote as . To avoid overcounting, we will only count pairs with .

#### Subtask 1

We can loop over all pairs of numbers and check if .

**Time complexity:**

#### Subtask 2

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 .

**Time complexity:**

#### Subtask 3

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.

**Time complexity:**

#### Bonus

Can you solve the problem if Jennifer erases numbers in general instead of just ?

## Comments

I've tried to use a formula for the problem and it doesn't seem to work? Why?

Here's my algorithm: let x be the difference between the real sum (N*(N+1)/2 and S, the number of possible pairs possible to form the sum x can be found by the integer (x-1)/2, I've tried it for big values and it's about the same and working, why not here?

What if , this means that the pair will not work. You must consider cases where

What is the expected complexity of the bonus?, I only know how to solve it in .

To be honest, we're not quite sure either! The bonus section was added to inspire some further thinking for those who have already solved the original problem. If you've found an interesting or fast algorithm that solves it, please let us know here! :D

wait can u go over the "simple subtraction" pls

If the average is , all pairs must be of the form , for some , such that and are integers between and , so there will be (for not taking into account equal numbers) pairs.