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

#### Subtask 1

For the first subtask, we can naively check if each number from to is present in the array. Because such a check takes time, this solution runs in .

Time Complexity:

#### Subtask 2

There are many ways that we can check this efficiently:

• We can use an array of size 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 and , so checking that they are all distinct is equivalent.

Time Complexity: or

## Comments

There are no comments at the moment.