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
User avatar
Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria

Post by Sedefcho » Tue May 24, 2005 5:00 pm

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

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

Post by Abednego » Tue May 24, 2005 5:30 pm

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

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

Post by Sedefcho » Tue May 24, 2005 5:50 pm

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 !

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

Post by Abednego » Tue May 24, 2005 7:21 pm

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 » Tue May 24, 2005 7:36 pm

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.

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

Post by Sedefcho » Tue May 24, 2005 10:57 pm

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 » Tue May 31, 2005 2:26 pm

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

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

Post by Sedefcho » Tue May 31, 2005 3:05 pm

Just use the edit button :)

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

Question

Post by Ndiyaa ndako » Sat Jun 25, 2005 12:26 pm

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?

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

Post by Abednego » Sat Jun 25, 2005 1:20 pm

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

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

Post by Ndiyaa ndako » Sun Jun 26, 2005 9:46 am

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

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

Post by Abednego » Mon Jun 27, 2005 7:28 am

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


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

Post by Abednego » Wed Jun 29, 2005 5:21 am

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 » Tue Nov 01, 2005 7:12 pm

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)”