Editorial for DMOPC '20 Contest 3 P1 - Present Checking
Submitting an official solution before solving the problem yourself is a bannable offence.
The problem is asking if the input array is a permutation of the integers from ~1~ to ~N~.
For the first subtask, we can naively check if each number from ~1~ to ~N~ is present in the array. Because such a check takes ~\mathcal O(N)~ time, this solution runs in ~\mathcal O(N^2)~.
Time Complexity: ~\mathcal O(N^2)~
There are many ways that we can check this efficiently:
We can use an array of size ~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~ and ~N~, so checking that they are all distinct is equivalent.
Time Complexity: ~\mathcal O(N)~ or ~\mathcal O(N \log N)~