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$ ~arr~ 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]$ ~arr[u_i]~ to $1$ ~1~.

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

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

Comments

There are no comments at the moment.