KOL16J - Editorial

acm16kol
cakewalk
editorial
kol16j
sorting

#1

PROBLEM LINK:

Practice
Contest

Editorialist: Soumik Sarkar

DIFFICULTY:

CAKEWALK

PREREQUISITES:

Arrays, Sorting

PROBLEM:

Given a list of N integers, determine if all numbers from 1 to N appear exactly once, and whether the list is sorted.

EXPLANATION:

A Tarantino movie must have two properties:

  1. Each chapter from 1 to N must be in the movie
  2. The chapters must not be in sorted order
    If both properties are satisfied, the output is “yes”, otherwise “no”.

For the first condition, this easiest approach is to check whether each number from 1 to N appear in the array.

for i in [1..N]
    flag = 0
    for j in [1..N]
        if i == A[j]
            flag = 1
            break current loop
    if flag == 0
        break current loop
if flag == 0
    definitely not a Tarantino movie
else
    proceed to check next condition

This algorithm has complexity \mathcal{O}(N^2). This works just fine with the given constraints, but alternately one can generate a frequency array which would be \mathcal{O}(N).

If the first check is passed, we know that the array only contains elements from 1 to N. Now to check whether the array is sorted, we can just check whether each A* is A[i-1] + 1 since this property holds true only when the array is sorted.

flag = 0
for i in [2..N]
    if A* != A[i-1] + 1
        flag = 1
        break current loop
if flag == 0
    cannot be a Tarantino movie
else
    both tests have been passed!

This approach is \mathcal{O}(N). Alternately, it is possible to sort a copy of A and if A is initially sorted the copy will be element-wise equal to A. This approach would be \mathcal{O}(N^2) or \mathcal{O}(N \log N) depending on the sorting procedure.

Overall complexity may be \mathcal{O}(N), \mathcal{O}(N^2) or \mathcal{O}(N \log N).

EDITORIALIST’S SOLUTION:

Editorialist’s solution can be found here.
Editorialist’s alternate solution can be found here.