164 - String Computer

[Sedefcho]

Could someone verify the I/O below
( it comes from my WA program ).

Or post some more test I/O ?

Input

Code: Select all

abcde bcgfe
axd accdd
accdd a
abcxdefxghix abcyydefyyghiyy
ddppqq dapaqaaa
aab aab

abcdefghijklxyztpr pacdfeoomnrdffrr

himynameishihaho himynameishohiha 
associationforcomputingmachinary associationforcomputingmathematics 
urreallyaniceguy yesiam 
wowthisisagoodprogram goodprogramthisisindeed
aaa abaaaaaa

abccdddz accxyyy
#

Output

Code: Select all

E
Da1Ig3Cf4E
Ic2Ic3Cd4E
Dc2Dc2Dd2Dd2E
Iy4Cy5Iy9Cy10Iy14Cy15E
Ca2Ca4Ia6Ia7Ca8E
E
E
Cp1Ca2De5Dg6Ce6Co7Co8Cm9Cn10Cr11Cd12Cf13Cf14Cr15E
E
Co12Ci14Ca16E
Ct26Ce28Cm29It31Ii32Cc33Cs34E
Du1Dr1Dr1De1Da1Dl1Dl1Ce2Cs3Dc5De5Dg5Ca5Cm6E
Cg1Co3Cd4Cp5Cr6Co7Cg8Cr9Im11It12Ch13Ci14Cs15Ci16Cs17Ci18Cn19Cd20Ce21Ce22Cd23E
Ia1Ib2Ia3Ia4Ia5E
E
Db2Cx4Cy5Cy6Cy7E

A modified version of my program prints each number in
two decimal digits ( i.e. 03 instead of 3 ). It also gets WA.
See output 2 below.

Output 2

Code: Select all

E
Da01Ig03Cf04E
Ic02Ic03Cd04E
Dc02Dc02Dd02Dd02E
Iy04Cy05Iy09Cy10Iy14Cy15E
Ca02Ca04Ia06Ia07Ca08E
E
E
Cp01Ca02De05Dg06Ce06Co07Co08Cm09Cn10Cr11Cd12Cf13Cf14Cr15E
E
Co12Ci14Ca16E
Ct26Ce28Cm29It31Ii32Cc33Cs34E
Du01Dr01Dr01De01Da01Dl01Dl01Ce02Cs03Dc05De05Dg05Ca05Cm06E
Cg01Co03Cd04Cp05Cr06Co07Cg08Cr09Im11It12Ch13Ci14Cs15Ci16Cs17Ci18Cn19Cd20Ce21Ce22
Cd23E
Ia01Ib02Ia03Ia04Ia05E
E
Db02Cx04Cy05Cy06Cy07E

[Abednego]

Here are my outputs that are accepted by the old judge program. The empty lines are invalid input. Each line must contain a space.

Code: Select all

Da01Ig03Cf04E
Ic02Ic03Id04Id05E
Dc02Dc02Dd02Dd02E
Iy04Cy05Iy09Cy10Iy14Cy15E
Ca02Ca04Ia06Ia07Ca08E
E
Ip01Db03De05Ce06Co07Co08Cm09Cn10Cr11Cd12Cf13Cf14Cr15Dp16E

[Sedefcho]

Hi Abednego!

First, thanks for the answer.

One question - what do you mean by "the old judge" ?

I got it ACC a few minutes ago. The WAs I was getting were
due to a very very subtle BUG in my program.

I managed to discover this BUG by solving
problem 526 first. I've found a sample I/O from
little joey for 526 / tomorrow - sorrow - no sorrow /
which has revealed my BUG.

I don't think any of the sample inputs given here and
in the other thread
http://online-judge.uva.es/board/viewtopic.php?t=7152
were able to reveal that BUG of mine.

Thanks once again for answering me.

I will be happy to help others which still have WA on 164 by
giving them some sample I/O or in some other way.

Regards !

[Abednego]

I sent a new judge program for this problem to the judge maintainers. I guess they are busy now, but it should be rejudged eventually.

[Experimenter]

probably, this is the one I got AC. sorry, but I am really 2 busy 2 get the output. just do it, ok? I mean, this is probably more harm than good, but this is the only way I can help. sorry.

Code: Select all

it is gone. sorry.

[Sedefcho]

Experimenter, I got ACC on problem 164 soon after
my previous post. Thank you anyway.

If that is an ACC code better don't post it here, it will become a spoiler

Thanks once again.

[Experimenter]

I cannot find this "delete"-button 2 delete it.

[Sedefcho]

Just use the edit button

[Ndiyaa ndako]

I used the algorithm that appears in the Programming Challenges book, and now my code is rejected. Is the algorithm wrong or the judge solution has to be checked again?

[Abednego]

Post your code here, and I will look at it. I hope that it's not a mistake in my special judge.

[Ndiyaa ndako]

The code that they used for their algorithm is:

Code: Select all

int string_compare(char *s, char *t)
{
	int i,j,k;		/* counters */
	int opt[3];		/* cost of the three options */

	for (i=0; i<MAXLEN; i++) {
		row_init(i);
		column_init(i);
	}

	for (i=1; i<strlen(s); i++)
		for (j=1; j<strlen(t); j++) {
			opt[MATCH] = m[i-1][j-1].cost + match(s[i],t[j]);
			opt[INSERT] = m[i][j-1].cost + indel(t[j]);
			opt[DELETE] = m[i-1][j].cost + indel(s[i]);

			m[i][j].cost = opt[MATCH];
			m[i][j].parent = MATCH;
			for (k=INSERT; k<=DELETE; k++)
				if (opt[k] < m[i][j].cost) {
					m[i][j].cost = opt[k];
					m[i][j].parent = k;
				}
		}

	goal_cell(s,t,&i,&j);
	return( m[i][j].cost );
}

[Abednego]

I'm assuming that
INSERT = 0,
MATCH = 1 and
DELETE = 2.

First of all, if m=strlen(s) and n=strlen(t), then this algorithm takes m*n*n time because you have strlen(t) inside the loop.

Also, I don't know what these functions do:
match()
indel()
row_init()
column_init()
goal_cell()

Generally, it looks correct, but the goal_cell() function is tricky. My guess is that the mistake is in there.

[Ndiyaa ndako]

You can find the full source code at:

http://www.cs.sunysb.edu/~skiena/392/pr ... distance.h
http://www.cs.sunysb.edu/~skiena/392/pr ... distance.c
http://www.cs.sunysb.edu/~skiena/392/pr ... ringedit.c

[Abednego]

But you didn't submit 3 files to the judge. If you send me the source code that you submitted, I can run the special correction program on it and tell you what your mistake is. My email is abednego at gmail.

[tRipper]

This problem is driving me mad too!
This time i get TLE, and I really can't find a rational explanation for it. Can somebody help me?

Code: Select all

#include <iostream>
#include <string>

using namespace std;

string prva,druga;

int init() {
    string red;
    if (!getline(cin,red)) return 0;
    prva="";
    druga="";
    if (red[0]=='#') return 0;
    for (int i=0; i<red.size(); i++)
        if  (red[i]==' ') {
            prva=red.substr(0,i);
            druga=red.substr(i+1,red.size()-i-1);
            break;
        }    
    return 1;
}

string make(string a, char z, int r) {
       string sol=a;
       sol+=z;
       sol=sol+char(r/10+'0');
       sol=sol+char(r%10+'0');
       return sol;
}

string min(string a, string b, string c) {
       string m=a;
       if (b.size()<m.size()) m=b;
       if (c.size()<m.size()) m=c;
       return m;
}

string solve() {
       string matrix[100][100];
       matrix[0][0]="";
       for (int i=1; i<=druga.size(); i++)
           matrix[i][0]=matrix[i-1][0]+make("I",druga[i-1],i);
       for (int i=1; i<=prva.size(); i++)
           matrix[0][i]=matrix[0][i-1]+make("D",prva[i-1],i);
           
       for (int i=1; i<=druga.size(); i++)
           for (int j=1; j<=prva.size(); j++) {
               if (druga[i-1]==prva[j-1]) matrix[i][j]=matrix[i-1][j-1]; else
               matrix[i][j]=min(matrix[i][j-1]+make("D",prva[j-1],j),
                                matrix[i-1][j]+make("I",druga[i-1],i),
                                matrix[i-1][j-1]+make("C",druga[i-1],i));
                                
           }                                                                                                                           
       return matrix[druga.size()][prva.size()];
}
       
int main() {
    while (init()) {
          cout << solve()+"E" << endl;
    }
    return 0;
}