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
MegaS
New poster
Posts: 9
Joined: Tue Feb 05, 2002 2:00 am

Post by MegaS » Wed Feb 06, 2002 4:33 pm

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
Learning poster
Posts: 75
Joined: Thu Nov 22, 2001 2:00 am
Location: Taiwan

Post by Even » Wed Feb 06, 2002 4:56 pm

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
New poster
Posts: 3
Joined: Wed May 29, 2002 4:48 pm
Location: Hong Kong
Contact:

164 - String Computer

Post by Yuffie Choi » Wed May 29, 2002 4:57 pm

:cry: 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??
Yuffie @.@

wyvmak
Experienced poster
Posts: 110
Joined: Thu Dec 13, 2001 2:00 am

Post by wyvmak » Sun Jun 16, 2002 4:18 pm

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
New poster
Posts: 3
Joined: Wed May 29, 2002 4:48 pm
Location: Hong Kong
Contact:

Thx

Post by Yuffie Choi » Sun Jun 16, 2002 4:56 pm

Thx for telling!!!!
Yuffie @.@

scarstar
New poster
Posts: 1
Joined: Sun Jul 21, 2002 8:36 pm
Location: Korea,

help~164(string computer)

Post by scarstar » Sun Jul 21, 2002 8:54 pm

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
New poster
Posts: 3
Joined: Sun Jan 20, 2002 2:00 am

164 is driving me mad (String Computer)

Post by sophisticate » Tue Oct 15, 2002 11:54 pm

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
New poster
Posts: 3
Joined: Sun Jan 20, 2002 2:00 am

continuation...

Post by sophisticate » Wed Oct 16, 2002 12:15 am

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
Experienced poster
Posts: 169
Joined: Wed Oct 31, 2001 2:00 am
Location: Singapore

Post by junjieliang » Wed Nov 20, 2002 3:00 pm

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
Experienced poster
Posts: 167
Joined: Fri Oct 19, 2001 2:00 am
Location: Saint Petersburg, Russia

Post by Ivan Golubev » Wed Nov 20, 2002 3:32 pm

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

junjieliang
Experienced poster
Posts: 169
Joined: Wed Oct 31, 2001 2:00 am
Location: Singapore

Post by junjieliang » Thu Nov 21, 2002 12:11 pm

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

epsilon0
Experienced poster
Posts: 112
Joined: Tue Nov 12, 2002 11:15 pm
Location: Paris, France.

interesting problem...

Post by epsilon0 » Fri Nov 22, 2002 11:49 am

this problem seems interesting...

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

Ivan Golubev
Experienced poster
Posts: 167
Joined: Fri Oct 19, 2001 2:00 am
Location: Saint Petersburg, Russia

Post by Ivan Golubev » Fri Nov 22, 2002 2:55 pm

junjieliang wrote:Did you take into account empty strings, ie blank lines?
Yes, my solution can handle cases with blank lines.

yiuyuho
A great helper
Posts: 325
Joined: Thu Feb 21, 2002 2:00 am
Location: United States
Contact:

Strange

Post by yiuyuho » Thu Mar 20, 2003 7:58 pm

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?

User avatar
Maxim
New poster
Posts: 38
Joined: Tue Aug 27, 2002 12:36 am
Location: Croatia
Contact:

Post by Maxim » Mon Apr 21, 2003 12:14 pm

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

Post Reply

Return to “Volume 1 (100-199)”