You are not logged in. Please login at www.codechef.com to post your questions!

×

Swap the Boxes

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

slash_it's gravatar image

4★slash_it
11236
accept rate: 0%


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.

link

answered 30 Sep '12, 09:54

sjaljain's gravatar image

4★sjaljain
10333
accept rate: 100%

edited 30 Sep '12, 10:42

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★

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;
}
link
This answer is marked "community wiki".

answered 30 Sep '12, 10:50

shubhamvslavi's gravatar image

2★shubhamvslavi
1111
accept rate: 0%

edited 30 Sep '12, 11:03

vinayak%20garg's gravatar image

4★vinayak garg
3.7k113249

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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,917
×1,664
×1,490
×1,313
×1,284

question asked: 30 Sep '12, 09:39

question was seen: 1,753 times

last updated: 30 Sep '12, 11:03