Geek asks and answers

Swap boxes with minimal moves

This is a question of a programming contest (which has ended). I tried to solve this problem, but could not find a healthy method for this.

The question is this:

IIIT Allahabad celebrates its annual Technocultural Fiesta Effervescence MM12 from October 1 to 5. The chef agreed to provide candy for this holiday season. The chef prepared N boxes of sweets, numbered from 1 to N (each number occurs exactly once). The chef is very concerned about the arrangement of the boxes. He wants the boxes to be organized in a certain order, but, unfortunately, the Chef is busy. He asked you to rearrange the boxes for him. Given the current order of the boxes, you should reorder the boxes in that order. However, there is a limitation. You can exchange only two adjacent fields to achieve the desired order. Conclusion, a minimum number of such adjacent swaps is required.

Enter

The first line of input contains a single integer T, the number of test cases. Each test case contains 3 lines, the first line contains a single integer N, the number of boxes. The next 2 lines contain N numbers each, the first line is the specified order of boxes, and the second line is the desired order.

Output

For each test case, print a single integer "K", the minimum number of contiguous swaps. Limitations:

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

Conclusion:

2
3
6
3

I almost did not know about this issue. Can someone explain the logic of the question?

+5
source share
5 answers

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

, , , O (n log n), .

^, ( , ), O (n log m), m . - , , , .

, , . ? .

, . :

  • Fenwick Tree ( ) m (m = n ).

    Fenwick, , . , , Fenwick Tree, ( , , ).

  • n :

    • , , .
    • , , . . , . (*)
    • + 1 Fenwick .

  • , (*).

^ , , . , , , , .

+6

(1,2,..., N). ( )

.

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]];

perm .

+4

, , .

A pair (i,j) , i < j array[i] > array[j]. , () 1. O(n log n) , . C.

EDIT , :

i - array. array[i] array[i+1] 1. , . , array , (i, i+1) , array[i] > array[i+1] (.. (i,j) ) 1, array[i] array[i+1]. , .

+2

:

, , .

:

3 4 5 2 1  
4 1 5 2 3

, 4 1, 1 2, 5 3 ..  ,

.

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

( , )

5 1 3 4 2

.

, .. .

, , , .

,

5 1 3 4 2

5 4 , 5 .

1 0 , 1 .

3 1 , 3 .

4 1 , , 1 .

2 0 , 2 .

: (4 + 0 + 1 + 1 + 0) = 6.

, http://www.geeksforgeeks.org/archives/3968.

. , , , .

0

, 4/4 , , ( ), . .

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.

Thus, this algorithm looks as if it would give you a minimum for any given input. The worst case as a whole looks like a U-turn, which will require the replacement of N * (N-1) / 2 (see Example 2).

-1
source

More articles:


All Articles