Editorial for DMOPC '20 Contest 4 P1 - Missing 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: 4fecta

Note that the sum of all numbers from $1$ ~1~ to $N$ ~N~ is $\frac{N(N+1)}{2}$ ~\frac{N(N+1)}{2}~, which we will denote as $M$ ~M~. To avoid overcounting, we will only count pairs $(i, j)$ ~(i, j)~ with $i < j$ ~i < j~.

Subtask 1

We can loop over all $\mathcal{O}(N^2)$ ~\mathcal{O}(N^2)~ pairs of numbers $(i, j)$ ~(i, j)~ and check if $M - i - j = S$ ~M - i - j = S~.

Time complexity: $\mathcal{O}(TN^2)$ ~\mathcal{O}(TN^2)~

Subtask 2

To speed the previous solution up, note that there is at most one valid $j$ ~j~ for each $i$ ~i~. Thus, we can loop all $i$ ~i~ and check if there is a $j$ ~j~ such that $j \in (i, N]$ ~j \in (i, N]~ and $M - i - j = S$ ~M - i - j = S~.

Time complexity: $\mathcal{O}(TN)$ ~\mathcal{O}(TN)~

Subtask 3

For full marks, note that the average of all valid pairs $(i, j)$ ~(i, j)~ must be constant since their sum is constant. We can compute the required average of $(i, j)$ ~(i, j)~, find the pair with the required average and minimal $j-i$ ~j-i~ (intuitively closest to the average), and imagine "expanding" the pair to $(i-1, j+1)$ ~(i-1, j+1)~ repeatedly until either $i = 1$ ~i = 1~ or $j = N$ ~j = N~. The number of pairs can thus be computed with a simple subtraction.

Time complexity: $\mathcal{O}(T)$ ~\mathcal{O}(T)~

Bonus

Can you solve the problem if Jennifer erases $K$ ~K~ numbers in general instead of just $2$ ~2~?

Comments

0

YassineAllala commented on March 28, 2021, 11:28 a.m.

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?

4

dxke02 commented on March 28, 2021, 12:26 p.m. ← edited →

What if $N \le X$ ~N \le X~, this means that the pair $1, N$ ~1, N~ will not work. You must consider cases where $N \le X$ ~N \le X~

0

humbertoyusta commented on March 15, 2021, 10:23 p.m. ← edited →

What is the expected complexity of the bonus?, I only know how to solve it in $\mathcal{O}(N^4)$ ~\mathcal{O}(N^4)~.

0

4fecta commented on March 16, 2021, 1:37 a.m.

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

1
piddddgy commented on March 15, 2021, 2:44 p.m.
wait can u go over the "simple subtraction" pls

someone who bsearched

7

humbertoyusta commented on March 15, 2021, 3:29 p.m. ← edited →

If the average is $X$ ~X~, all pairs must be of the form $(X-K, X+K)$ ~(X-K, X+K)~, for some $K$ ~K~, such that $X-K$ ~X-K~ and $X+K$ ~X+K~ are integers between $1$ ~1~ and $N$ ~N~, so there will be $\min(N-\lceil K \rceil+1, \lfloor K \rfloor) - [K\text{ is an integer}]$ (for not taking into account equal numbers) pairs.