331 - Mapping the Swaps

All about problems in Volume 3. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

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

331 speed

Post by Minilek » Wed Aug 18, 2004 3:35 pm

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

Post by SilentStrike » Mon Dec 27, 2004 2:31 am

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 

User avatar
UFP2161
A great helper
Posts: 277
Joined: Mon Jul 21, 2003 7:49 pm
Contact:

Post by UFP2161 » Mon Dec 27, 2004 4:43 am

The first number is the number of elements.

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

Post by SilentStrike » Mon Dec 27, 2004 9:10 am

asdfasdfasdfasdfaf

Thanks :).

I am sure that makes it a LOT easier.

User avatar
newton
Experienced poster
Posts: 162
Joined: Thu Jul 13, 2006 7:07 am
Location: Campus Area. Dhaka.Bangladesh
Contact:

Post by newton » Sat Feb 17, 2007 3:17 pm

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

User avatar
rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan

Post by rio » Sat Feb 17, 2007 3:41 pm

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

Obaida
A great helper
Posts: 380
Joined: Wed Jan 16, 2008 6:51 am
Location: (BUBT) Dhaka,Bagladesh.

Post by Obaida » Sat Mar 29, 2008 8:28 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
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Sat Mar 29, 2008 1:35 pm

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
Location: sylhet,Bangladesh

Re: 331 confusion

Post by rajib_cse_sust » Thu May 08, 2008 10:02 am

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

Post by abid_iut » Mon Dec 22, 2008 9:55 am

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
Location: CSE-DU, Bangladesh
Contact:

Re: 331 confusion

Post by zobayer » Mon Jul 13, 2009 9:31 pm

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

Post by jddantes » Thu Jul 23, 2015 8:14 am

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

Post Reply

Return to “Volume 3 (300-399)”