331 - Mapping the Swaps

[Minilek]

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]

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]

The first number is the number of elements.

[SilentStrike]

asdfasdfasdfasdfaf

Thanks .

I am sure that makes it a LOT easier.

[newton]

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]

Just read the problem statement again. You will soon understand.

[Obaida]

But What is my mistake...

Code: Select all

removed

[Jan]

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]

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

thanks for help

[abid_iut]

Can anyone explain what the problem wants??
pls help

[zobayer]

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

[jddantes]

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