Page **1** of **9**

Posted: **Wed Feb 06, 2002 4:33 pm**

by **MegaS**

I really tried to accept this problem many times. I even wrote a test program - and I'm sure my program outs right answer - I mean correct to transform String1 to String2.

Maybe it's not a best solution, but I'm sure it's right. Maybe someone know a small gluk in this problem?

Posted: **Wed Feb 06, 2002 4:56 pm**

by **Even**

try this...

abcbdab bdcaba

abcde bcgfe

abc abcdeeeee

abdddd absed

yrnkpnbcwobtxw k

juxpjik lfjlpjhrzzb

#

my answer is...

Da01Da01Da01Ic03Ia06E

Da01Cg03If04E

Id04Ie05Ie06Ie07Ie08Ie09E

Cs03Ce04Dd05E

Dy01Dy01Dy01Dr02Dr02Dr02Dr02Dr02Dr02Dr02Dr02Dr02Dr02E

Cl01Cf02Cj03Il04Ch07Cr08Iz09Iz10Ib11E

the answer may not only...

any correct answer will accept...

if it has the minimal step...

### 164 - String Computer

Posted: **Wed May 29, 2002 4:57 pm**

by **Yuffie Choi**

There is a note saying: "A bug in the Online Judge has caused the problems 104, 120 and 164 to be incorrectly judged in some cases. "

Is the msg update and the problem still exists???

I have been debugging the program for a few days but still get wrong answer. I wonder if it is my mistake or caused by the bug.....~_~

Can anyone help me??

Posted: **Sun Jun 16, 2002 4:18 pm**

by **wyvmak**

I guess that's really your bug, coz that statement "A bug in the Online Judge has caused the problems 104, 120 and 164 to be incorrectly judged in some cases. " has been here for years. Try more test cases with your program like:

abcxdefxghix abcyydefyyghiyy

### Thx

Posted: **Sun Jun 16, 2002 4:56 pm**

by **Yuffie Choi**

Thx for telling!!!!

### help~164(string computer)

Posted: **Sun Jul 21, 2002 8:54 pm**

by **scarstar**

help~

I don't understand why WA.

I use a Levenshtein Distance(edit Distance) algorithims.

help~

[c]

#include <stdio.h>

#define m(x,y) (((x)<(y))?(x):(y))

int t[30][30];

char is[100][10];

main(){

int i,j,min,k;

char ss[21],ts[21];

while(scanf("%s%s",ss,ts)){

if(ss[0]=='#')

break;

t[0][0]=0;

for(i=1;i<=strlen(ts);i++)

t[0]*=i;*

for(i=1;i<=strlen(ss);i++)

t*[0]=i; *

for(i=1;i<=strlen(ss);i++)

for(j=1;j<=strlen(ts);j++)

t*[j]=m(m(t[i-1][j-1]+((ts[j-1]==ss[i-1])?0:1),t[i-1][j]+1),t**[j-1]+1); *

j=strlen(ts);i=strlen(ss);

while(t*[j]!=0){*

if(i==0)

min=t*[j-1];*

else if(j==0)

min=t[i-1][j];

else

min=m(m(t[i-1][j-1],t[i-1][j]),t*[j-1]);*

if(min==t*[j]){ *

i--;j--;

}

else if(min==t[i-1][j]&&i!=0){

sprintf(is[t*[j]],"D%c%02d",ss[i-1],j+1);*

i--;

}

else if(min==t*[j-1]&&j!=0){*

sprintf(is[t[i][j]],"I%c%02d",ts[j-1],j);

j--;

}

else if(min==t[i-1][j-1]){

sprintf(is[t[i][j]],"C%c%02d",ts[j-1],j);

j--;i--;

}

}

for(k=1;k<=t[strlen(ss)][strlen(ts)];k++)

printf("%s",is[k]);

printf("E\n");

}

}

[/c]

### 164 is driving me mad (String Computer)

Posted: **Tue Oct 15, 2002 11:54 pm**

by **sophisticate**

Another one of those "why am I getting WA?!" questions...

Given the following test data, my solution-pending calculates the results thereafter. I've accounted for same-string pairs, and pairs with empty strings and am still getting WA.

I'm spending too long dwelling on this. Threats of institutionalization are coming from people I don't even know. Please help

abcde bcgfe

abcdefghijkl bcdeffghixkl

bird abird

bird sirdsd

bird irde

a bc

a ba

bac bc

bac ba

abcxdefxghix abcyydefyyghiyy

a a

a

a b

b

#

Da01Cg03If04E

Da01If06Cx10E

Ia01E

Cs01Is05Id06E

Db01Ie04E

Cb01Ic02E

Ib01E

Da02E

Dc03E

Cy04Iy05Cy09Iy10Cy14Iy15E

E

Da01E

Cb01E

Ib01E

---

sophie

### continuation...

Posted: **Wed Oct 16, 2002 12:15 am**

by **sophisticate**

I should mention that in that last line of the test case, there should be a space before the 'b'. Also, what I'm looking for are suggestions on test data... I'm not interested in seeing any code. Thanks!

---

sophie

Posted: **Wed Nov 20, 2002 3:00 pm**

by **junjieliang**

I'm getting WA as well, but the problem is that my code works for 526. Isn't both problems about edit distance? Could someone tell me the difference (if any) between the two problems?

Posted: **Wed Nov 20, 2002 3:32 pm**

by **Ivan Golubev**

junjieliang wrote:I'm getting WA as well, but the problem is that my code works for 526. Isn't both problems about edit distance? Could someone tell me the difference (if any) between the two problems?

I've got AC for P164 and WA for P526 (with same algorithm), so I'm also puzzled about this thing...

Posted: **Thu Nov 21, 2002 12:11 pm**

by **junjieliang**

Did you take into account empty strings, ie blank lines?

### interesting problem...

Posted: **Fri Nov 22, 2002 11:49 am**

by **epsilon0**

this problem seems interesting...

how do you go about finding a minimal X9091 program? this must be difficult...

Posted: **Fri Nov 22, 2002 2:55 pm**

by **Ivan Golubev**

junjieliang wrote:Did you take into account empty strings, ie blank lines?

Yes, my solution can handle cases with blank lines.

### Strange

Posted: **Thu Mar 20, 2003 7:58 pm**

by **yiuyuho**

This is strange:

I calculated the distance and back track:

I track for IDC and I got WA, but when I track in the order DIC I get AC, then I discover:

IDC, DCI, CID --> WA

DIC, ICD, CDI --> AC

The procedures of tracking is exactly identical, only the if-statements order is altered, how can that alter the outcome?

It there something wrong with the judge?

Posted: **Mon Apr 21, 2003 12:14 pm**

by **Maxim**

My problem is that I can calculate the minimum edit distance between these two strings and cannot reconstruct solution. I know it should be recursive function, but I find it difficult to implement it. Can anybody help? I