×

# Swap the Boxes

 0 In this problem , i thought of a logic but it was O(N^2), which obviously resulted into TLE. Can anyone explain a faster way? asked 30 Sep '12, 09:39 4★slash_it 11●2●3●6 accept rate: 0%

 5 The problem could be reduced to sorting the array by some trivial position tricks. Then you can use the "inversion count" to find the swaps required. This can be done in O(nlogn) time as done here : http://www.geeksforgeeks.org/archives/3968 EDIT: Considering 1 of the test cases in the problem: 5 3 4 5 2 1 4 1 5 2 3 Let us give ranks to the numbers according to the second sequence rank(4)=1,rank(1)=2,rank(5)=3,rank(2)=4,rank(3)=5 Now in the original sequence, we replace the numbers by their ranks, 5 1 3 4 2 Now we need to essentially sort this new permutation. We can apply the inversion count method on this new sequence. answered 30 Sep '12, 09:54 4★sjaljain 103●3●3 accept rate: 100% I know the "inversion count method", the thing i was asking for that "trivial position tricks", could you explain a bit more about that. (30 Sep '12, 10:00) slash_it4★ @slash_it Edited my answer to make it more lucid (30 Sep '12, 10:43) sjaljain4★
 0 Well, I did the same and it was giving correct answer for all the testcases that were given and even I checked for upto 20 numbers and it was giving me the correct answer but my submission showed the incorrect answer and I dont know why it is showing incorrect.Here is my code: #include #include #include #include #define REP(i,n) for (int i=0;i0;i--) #define MAX 100002 #define mp(a,b) pair(a,b) using namespace std; typedef vector vi; int l[MAX]; long ans; void cross(int * a,int * b,int al,int bl,int *arr){ int i=0,j=0; while( i>1; int bl=len-al; int a[al]; int b[bl]; REP(i,al) a[i]=arr[i]; REP(i,bl) b[i]=arr[i+al]; inversions(a,al); inversions(b,bl); cross(a,b,al,bl,arr); } int main(){ map nums; int t,N,a; cin>>t; while((t--)>0){ cin>>N; nums.clear(); ans=0; REP(i,N){ cin>>a; nums.insert( mp(a,i));} REP(i,N){ cin>>a; l[i]=nums[a];} inversions(l,N); cout<
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×1,912
×1,657
×1,477
×1,302
×1,242

question asked: 30 Sep '12, 09:39

question was seen: 1,748 times

last updated: 30 Sep '12, 11:03