164 - String Computer

[Experimenter]

anyway, thanks.

[alu_mathics]

try to maintain

insert first , then replace and finally delete.

that is the order should be ICD

[Experimenter]

Ok, I'll try. I don't know whether it gonna help, but it is worth trying.
thanks indeed.

[Experimenter]

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

[alu_mathics]

try with this.
in:
himynameishihaho himynameishohiha
associationforcomputingmachinary associationforcomputingmathematics
urreallyaniceguy yesiam
wowthisisagoodprogram goodprogramthisisindeed
#
out:
Co12Ci14Ca16E
Ct26Ce28Cm29It31Ii32Cc33Cs34E
Du1Dr1Dr1De1Da1Dl1Dl1Ce2Cs3Dc5De5Dg5Ca5Cm6E
Cg1Co3Cd4Cp5Cr6Co7Cg8Cr9Im11It12Ch13Ci14Cs15Ci16Cs17Ci18Cn19Cd20Ce21Ce22Cd23E

[Experimenter]

ok.let me try this.thanks very much indeed.

[Experimenter]

alu_mathics, I got it accepted. mine did not work with that guy-string. thanks a great deal.I am really greateful.

[alu_mathics]

Good to see that you got AC.Hope you will get AC for problem 526.Best of luck

[Experimenter]

let me first look at that problem.

[Experimenter]

yep, it looks familiar.

[Abednego]

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

[Abednego]

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.

[little joey]

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]

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.

[Sedefcho]

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