164 - String Computer
Moderator: Board moderators
-
- Learning poster
- Posts: 76
- Joined: Thu Mar 13, 2003 5:12 am
- Location: Russia
-
- Learning poster
- Posts: 55
- Joined: Sat Jan 24, 2004 9:30 pm
- Location: Chittagong
- Contact:
-
- Learning poster
- Posts: 76
- Joined: Thu Mar 13, 2003 5:12 am
- Location: Russia
-
- Learning poster
- Posts: 76
- Joined: Thu Mar 13, 2003 5:12 am
- Location: Russia
I tried to reoder this bit, if I understood correctly, but it did not help anyway:
Code: Select all
// backtracking
while(i>0 && j>0){
if((d[i][j-1] + 1) == d[i][j]){
sprintf(buf,"I%c%02d",t[j-1],j);
j--;
}
else if(d[i][j] == d[i-1][j-1] + 1 || d[i][j] == d[i-1][j-1])
{
i--, j--;
if(d[i][j] != d[i+1][j+1]) sprintf(buf,"C%c%02d",t[j],j+1);
else continue;
}
else {
sprintf(buf,"D%c%02d",s[i-1],j+1);
i--;
}
commands.push_back(string(buf));
}
it would be great if you replied this post. really.
-
- Learning poster
- Posts: 55
- Joined: Sat Jan 24, 2004 9:30 pm
- Location: Chittagong
- Contact:
try with this.
in:
himynameishihaho himynameishohiha
associationforcomputingmachinary associationforcomputingmathematics
urreallyaniceguy yesiam
wowthisisagoodprogram goodprogramthisisindeed
#
out:
Co12Ci14Ca16E
Ct26Ce28Cm29It31Ii32Cc33Cs34E
Du1Dr1Dr1De1Da1Dl1Dl1Ce2Cs3Dc5De5Dg5Ca5Cm6E
Cg1Co3Cd4Cp5Cr6Co7Cg8Cr9Im11It12Ch13Ci14Cs15Ci16Cs17Ci18Cn19Cd20Ce21Ce22Cd23E
in:
himynameishihaho himynameishohiha
associationforcomputingmachinary associationforcomputingmathematics
urreallyaniceguy yesiam
wowthisisagoodprogram goodprogramthisisindeed
#
out:
Co12Ci14Ca16E
Ct26Ce28Cm29It31Ii32Cc33Cs34E
Du1Dr1Dr1De1Da1Dl1Dl1Ce2Cs3Dc5De5Dg5Ca5Cm6E
Cg1Co3Cd4Cp5Cr6Co7Cg8Cr9Im11It12Ch13Ci14Cs15Ci16Cs17Ci18Cn19Cd20Ce21Ce22Cd23E
cuii e
-
- Learning poster
- Posts: 76
- Joined: Thu Mar 13, 2003 5:12 am
- Location: Russia
-
- Learning poster
- Posts: 76
- Joined: Thu Mar 13, 2003 5:12 am
- Location: Russia
-
- Learning poster
- Posts: 55
- Joined: Sat Jan 24, 2004 9:30 pm
- Location: Chittagong
- Contact:
-
- Learning poster
- Posts: 76
- Joined: Thu Mar 13, 2003 5:12 am
- Location: Russia
-
- Learning poster
- Posts: 76
- Joined: Thu Mar 13, 2003 5:12 am
- Location: Russia
-
- A great helper
- Posts: 281
- Joined: Tue Sep 10, 2002 5:14 am
- Location: Mountain View, CA, USA
- Contact:
Ok. I confirm that this problem is broken!
I did a standard Longest Common Subsequence dynamic programming, got about 20 WA on it trying to tweak various things. This code gets WA:
This code gets accepted:
I think this needs to be fixed.
I did a standard Longest Common Subsequence dynamic programming, got about 20 WA on it trying to tweak various things. This code gets WA:
Code: Select all
for( int i = m - 1; i >= 0; i-- ) for( int j = n - 1; j >= 0; j-- )
{
table[i][j] = 0x7FFFFFFF;
for( int dir = 0; dir < 3; dir++ )
{
int val = table[i + DI[dir]][j + DJ[dir]];
if( dir != 1 || s[i] != t[j] ) val++;
if( val < table[i][j] )
{
table[i][j] = val;
next[i][j] = dir;
}
}
}
Code: Select all
for( int i = m - 1; i >= 0; i-- ) for( int j = n - 1; j >= 0; j-- )
{
table[i][j] = 0x7FFFFFFF;
for( int dir = 2; dir >= 0; dir-- ) // <-- the ONLY changed line
{
int val = table[i + DI[dir]][j + DJ[dir]];
if( dir != 1 || s[i] != t[j] ) val++;
if( val < table[i][j] )
{
table[i][j] = val;
next[i][j] = dir;
}
}
}
If only I had as much free time as I did in college...
-
- Guru
- Posts: 1080
- Joined: Thu Dec 19, 2002 7:37 pm
What people are referring to as 'backtracking' here is not backing out of an exhaustive search, but as the second stage of the matrix method of string comparison (a DP solution). In the first stage you fill the matrix with the minimum number of changes needed, in the second stage you reed the matrix 'backward' to find a minimum path. If you have a copy of Cormen, you can find a picture of the matrix in fig. 15.6.Abednego wrote:I can't believe people are getting it accepted with backtracking. This is just wrongIt should be a DP problem.
And yes, the special corrector for this problem is broken, but nobody wrote a new one to date. Maybe you like to do it?
-
- A great helper
- Posts: 281
- Joined: Tue Sep 10, 2002 5:14 am
- Location: Mountain View, CA, USA
- Contact:
Oh, I see. So it means "tracing back".
As for a new special correction program, I have written one. little joey, could you send me your code (to abednego at gmail dot com) so that I have another solution to test the judge? I have asked Shahriar for the secret input, and I also have several versions of my solution which should all be correct. When I verify that they all work, I will ask that everything be rejudged using the new judge.
As for a new special correction program, I have written one. little joey, could you send me your code (to abednego at gmail dot com) so that I have another solution to test the judge? I have asked Shahriar for the secret input, and I also have several versions of my solution which should all be correct. When I verify that they all work, I will ask that everything be rejudged using the new judge.
If only I had as much free time as I did in college...
Could someone having an ACC program post several test cases?
Here are some test cases and the ouput which my program
produces for these test cases.
I have two empty lines in my test input.
For these two lines I print just the letter 'E' on a single line
in the output.
It would be also useful if someone posts the correct
answers for the test cases I give below.
And if possible post some other tests here too.
Here are some test cases and the ouput which my program
produces for these test cases.
I have two empty lines in my test input.
For these two lines I print just the letter 'E' on a single line
in the output.
It would be also useful if someone posts the correct
answers for the test cases I give below.
And if possible post some other tests here too.
Code: Select all
abcde bcgfe
a accdd
accdd a
abcxdefxghix abcyydefyyghiyy
ddppqq dapaqaaa
aab aab
abcdefghijklxyztpr pacdfeoomnrdffrr
#
Code: Select all
E
Da01Ig03Cf04E
Ic02Ic03Id04Id05E
Dc02Dc03Dd04Dd05E
Iy04Cy05Iy09Cy10Iy14Cy15E
Ca02Ca04Ia06Ia07Ca08E
E
E
Cp01Ca02De05Dg07Ce06Co07Co08Cm09Cn10Cr11Cd12Cf13Cf14Cr15E