Editorial for DMOPC '20 Contest 3 P1 - Present Checking

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

The problem is asking if the input array is a permutation of the integers from $1$ ~1~ to $N$ ~N~.

Subtask 1

For the first subtask, we can naively check if each number from $1$ ~1~ to $N$ ~N~ is present in the array. Because such a check takes $\mathcal O(N)$ ~\mathcal O(N)~ time, this solution runs in $\mathcal O(N^2)$ ~\mathcal O(N^2)~.

Time Complexity: $\mathcal O(N^2)$ ~\mathcal O(N^2)~

Subtask 2

There are many ways that we can check this efficiently:

We can use an array of size $N$ ~N~ to track the number of times each element appears, and then ensure that they each appear once exactly.
We can use a set to track the elements we've seen before.
We can sort the array, and ensure that adjacent elements are not equal. This is sufficient because each element in the input is between $1$ ~1~ and $N$ ~N~, so checking that they are all distinct is equivalent.

Time Complexity: $\mathcal O(N)$ ~\mathcal O(N)~ or $\mathcal O(N \log N)$ ~\mathcal O(N \log N)~

Comments

There are no comments at the moment.