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 to N.

Subtask 1

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)

Subtask 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)


Comments

There are no comments at the moment.