## 164 - String Computer

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

Moderator: Board moderators

Experimenter
Learning poster
Posts: 76
Joined: Thu Mar 13, 2003 5:12 am
Location: Russia
anyway, thanks.
it would be great if you replied this post. really.

alu_mathics
Learning poster
Posts: 55
Joined: Sat Jan 24, 2004 9:30 pm
Location: Chittagong
Contact:
try to maintain

insert first , then replace and finally delete.

that is the order should be ICD
cuii e

Experimenter
Learning poster
Posts: 76
Joined: Thu Mar 13, 2003 5:12 am
Location: Russia
Ok, I'll try. I don't know whether it gonna help, but it is worth trying.
thanks indeed.
it would be great if you replied this post. really.

Experimenter
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.

alu_mathics
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
cuii e

Experimenter
Learning poster
Posts: 76
Joined: Thu Mar 13, 2003 5:12 am
Location: Russia
ok.let me try this.thanks very much indeed.
it would be great if you replied this post. really.

Experimenter
Learning poster
Posts: 76
Joined: Thu Mar 13, 2003 5:12 am
Location: Russia
alu_mathics, I got it accepted. mine did not work with that guy-string. thanks a great deal.I am really greateful.
it would be great if you replied this post. really.

alu_mathics
Learning poster
Posts: 55
Joined: Sat Jan 24, 2004 9:30 pm
Location: Chittagong
Contact:
Good to see that you got AC.Hope you will get AC for problem 526.Best of luck
cuii e

Experimenter
Learning poster
Posts: 76
Joined: Thu Mar 13, 2003 5:12 am
Location: Russia
let me first look at that problem.
it would be great if you replied this post. really.

Experimenter
Learning poster
Posts: 76
Joined: Thu Mar 13, 2003 5:12 am
Location: Russia
yep, it looks familiar.
it would be great if you replied this post. really.

Abednego
A great helper
Posts: 281
Joined: Tue Sep 10, 2002 5:14 am
Location: Mountain View, CA, USA
Contact:
I can't believe people are getting it accepted with backtracking. This is just wrong :-) It should be a DP problem.

That said, I got lots and lots of WA on it. And I still don't know what's wrong...
If only I had as much free time as I did in college...

Abednego
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:

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;
}
}
}
``````
This code gets accepted:

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;
}
}
}
``````
I think this needs to be fixed.
If only I had as much free time as I did in college...

little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm
Abednego wrote:I can't believe people are getting it accepted with backtracking. This is just wrong It should be a DP problem.
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.

And yes, the special corrector for this problem is broken, but nobody wrote a new one to date. Maybe you like to do it?

Abednego
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.
If only I had as much free time as I did in college...

Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria
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.

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``````