Page 1 of 1
11212 - Editing a Book
Posted: Sun Jun 03, 2007 9:31 pm
by 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.
Posted: Mon Jun 04, 2007 4:37 am
by 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.
???
Posted: Mon Jun 04, 2007 3:20 pm
by 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.
Pruning strategies
Posted: Mon Jun 04, 2007 6:08 pm
by jah
Hi,
[EDIT] (Solved. Rujia that was very helpful)
Thank you for your help.
Re: ???
Posted: Mon Jun 04, 2007 6:49 pm
by rujialiu
rezaeeEE wrote: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
Your program output 4, but the correct output is 3
Re: Pruning strategies
Posted: Mon Jun 04, 2007 6:50 pm
by rujialiu
jah wrote: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.
?
Posted: Wed Jun 06, 2007 1:49 pm
by 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?
Posted: Wed Jun 06, 2007 2:40 pm
by 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