164 - String Computer

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

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

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

[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

[Yuffie Choi]

Thx for telling!!!!

[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]

[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

[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

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

[Ivan Golubev]

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

[junjieliang]

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

[epsilon0]

this problem seems interesting...

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

[Ivan Golubev]

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

Yes, my solution can handle cases with blank lines.

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

[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