Page 4 of 9

Posted: Sat Dec 25, 2004 7:21 am
by Experimenter
anyway, thanks.

Posted: Sun Dec 26, 2004 9:33 am
by alu_mathics
try to maintain

insert first , then replace and finally delete.

that is the order should be ICD

Posted: Tue Dec 28, 2004 1:58 pm
by Experimenter
Ok, I'll try. I don't know whether it gonna help, but it is worth trying.
thanks indeed.

Posted: Tue Dec 28, 2004 2:04 pm
by 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));
	}

Posted: Tue Dec 28, 2004 7:27 pm
by alu_mathics
try with this.
in:
himynameishihaho himynameishohiha
associationforcomputingmachinary associationforcomputingmathematics
urreallyaniceguy yesiam
wowthisisagoodprogram goodprogramthisisindeed
#
out:
Co12Ci14Ca16E
Ct26Ce28Cm29It31Ii32Cc33Cs34E
Du1Dr1Dr1De1Da1Dl1Dl1Ce2Cs3Dc5De5Dg5Ca5Cm6E
Cg1Co3Cd4Cp5Cr6Co7Cg8Cr9Im11It12Ch13Ci14Cs15Ci16Cs17Ci18Cn19Cd20Ce21Ce22Cd23E

Posted: Sat Jan 01, 2005 3:51 pm
by Experimenter
ok.let me try this.thanks very much indeed.

Posted: Sat Jan 01, 2005 5:59 pm
by Experimenter
alu_mathics, I got it accepted. :D mine did not work with that guy-string. thanks a great deal.I am really greateful.

Posted: Sun Jan 02, 2005 1:23 pm
by alu_mathics
Good to see that you got AC.Hope you will get AC for problem 526.Best of luck :wink:

Posted: Sun Jan 02, 2005 7:41 pm
by Experimenter
let me first look at that problem. :)

Posted: Sun Jan 02, 2005 7:43 pm
by Experimenter
yep, it looks familiar. :D

Posted: Mon May 02, 2005 4:54 am
by 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...

Posted: Mon May 02, 2005 6:46 am
by 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.

Posted: Mon May 02, 2005 8:31 am
by little joey
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?

Posted: Mon May 02, 2005 9:22 pm
by 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.

Posted: Tue May 24, 2005 3:40 pm
by 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