# PROBLEM LINK

# 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(N**^{2}) - 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.