ACM14KP2 - Editorial

PROBLEM LINK:

Practice
Contest

Author: Jingbo Shang
Tester: Anudeep Nekkanti
Editorialist: Jingbo Shang

DIFFICULTY:

Easy-Medium

PREREQUISITES:

Merge Sort, Segment Tree/Fenwick Tree

PROBLEM:

Given an array A[1…N], you are allowed to swap exactly k times of adjacent numbers. Find out the minimum inversions that you can achieve.

EXPLANATION:

Basic Idea

It is worth noting that the number of swaps in bubble sort is equal to the number of inversions. And we only swap adjacent numbers in bubble sort. Therefore, we can greedily reduce the inversions in each swap. If k is less than the initial inversions I, the answer should be I – k.

To find out the number of inversion I, there are many classical solutions, such as Merge Sort, Segment Tree, and Fenwick Tree.

Corner Cases

As we have to apply exact k times, things go different when k is greater than I.

If k – I is even, we can repeatedly swap two numbers such that there will be no extra inversions after even number of swaps. Therefore, in this case, the answer should 0.

If k – I is odd, usually the answer should be 1. However, if there are duplicated numbers in the array, the answer could be 0, because we can swap these same numbers without any increases of the inversions.

AUTHOR’S AND TESTER’S SOLUTIONS:

Solutions will be available soon.

Author’s solution can be found here.
Tester’s solution can be found here.

Practice Link is broken…

Please Admin add these questions under practice link…

Yes, I also realized that when I posted it. It seems work now. Thanks for pointing out it!

1 Like

I can’t figure out what’s wrong with my


[1]. Can anyone look into it?


  [1]: http://www.codechef.com/viewplaintext/5479406

While counting inversions using BIT, we add numbers greater than current element ar[i]. So why does { query(n) - query(ar[i]-1) } give WA, but { query(n) - query(ar[i]) } is accepted?

//