Editorial for TLE '17 Contest 2 P2 - Unlucky 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: ChaSiu

The solution uses a prefix sum array. Create an int array $arr$ $a r r$ of size $1\,000\,001$ $1 000 001$ , and ensure that all values in that array are set to 0. Then, for each unlucky number $u_i$ $u_{i}$ , set $arr[u_i]$ $a r r [u_{i}]$ to $1$ $1$ .

Now you may create a prefix sum array with the same size as $arr$ $a r r$ ( $1\,000\,001$ $1 000 001$ ). In the PSA, $psa[0] = 0$ $p s a [0] = 0$ , and for all $1 \le i \le 1\,000\,000$ $1 \leq i \leq 1 000 000$ , $psa[i] = psa[i-1] + arr[i]$ $p s a [i] = p s a [i - 1] + a r r [i]$ . The PSA shows you that for an apartment with top floor $j$ $j$ , there will be $psa[j]$ $p s a [j]$ floors removed.

Time Complexity: $\mathcal{O}(K+N)$ $O (K + N)$

Comments

There are no comments at the moment.