11212 - Editing a Book

[rezaeeEE]

i get wa and in dont know why.
can give me some test case.

Code: Select all

#include <iostream>

using namespace std;
int n;
int mn;
int b[150000][10];

void cut(int a,int avval,int akhar,int ja)
{
	for(int i=1;i<ja;i++)
		b[a+1][i]=b[a][i];
	int pointer=ja;
	for(int i=avval;i<=akhar;i++)
		b[a+1][pointer++]=b[a][i];
		
	for(int i=ja;i<avval;i++)
		b[a+1][pointer++]=b[a][i];

	for(int i=akhar+1;i<=n;i++)
		b[a+1][pointer++]=b[a][i];
}

void tabe(int a,int i,int shomar)
{
	if(i==n)
	{
		if(mn>shomar)
			mn=shomar;
		return;
	}
	if(b[a][i]==i)
	{
		tabe(a,i+1,shomar);
		return ;
	}
	int pointer=1;
	while(b[a][pointer]!=i)
		pointer++;
	for(int j=0;j<=n-pointer;j++)
		{
			cut(a,pointer,pointer+j,i);
			tabe(a+1,i+1,shomar+1);
		}
	
	return ;
}

int main()
{
	int u=1;
	while(cin>>n,n)
	{
		for(int i=0;i<1500;i++)
			for(int j=0;j<=9;j++)
				b[i][j]=0;
		mn=10;
		for(int i=1;i<=n;i++)
			cin>>b[0][i];
		tabe(0,1,0);
		cout<<"Case "<<u++<<": "<<mn<<endl;
	}
	return 0;
}

thank u.

[rujialiu]

I've tested your code with a typical test case and it seems to me that your algorithm is incorrect. Please read the problem description once more to make sure that you're considering every possible operation. Also, you may think some operations are 'obviously' useless but actually they ARE useful.

[rezaeeEE]

thank u very much.
but i can't understand .

i think my backtracking tests all the good way to get a result.

can u give me some test case that result of my algorithm is incorrect?

thak u.

[jah]

Hi,

[EDIT] (Solved. Rujia that was very helpful)

Thank you for your help.

[rujialiu]

thank u very much.
but i can't understand .

i think my backtracking tests all the good way to get a result.

can u give me some test case that result of my algorithm is incorrect?

thak u.

for the input

Code: Select all

5
5 4 3 2 1

Your program output 4, but the correct output is 3

[rujialiu]

Hi,

(I TLE'd)
What kind of prunning strategies have you used?

The two simple tricks I used are to "merge" all the consecutive elements in a permutation so that we can't cut subsequences of a sequence of consecutive elements. I also tried to cut subsequences and move them at a higher position than the actual position of the sequence to be moved ( if the sequence goes from i -> j I move it to a k > j just because it's the same as moving j -> k to i). I also used a rank macro for the permutations in order to look in (nearly) constant time if I have already visited that state, etc.

Thank you for your help.

You may want to try bidirectional search or something like A* that uses heuristic.

[rezaeeEE]

thank u very much for your tricky test case

but i didn't understand. if we can only cut and paste such as what is available in windows the answer migth be 4. can help me a little more?

[rio]

Heres the 3 step solution:

Code: Select all

step1: 5 4 (3 2) 1  -->  (3 2) 5 4 1
step2: 3 (2 5) 4 1  -->  3 4 1 (2 5)
step3: (3 4) 1 2 5  -->  1 2 (3 4) 5

----
Rio