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

Post by Experimenter »

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:

Post by alu_mathics »

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

Post by Experimenter »

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

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

Post by alu_mathics »

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

Post by Experimenter »

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

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

Post by alu_mathics »

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

Experimenter
Learning poster
Posts: 76
Joined: Thu Mar 13, 2003 5:12 am
Location: Russia

Post by Experimenter »

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

Post by Experimenter »

yep, it looks familiar. :D
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:

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

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

Post 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?

Abednego
A great helper
Posts: 281
Joined: Tue Sep 10, 2002 5:14 am
Location: Mountain View, CA, USA
Contact:

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

Post 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

Post Reply

Return to “Volume 1 (100-199)”