Swap the Boxes

general
, , , ,
1

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?

2

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 : Inversion count in Array using Merge Sort - GeeksforGeeks

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.

5 Likes
3

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 <iostream>
#include <vector>
#include <map>
#include <algorithm>
#define REP(i,n) for (int i=0;i<n ;i++)
#define FOR(i,a,b) for(int i=a;i<b;i++)
#define BACK(i,n) for(int i=n;i>0;i--)
#define MAX 100002
#define mp(a,b) pair<int,int>(a,b)
using namespace std;

typedef vector<int> 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<al && j<bl ){
	  if(a[i]<=b[j]){
	      arr[i+j]=a[i];
		  i++;}
	  else{
	      arr[i+j]=b[j];
		  j++;
		  ans+=(al-i);}}
	  while(i<al){
		arr[i+j]=a[i];
		i++;}
	  while(j<bl){
		arr[i+j]=b[j];
		j++;}}

void inversions(int * arr,int len){
  if(len==1) return;
  int al=len>>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<int,int> 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<<ans<<endl;}
	return 0;
}
4

I know the “inversion count method”, the thing i was asking for that “trivial position tricks”, could you explain a bit more about that.

5

@slash_it Edited my answer to make it more lucid