5

This is a question from a programming competition ( which has ended ). I was struggling to solve this problem but couldn't find a healthy method to do so.

The question is as follows:

IIIT Allahabad is celebrating its annual Techno-Cultural Fiesta Effervescence MM12 from 1st to 5th October. The Chef has agreed to supply candies for this festive season. The chef has prepared N boxes of candies, numbered 1 to N (Each number occurring exactly once ). The Chef is very particular about the arrangement of boxes. He wants boxes to be arranged in a particular order, but unfortunately Chef is busy. He has asked you to rearrange the boxes for him. Given the current order of boxes, you have to rearrange the boxes in the specified order. However there is a restriction.You can only swap two adjacent boxes to achieve the required order. Output, the minimum number of such adjacent swaps required.

Input

First line of input contains a single integer T, number of test cases. Each test case contains 3 lines, first line contains a single integer N, number of boxes. Next 2 lines contains N numbers each, first row is the given order of boxes while second row is the required order.

Output

For each test case, output a single integer 'K', minimum number of adjacent swaps required. Constraints:

1<=T<=10
1<=N<=10^5

Example

Input:

4

3
1 2 3
3 1 2

3
1 2 3
3 2 1

5
3 4 5 2 1  
4 1 5 2 3  

4
1 2 3 4
2 3 4 1

Output:

2
3
6
3

I was almost clueless about this question. Can somebody please explain the logic behind the question!!

Akashdeep Saluja
  • 2,959
  • 8
  • 30
  • 60
  • This problem can be reduce to find the number of steps in a bubble sort algorithm. – nhahtdh Sep 30 '12 at 04:42
  • It is counting inversion problem, which can be done in O(n log n) with modified merge sort: http://stackoverflow.com/questions/337664/counting-inversions-in-an-array or you can use Fenwick Tree (since you are counting the number of (i, j) pairs where i < j and A[i] > A[j] and luckily the range of the numbers can be confined to 10^5). – nhahtdh Sep 30 '12 at 04:57
  • Have you checked the link above, it has the solution to the problem in O(n log n)? – nhahtdh Sep 30 '12 at 05:05
  • @nhahtdh How can a reversal (e.g. 1...5 to 5...1) be done in anything less than n*(n-1)/2 swaps? – Matt Phillips Sep 30 '12 at 05:06
  • @MattPhillips: The point is not swapping the numbers. The point is counting the number of swaps, which may not involve swapping. – nhahtdh Sep 30 '12 at 05:07
  • @nhahtdh I understand that, and that in principle counting could be less than actually doing. You could make a big lookup table. But we're presumably not doing that, and so the claim that counting can be done in O(nlogn) is currently just an empty assertion. The fact that *sorting* is O(nlogn) is not enough, this is a mapping from one unordered array to another. – Matt Phillips Sep 30 '12 at 05:18
  • @MattPhillips: I'm saying that it can be done in O(n log n), never say anything about the lower bound. And since the numbers in the arrays are unique, we can derive the mapping to do inversion counting. – nhahtdh Sep 30 '12 at 05:36
  • 6 upvotes, 2 favourites, 5 people have posted answers, many of which have been upvoted and one of which has been accepted... yet apparently "It's difficult to tell what is being asked here" and so this question has been closed. Another victory for the brave bureaucrats of SO! – j_random_hacker Oct 01 '12 at 09:04
  • 1
    @j_random_hacker: It should be closed as duplicate, though. I found a duplicated question later and it describes the same method as my post does (Binary Indexed Tree/Fenwick Tree). – nhahtdh Oct 03 '12 at 07:55
  • @nhahtdh: Fair enough. What was that other question? – j_random_hacker Oct 03 '12 at 16:30
  • 1
    @j_random_hacker: This is a good one http://stackoverflow.com/questions/11497502/counting-inversions-using-bit and another one not as good but also gives hint http://stackoverflow.com/questions/4214102/measuring-how-out-of-order-an-array-is – nhahtdh Oct 03 '12 at 20:35
  • @nhahtdh: Hmm. Those are definitely questions *that have the same answer* as this one, but I would not say they are the same question because some logic is required to figure out that this question can be transformed into them. – j_random_hacker Oct 03 '12 at 20:48
  • @j_random_hacker I think the question doesn't shown any research effort into the problem: OP's thoughts, opinions, the results of those "struggles" mentioned in the question. – Vicky Chijwani Oct 27 '12 at 17:02

5 Answers5

6

The problem is quite a "classic" competitive programming problem, which is counting inversions in an array. Inversion is defined as a pair (i, j) where i < j and A[i] > A[j].

The most general version, which an array of arbitrary numbers are given and you are asked to count the number of inversions, has an O(n log n) solution by modifying merge sort algorithm.

A more restricted version^, in which there is a reasonable upperbound on the maximum value in the array (note that this is NOT the length of the array), can be solved in O(n log m), where m is the maximum value in the array. The main point here is the amount of code you have to write is much less than merge sort approach.

The problem in the question is about counting the number of swaps to sort the array to certain order, which can be reconstructed as counting the number of swaps to sort the array in ascending order, and it boils down to count the number of inversions. Why number of inversions? Because you can only resolve at most one inversion per swapping 2 adjacent elements.

You need to create an array that describes the current position of the boxes with respect to the final settings. Then the algorithm can start:

  1. Construct a Fenwick Tree (Binary Indexed Tree) with length m (m = n for the problem in the question).

    We will use the Fenwick Tree to help us in counting the number of preceding elements in the array that is larger than the current element. We will keep the frequency of the numbers that we have encountered so far and use Fenwick Tree range sum query to get the number of elements less than current element (and derive the number of elements larger than current element).

  2. Loop through n elements of the array:

    • Use range sum query to count how many numbers that is smaller than the current number has been recorded.
    • Use the info above to find out how many numbers that is larger than the current number. Add this to the inversion count. Take note to not include the element being considered. (*)
    • Adjust + 1 to the Fenwick Tree at the value of the element.

  3. The inversion count that is accumulated in the (*) step.

^ The question clearly says the elements are unique, so the algorithm above will work. I'm just not sure whether uniqueness is necessary condition, or the algorithm can be modified to accommodate the case where there are repeating elements.

Community
  • 1
  • 1
nhahtdh
  • 55,989
  • 15
  • 126
  • 162
  • Also: you don't explain *why* counting inversions solves the given problem. – j_random_hacker Sep 30 '12 at 05:48
  • It looks like a very comprehensive answer otherwise, but I think that "why" question is crucial :) – j_random_hacker Sep 30 '12 at 05:52
  • Sample code here: http://pastebin.com/3fBa7PT7 . The code is not proper, so I don't include it in my answer. Unless you are willing to refactor it, please don't edit to put it in my answer - since the answer has enough steps to reproduce the code. – nhahtdh Sep 30 '12 at 05:58
  • @j_random_hacker: Please check my answer now (I hope I didn't miss out anything). – nhahtdh Sep 30 '12 at 06:06
  • i just want to discuss that can't we get any benefit from the numbers being unique and strictly from 1 to N i.e. cant we do it more faster than O(NlogN)? – Akashdeep Saluja Sep 30 '12 at 06:12
  • +1. I've deleted my first comment, which was mistaken -- you are counting the right number of things. It would be a perfect answer if you could also explain why an adjacent-swap that decreases the number of inversions must always exist in a non-sorted array :) – j_random_hacker Sep 30 '12 at 06:13
  • @AkashdeepSaluja: I'm also wondering if there is exact O(N) algorithm for this. There is a *linear* **approximation** algorithm. – nhahtdh Sep 30 '12 at 06:17
  • @j_random_hacker: Probably leave as exercise for reader? :P Just pick out a segment that has only has inverted pair at 2 ends and we will see the contradiction. – nhahtdh Sep 30 '12 at 06:22
  • Added the "why" as a comment on my answer below. – Andrew Tomazos Sep 30 '12 at 07:37
4

Reduce the source list to a permutation of (1,2,...,N). (By applying the inverse of the target to the source)

Then count the number of inversions.

ie

vector<int> source = ...;
vector<int> target = ...;

vector<int> inv(N)

for (int i = 0; i < N; i++)
   inv[target[i]] = i;

vector<int> perm(N);

for (int i = 0; i < N; i++)
    perm[i] = source[inv[i]];

Then count inversions in perm using the standard algorithm.

Andrew Tomazos
  • 66,139
  • 40
  • 186
  • 319
  • Why does counting the inversions work? – j_random_hacker Sep 30 '12 at 05:54
  • 2
    Assuming distinct elements (which is a given in a permutation) then any adjacent swap either increases the inversions by one or reduces it by one. Therefore the fastest path is to always pick a swap that reduces the inversions by one. Such a swap must always be available, simply walk the list and swap the first adjacent pair you find that is inverted. If there is no such pair the inversions = 0 and you are done. – Andrew Tomazos Sep 30 '12 at 07:33
  • Good explanation, +1. Belongs in the main post! – j_random_hacker Oct 01 '12 at 09:01
2

Assuming that the desired order is the sorted order of numbers, the problem reduces to finding the number of inversions in an array.

A pair (i,j) is said to be an inversion if i < j and array[i] > array[j]. This is because each (optimal) swap between adjacent elements reduces the number of inversions by exactly 1. You can find the number of inversions in O(n log n) by a divide and conquer algorithm that is very similar to merge sort. Here's a nice explanation with C code.

EDIT Proof that number of inversions is equal to the optimal number of swaps:

Let i be any position in an array. Swapping array[i] and array[i+1] reduces the number of inversions by at most 1. Thus the number of swaps required is at least equal to the number of inversions. On the other hand if array is not sorted, we can always find a pair (i, i+1) such that array[i] > array[i+1] (i.e. (i,j) is an inversion), and reduce the number of inversions by 1, by swapping array[i] with array[i+1]. Thus the number of inversions is equal to the minimum number of swaps.

krjampani
  • 2,902
  • 20
  • 23
  • "Formally speaking, two elements a[i] and a[j] form an inversion if a[i] > a[j] and i < j" This definition is fine for a sort, when the target is number in ascending order. But how does this generalize to OP's case, where the target ordering is not ascending? – Matt Phillips Sep 30 '12 at 05:13
  • 1
    Apply the inverse of the target permutation to the source, see my answer. – Andrew Tomazos Sep 30 '12 at 05:15
  • This is a good start. I can see why an adjacent-swap can reduce the number of inversions by at most 1 (because the only pair of positions (i, j) whose "inversion-ness" can be changed by an adjacent-swap (i', i'+1) is the pair (i=i', j=i'+1), but how to prove that such a move always exists? – j_random_hacker Sep 30 '12 at 05:36
  • @j_random_hacker Whenever we swap two adjacent numbers A[i] and A[i+1], it must be the case that A[i] > A[i+1], otherwise the swap is not optimal and it actually increases the number of inversions. On the other hand, if the array is not yet sorted we can always find two adjacent numbers A[i] and A[i+1], such that A[i] > A[i+1]. – krjampani Sep 30 '12 at 12:39
  • I believe you :) But I would ideally like to see a proof spelled out for that 2nd part -- namely, that "A is not sorted" implies "There exists i such that (i, i+1) is an inversion". "A is not sorted" clearly implies "There exists i, j such that (i, j) is an inversion", but we need to show it's still true for j = i+1. – j_random_hacker Sep 30 '12 at 12:57
  • 1
    How about this ? IF A is not sorted there exists an index i such that A[i] > A[i+1]. Otherwise if A[i] <= A[i+1], for every i, A is already sorted. But then (i, i+1) is an inversion. – krjampani Sep 30 '12 at 13:11
  • 1
    Sorted -> ForAll i, A[i] < A[i+1] -> Not Exists i A[i] > A[i+1]. Not Sorted -> Not ForAll i, A[i] < A[i+1] -> Exists i A[i] > A[i+1]. – Andrew Tomazos Oct 01 '12 at 00:40
  • @AndrewTomazos-Fathomling, krjampani: Thanks, it's clear now. – j_random_hacker Oct 01 '12 at 08:55
0

The problem can be considered as an inversion count problem as follows:

As the priorities of numbers are given i.e. in the order in which we are supposed to sort.

Consider the priorities and replace it with the numbers

e.g:

3 4 5 2 1  
4 1 5 2 3

In the above test case we can observe that 4 is assigned priority 1, 1 is assigned priority 2 , 5 is assigned priority 3 and so on. So why not replace the number in original list with these priorities

i.e. transforming the original list

(3 4 5 2 1) to (5 1 3 4 2)

(just replacing the number with their respective priorities as discussed above)

Now our list has transformed to 

5 1 3 4 2

and we are just supposed to sort it in ascending order.

Now we are allowed only adjacent swaps i.e. somewhat related to bubble sort.

the count of swaps needed for bubble sort which is equal to the sum of count of elements on the right side of each element which is smaller than the current element.

for e.g: In list

5 1 3 4 2

5 has 4 elements smaller than 5 on its right side.

1 has 0 elements smaller than 1 on its right side.

3 has 1 elements smaller than 3 on its right side.

4 has 1 elements smaller than 1 on its right side.

2 has 0 elements smaller than 2 on the right side.

Now the final answer is (4+0+1+1+0)=6.

Now the above procedure can be computed using inversion count which is discussed here http://www.geeksforgeeks.org/archives/3968 .

NOTE: The answers I obtained were of great use, just describing the whole thing in detail. Thank You

Akashdeep Saluja
  • 2,959
  • 8
  • 30
  • 60
-1

I can't prove this mathematically, but in 4/4 of the test cases you get the minimum swaps by getting the boxes in the right position starting with the leftmost (could do this with rightmost too) and moving right. I.e.

3 4 5 2 1 //First get the 4 in the right place
4 3 5 2 1 //Done.  Now get the 1 in the right place
4 3 5 1 2
4 3 1 5 2
4 1 3 5 2 //Done.  Now the 5
4 1 5 3 2 //Done.  Now the 2
4 1 5 2 3 //All done.

So this algorithm looks like it will give you the minimum for any given input. The worst case in general looks like a reversal, which will require N*(N-1)/2 swaps (see ex. 2).

Matt Phillips
  • 9,465
  • 8
  • 44
  • 75
  • This will be O(N^2) worst case, which is not what the OP needs. – nhahtdh Sep 30 '12 at 05:04
  • yeah, but O(N^2) exceeds the time limit. – Akashdeep Saluja Sep 30 '12 at 05:04
  • @nhahtdh It doesn't matter what OP 'needs', the solution is dictated by the structure of the problem. If you can do a reversal (see above and my comment to the top post) in O(n log(n)) let's see it, and perhaps hold off on the downvotes until that's actually delivered. – Matt Phillips Sep 30 '12 at 05:09
  • @AkashdeepSaluja How is the time limit determined? Did the contest organizers tell you this or something? – Matt Phillips Sep 30 '12 at 05:20
  • i forgot to enter it but it was 2 sec . – Akashdeep Saluja Sep 30 '12 at 05:29
  • 1
    @MattPhillips: You can look at the modified merge sort algorithm, or my algorithm and try to simulate it. In my algorithm, the reversal can be done with O(n log m) (with m = n) with Fenwick Tree (rsq and adjust always log m). Competition problem usually are 1-3 seconds (but we can assume 1 second for most cases) - and by looking at the constraint on input, it might be possible to guess the expectation of the judge, which is an algorithm faster than O(N ^ 2). – nhahtdh Sep 30 '12 at 08:54