LEPERMUT - Editorial

editorial
, , ,
1

PROBLEM LINK

Practice
Contest

DIFFICULTY

CALEWALK

PREREQUISITES

Ad Hoc

PROBLEM

You are given a permutation in which you have to find the number of inversions and the number of local inversions.

Print YES, if they are equal.

Print NO, otherwise.

QUICK EXPLANATION

This ad-hoc problem can be solved by

  • Iterating on i and j for calculating the number of inversions in order O(N2)
  • Iterating on i for calculating the number of local inversions in order O(N) 
for i = 1 to N
    for j = i+1 to N
        if A[i] > A[j]
            inversions = inversions + 1

for i = 2 to N
    if A[i-1] > A[i]
        local_inv = local_inv + 1

if inversions = local_inv
    print YES
else
    print NO

To make this editorial more interesting, let us see if we can do any better.

EXPLANATION

Suppose we could only make local inversions.

In other words,

Given an ordered sequence { 1, 2, …, N } we want to try and convert it to the given permutation. But, the only operation we can perform is making local inversions. Also, the local inverisons should not overlap. If the local inversions overlap, they will introduce non-local inversions.

If only local inversions were introduced, then the given permutation should convert back to an ordered sequence upon inverting all the local inversions. And we know there can only be O(N) of them.

The following procedure inverts all the local inversions as required.

i = 2
while i < N
    if A[i-1] > A[i]
        swap( A[i-1], A[i] )
        i++
    i++

Now, if the permutation had no non-local inversions, then it should be ordered already! The following snippet of code returns what shoud be printed for a test case once the above snippet has been run.

for i = 2 to N
    if A[i-1] > A[i]
        return NO
return YES

This creates a very simple O(N) algorithm to test whether there are any non local inversions or not.

SETTERS SOLUTION

Can be found here.

TESTERS SOLUTION

Can be found here.
Refer to the code for an even more elegant simplification from the Editorial above. :slight_smile:

2 Likes
2

There exists another O(N) solution completely different from the O(N) solution in the editorial and tester’s (well mine) solution. Let’s count ‘local’ inversions of sizes 2 and 3:

cnt = 0
for i = 1 to N-2
   cnt += A[i] > A[i+2]
for i=1 to N-3
   cnt += A[i] > A[i+3]

It is a good exercise to prove that the permutation is good if and only if cnt = 0. Post your proofs as a comments. :slight_smile:

UPD P.S. When designing test data I was stuck for a while by this solution thinking “How could I fail it?” Bur then I’ve realized that it is correct :slight_smile:

2 Likes
3

Another very simple O(N) solution is the following: for each i compute

  • vmax(i) = the maximum value among A(1), …, A(i)
  • vmin(i) = the minimum value among A(i), …, A(N)

(obviously we can compute all these values in O(N) time)

Then, if there exists some i (2 <= i <= N-1) such that vmax(i-1) > vmin(i+1) then the answer is NO (that’s because that condition implies that the permutation also has other inversions besides the local inversions).

6 Likes
4

The Tester’s solution to this question is clearly wrong. Please check the solution.

5

If it does not perform the check as required in the problem statement it does not mean that it is wrong :wink:

As you see it gets AC
http://www.codechef.com/viewsolution/1566884

This is a good exercise to prove that it is indeed correct. Hint: the proof should continue the considerations written in the section EXPLANATION of the editorial :wink:

6

I read the EXPLANATION section of the editorial. My point is that if that program prints answers which are wrong according to the question, how does it get AC?
For example, for n = 2 and A[] = { 3, 1 }, it outputs NO (should be YES).

7

A[] = {3, 1} is incorrect test case. A[] should be a permutation of integers {1, 2, …, n}

8

Oh I forgot about that! Now I see why it works :slight_smile: