## 331 - Mapping the Swaps

Moderator: Board moderators

Minilek
Learning poster
Posts: 90
Joined: Tue Jul 27, 2004 9:34 am
Location: Cambridge, MA
Contact:

### 331 speed

I wanted to ask if there is a better way to approach 331. I did this problem by counting the number of inversions to tell me the minimum number of swaps, then from there I generated all possible swap sequences of that size by brute force. When #inversions==10, the only case is a list of length 5 completely backwards, so I returned a precalculated answer in that case as to not time out. It seems like there should be a better way; does anyone know one ?

Thanks.

SilentStrike
New poster
Posts: 22
Joined: Fri Jan 04, 2002 2:00 am

### 331 - Mapping the Swaps

Consider the number of swap maps for 3 9 1 5.
It seems to me that there are two, like shown. But the sample output says there is only 1.

Code: Select all

``````3 9 1 5
3 1 9 5
1 3 9 5
1 3 5 9
3 1 5 9
1 3 5 9
``````

UFP2161
A great helper
Posts: 277
Joined: Mon Jul 21, 2003 7:49 pm
Contact:
The first number is the number of elements.

SilentStrike
New poster
Posts: 22
Joined: Fri Jan 04, 2002 2:00 am
asdfasdfasdfasdfaf

Thanks .

I am sure that makes it a LOT easier.

newton
Experienced poster
Posts: 162
Joined: Thu Jul 13, 2006 7:07 am
Contact:
i am confused about the swaping procedure!
for input 3 3 2 1:
my algorithm works:

Code: Select all

``````    2 3 1=1
2 1 3=1
1 2 3=1

so total swap=(1+1+1=3)!
``````
but why the OJ's output is 2?
may anybody describe it?

newton..................... simply the best

rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan
Just read the problem statement again. You will soon understand.

Obaida
A great helper
Posts: 380
Joined: Wed Jan 16, 2008 6:51 am
But What is my mistake...

Code: Select all

``removed``
Last edited by Obaida on Tue Dec 23, 2008 9:54 am, edited 1 time in total.
try_try_try_try_&&&_try@try.com
This may be the address of success.

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Contact:
Try the cases.

Input:

Code: Select all

``````5 1 2 4 5 3
5 1 5 4 2 3
5 2 1 4 3 5
5 2 1 5 3 4
5 4 5 2 1 3
0``````
Output:

Code: Select all

``````There are 1 swap maps for input data set 1.
There are 5 swap maps for input data set 2.
There are 2 swap maps for input data set 3.
There are 3 swap maps for input data set 4.
There are 21 swap maps for input data set 5.``````
Hope these help.

rajib_cse_sust
New poster
Posts: 2
Joined: Mon May 05, 2008 11:05 am

### Re: 331 confusion

any one can explain it detail i am getting many wrong answer
in this problem

thanks for help

abid_iut
Learning poster
Posts: 82
Joined: Wed Jul 16, 2008 7:34 am

### Re: 331 help

Can anyone explain what the problem wants??
pls help i love to wait... wait for better... and better will come...
http://akanoi.webs.com/

zobayer
Experienced poster
Posts: 110
Joined: Tue May 06, 2008 2:18 pm
Contact:

### Re: 331 confusion

This problem wants you to calculate how many different minimum length swap map exists, not just to calculate how many swaps needed.

Example:
3 9 1 5
swap pos 1 and 2 : 1 9 5
swap pos 2 and 3 : 1 5 9
so the mapping is 1 2
no other mapping is possible.
so ans is 1

and the problem statement is also quite clear
You should not always say what you know, but you should always know what you say.

jddantes
Learning poster
Posts: 73
Joined: Sat Mar 08, 2014 8:55 am

### Re: 331 - Mapping the Swaps

Why is mine RE? Could it be due to the recursion stack being too deep? I've tried it with 5 and even 6 as the array size.

Code: Select all

``````#include <bits/stdc++.h>

using namespace std;

#define INF 1<<26

int N;
vector<int> input;
vector<int> orig;

vector<int> swap_map;

void printOrig(){
for(int i = 0; i<orig.size(); i++){
printf("%d ", orig[i]);
}
printf("\n");
}
void simulate(){
printf("Simulating\n");
for(int i = 0; i<swap_map.size(); i++){
int key = swap_map[i];
swap(orig[key], orig[key+1]);
printOrig();
swap(orig[key], orig[key+1]);
}
}
void print(){
printf("Map is: ");
for(int i = 0; i<swap_map.size(); i++){
printf("%d ", swap_map[i]);
}
printf("\n");
}

bool isSorted(){
bool ret = true;
for(int i = 1; i<N; i++){
if(input[i] >= input[i-1]){
continue;
}
return false;
}
return ret;
}

int shortest;
int cnt;

int f(int pred){
if(isSorted()){
// print();
// simulate();
return 0;
}

int best = INF;
for(int i = 0; i<N-1; i++){
if(i != pred){
if(input[i] < input[i+1]) continue;
swap(input[i], input[i+1]);
swap_map.push_back(i);
int ret = 1 + f(i);
swap_map.pop_back();
best = min(best, ret);
swap(input[i], input[i+1]);
}
}
return best;
}

int check(int pred, int len){
if(isSorted()){
if(len == shortest)
cnt++;
return 0;
}

int best = INF;
for(int i = 0; i<N-1; i++){
if(i != pred){
if(input[i] < input[i+1]) continue;
swap(input[i], input[i+1]);
int ret = 1 + check(i, len+1);
best = min(best, ret);
swap(input[i], input[i+1]);
}
}
return best;
}

int main(){
int caseNum = 0;

while(scanf("%d", &N)!=EOF){
if(!N) break;
caseNum++;
input.resize(N);
for(int i = 0; i<N; i++){
scanf("%d", &input[i]);
}
orig = input;
cnt = 0;
shortest = f(-1);
// printf("shortest is %d\n", shortest);
check(-1,0);
if(shortest == 0) cnt = 0;
printf("There are %d swap maps for input data set %d.\n", cnt, caseNum);
}

return 0;
}
``````