You are not logged in. Please login at www.codechef.com to post your questions!

×

KOL16J - Editorial

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[i]$ 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[i] != 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.

asked 30 Oct '17, 18:48

meooow's gravatar image

6★meooow ♦
6.7k717
accept rate: 48%

edited 14 Nov '17, 00:00

admin's gravatar image

0★admin ♦♦
19.5k348496535

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×15,026
×1,529
×743
×100
×6

question asked: 30 Oct '17, 18:48

question was seen: 504 times

last updated: 14 Nov '17, 00:00