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

Post Reply
Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria

Post by 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
A great helper
Posts: 281
Joined: Tue Sep 10, 2002 5:14 am
Location: Mountain View, CA, USA
Contact:

Post by 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
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 »

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
A great helper
Posts: 281
Joined: Tue Sep 10, 2002 5:14 am
Location: Mountain View, CA, USA
Contact:

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

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

I cann't be bothered.

Post by 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.
Last edited by Experimenter on Wed Jun 01, 2005 11:44 am, edited 1 time in total.
it would be great if you replied this post. really.

Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria

Post by 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
Learning poster
Posts: 76
Joined: Thu Mar 13, 2003 5:12 am
Location: Russia

Post by Experimenter »

I cannot find this "delete"-button 2 delete it. :-?
it would be great if you replied this post. really.

Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria

Post by Sedefcho »

Just use the edit button :)

Ndiyaa ndako
New poster
Posts: 21
Joined: Sat Sep 25, 2004 3:35 am
Location: Oaxaca de Ju
Contact:

Question

Post by 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
A great helper
Posts: 281
Joined: Tue Sep 10, 2002 5:14 am
Location: Mountain View, CA, USA
Contact:

Post by Abednego »

Post your code here, and I will look at it. I hope that it's not a mistake in my special judge.
If only I had as much free time as I did in college...

Ndiyaa ndako
New poster
Posts: 21
Joined: Sat Sep 25, 2004 3:35 am
Location: Oaxaca de Ju
Contact:

Post by 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
A great helper
Posts: 281
Joined: Tue Sep 10, 2002 5:14 am
Location: Mountain View, CA, USA
Contact:

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

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

tRipper
New poster
Posts: 22
Joined: Sun Mar 13, 2005 5:04 pm
Location: out there

Post by 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;
}
If I am out of my mind, it's all right with me.

Post Reply

Return to “Volume 1 (100-199)”