## 164 - String Computer

Moderator: Board moderators

RehabReda
New poster
Posts: 5
Joined: Thu Dec 03, 2009 8:25 pm

### Re: problem 164 .. why WA !! ???

btw if u know how to solve this share it Mans
New poster
Posts: 4
Joined: Wed Dec 02, 2009 6:21 am

### Re: problem 164 .. why WA !! ???

RehabReda wrote:
: D yup , because i was using my previous implementation of the Edit Distance Algorithm (copy and paste ! ):d

btw i had tested ur code ..
try to test your program with the following test case , i think it give "out of range" exception ! ..

input
wrrr awwsa

output form uvakit

Ia01Cw03Cs04Ca05EMans
thanks very much
yes i have changed it which was a trivial mistake j instead of i i have found a bug in your code which also find it in mine
this case
wwwww wwwwwww
in ur code and me
the output :
Iw01Iw02E
Iw06Iw07E
hmmm
but i think our output is also right !

because i can add W , W at the front or at the end ! the result string is the same ..

quote from problem statement "Since there may be multiple solutions, only one should be produced. Any solution that satisfies these criteria will be accepted. " ..

i am sure that our mistake is at finding path ! .. may be because when adding or removing a char the index must change in the next operations !

for example !.

it will add f at 01 and add l at 02 , then remove x from 06 !!

Mans
New poster
Posts: 4
Joined: Wed Dec 02, 2009 6:21 am

### Re: problem 164 .. why WA !! ???

RehabReda wrote:btw if u know how to solve this share it finally i get AC e7l :d lol

and ur code also get AC

your mistake was as i expected !... when you try to find the path ..

1-you must increment number of add or del at the end of each case , i mean after display the index .
2-in the insertion case .. the index will be J only without any addition or subtraction ! ..
3-in the deletion case ... the index will be j+NoOfAdditions-NoOfDeletions only , without add 1 ! .

so try to edit your printChanges function to :

Code: Select all

``````void printChanges(int i,int j)
{

if ( (i==0&&j==0))
return;
if(Tracing[i][j]==1)//Means Copy
{
printChanges(i-1,j-1);
}
else if (Tracing[i][j]==2)//Means Replace
{
printChanges(i-1,j-1);
cout<<"C"<<SecondString[i-1];
cout<<"0";
}
else if (Tracing[i][j]==3)//Means Delete
{
printChanges(i,j-1);
cout<<"D"<<FirstString[j-1];
cout<<"0";
NoOfDeletions++;
}
{

printChanges(i-1,j);
cout<<"I"<<SecondString[i-1];
if(i<10)
cout<<"0";
cout<<i;
}
}
``````
and you will get it accepted isA :d

RehabReda
New poster
Posts: 5
Joined: Thu Dec 03, 2009 8:25 pm

### Re: problem 164 .. why WA !! ???

Mans wrote:
RehabReda wrote:btw if u know how to solve this share it finally i get AC e7l :d lol

and ur code also get AC

your mistake was as i expected !... when you try to find the path ..

1-you must increment number of add or del at the end of each case , i mean after display the index .
2-in the insertion case .. the index will be J only without any addition or subtraction ! ..
3-in the deletion case ... the index will be j+NoOfAdditions-NoOfDeletions only , without add 1 ! .

so try to edit your printChanges function to :

Code: Select all

``````void printChanges(int i,int j)
{

if ( (i==0&&j==0))
return;
if(Tracing[i][j]==1)//Means Copy
{
printChanges(i-1,j-1);
}
else if (Tracing[i][j]==2)//Means Replace
{
printChanges(i-1,j-1);
cout<<"C"<<SecondString[i-1];
cout<<"0";
}
else if (Tracing[i][j]==3)//Means Delete
{
printChanges(i,j-1);
cout<<"D"<<FirstString[j-1];
cout<<"0";
NoOfDeletions++;
}
{

printChanges(i-1,j);
cout<<"I"<<SecondString[i-1];
if(i<10)
cout<<"0";
cout<<i;
}
}
``````
and you will get it accepted isA :d
thanks alot i get accepted el7dl thanks ^ infinity ^infinity

aia
New poster
Posts: 5
Joined: Wed Dec 02, 2009 12:01 am

### Re: problem 164 .. why WA !! ???

??? ?? ?????? ??? ???? ?? ??????? ??
???????? ????? ?? ?? ????? ??? ????? cases ? ??
?? ????? ????? ??? ???? ????????

Code: Select all

``````#include<iostream>
#include<vector>
#include<string>
//#include<fstream>
#include<math.h>
using namespace std ;
//fstream fin ("IN.txt");
//fstream fout("Out.txt");
string str1 , str2;
int Table;
int i , j ;
int minimum(int x ,int y,int  z)
{
int result ;
result = min(x , y);
result= min(result , z);
return result;
}

string convert(int num)
{
string number="" ;
int tempnum =num ;
int i=0 ;
while(num!=0)
{
if(num>=1 && num<=9)
number+=num+'0' ;
else
number+=(num%10)+'0' ;
num/=10 ;
i++;
}
string temp = number ;
if(tempnum>=1 &&tempnum<=9)
{
number = "0"+temp;
}
else
{
for(int j=0 ;j<number.length() ; j++)
number[j] = temp[temp.length()-1-j];
}
return number ;
}

int EditDistance(string dist , string source)
{
for ( i=0 ; i<=dist.length() ; i++)
Table[i] = i ;// deletion
for (j=0 ; j<=source.length() ; j++)
Table[j] = j; // insertion
for (j= 1 ;j<=source.length() ; j++)
{
for ( i=1 ; i<=dist.length() ; i++)
{
if( dist[i-1] == source[j-1])
Table[i][j] = Table[i-1][ j-1];
else
{
Table[i][j]= minimum
(
Table[i-1][j] + 1,  // deletion
Table[i][j-1] + 1,  // insertion
Table[i-1][j-1] + 1 // substitution
);
}
}
}

return Table[dist.length()][source.length()];
}

string BackTracke(int x , int y)
{
string temp ;
string number;
if(x>0&&y==0)
{
number = convert(x);
temp="D" ;
temp.append(1 , str1[x-1]);
temp+=number ;
return BackTracke(x-1 , y)+temp;
}
else if(x==0 &&y>0)
{
number = convert(y);
temp="I" ;
temp.append(1 , str2[y-1]);
temp+=number ;
return BackTracke(x , y-1)+temp;
}
else if(x==0 &&y>0)
{
number = convert(y);
temp="D" ;
temp.append(1 , str2[y-1]);
temp+=number ;
return BackTracke(x , y-1)+temp;
}
else if(x==0 ||y==0)
return"";
else if(str1[x-1]==str2[y-1])
return BackTracke(x-1 , y-1);
else
{
if(Table[x][y]==Table[x-1][y] + 1)//delete
{
number = convert(y+1);
temp="D" ;
temp.append(1 , str1[x-1]);
temp+=number ;
return BackTracke(x-1 , y)+temp;
}
else if(Table[x][y]==Table[x][y-1]+1)//insertion
{
number = convert(y);
temp="I" ;
temp.append(1 , str2[y-1]);
temp+=number ;
return BackTracke(x, y-1)+temp;
}
else if(Table[x][y]==Table[x-1][y-1]+1) //change Table[x-1][y-1] + 1
{
number = convert(y);
temp="C" ;
temp.append(1 , str2[y-1]);
temp+=number ;
return BackTracke(x-1 , y-1)+temp;
}

}
}
int main()
{
int s ;
while(cin>>str1)
{
if(str1=="#")
break;
cin>>str2;
if(str1==""&&str2=="")
{
cout<<"E"<<endl;
continue ;
}
s= EditDistance(str1, str2);
string n = BackTracke(str1.length(), str2.length());
cout<<n<<"E"<<endl;
}
return 0 ;
}``````
???? ?????

aia
New poster
Posts: 5
Joined: Wed Dec 02, 2009 12:01 am

### Re: #164 I think there is a bug in your tests!!!

plz could anyone help me to know the bug in my code in this Problem
this is my code :

Code: Select all

``````#include<iostream>
#include<vector>
#include<string>
//#include<fstream>
#include<math.h>
using namespace std ;
//fstream fin ("IN.txt");
//fstream fout("Out.txt");
string str1 , str2;
int Table;
int i , j ;
int minimum(int x ,int y,int  z)
{
int result ;
result = min(x , y);
result= min(result , z);
return result;
}

string convert(int num)
{
string number="" ;
int tempnum =num ;
int i=0 ;
while(num!=0)
{
if(num>=1 && num<=9)
number+=num+'0' ;
else
number+=(num%10)+'0' ;
num/=10 ;
i++;
}
string temp = number ;
if(tempnum>=1 &&tempnum<=9)
{
number = "0"+temp;
}
else
{
for(int j=0 ;j<number.length() ; j++)
number[j] = temp[temp.length()-1-j];
}
return number ;
}

int EditDistance(string dist , string source)
{
for ( i=0 ; i<=dist.length() ; i++)
Table[i] = i ;// deletion
for (j=0 ; j<=source.length() ; j++)
Table[j] = j; // insertion
for (j= 1 ;j<=source.length() ; j++)
{
for ( i=1 ; i<=dist.length() ; i++)
{
if( dist[i-1] == source[j-1])
Table[i][j] = Table[i-1][ j-1];
else
{
Table[i][j]= minimum
(
Table[i-1][j] + 1,  // deletion
Table[i][j-1] + 1,  // insertion
Table[i-1][j-1] + 1 // substitution
);
}
}
}

return Table[dist.length()][source.length()];
}

string BackTracke(int x , int y)
{
string temp ;
string number;
if(x==str1.length()+1&&y==str2.length()+1)
{
return BackTracke(x-1 , y-1)+"E";
}
if(x>0&&y==0)
{
number = convert(x);
temp="D" ;
temp.append(1 , str1[x-1]);
temp+=number ;
return BackTracke(x-1 , y)+temp;
}
else if(x==0 &&y>0)
{
number = convert(y);
temp="I" ;
temp.append(1 , str2[y-1]);
temp+=number ;
return BackTracke(x , y-1)+temp;
}
else if(x==0 &&y>0)
{
number = convert(y);
temp="D" ;
temp.append(1 , str2[y-1]);
temp+=number ;
return BackTracke(x , y-1)+temp;
}
else if(x==0 ||y==0)
return"";
else if(str1[x-1]==str2[y-1])
return BackTracke(x-1 , y-1);
else
{
if(Table[x][y]==Table[x-1][y] + 1)//delete
{
number = convert(y+1);
temp="D" ;
temp.append(1 , str1[x-1]);
temp+=number ;
return BackTracke(x-1 , y)+temp;
}
else if(Table[x][y]==Table[x][y-1]+1)//insertion
{
number = convert(y);
temp="I" ;
temp.append(1 , str2[y-1]);
temp+=number ;
return BackTracke(x, y-1)+temp;
}
else if(Table[x][y]==Table[x-1][y-1]+1) //change Table[x-1][y-1] + 1
{
number = convert(y);
temp="C" ;
temp.append(1 , str2[y-1]);
temp+=number ;
return BackTracke(x-1 , y-1)+temp;
}

}
}
int main()
{
int s ;
while(cin>>str1)
{
if(str1=="#")
break;
cin>>str2;
s= EditDistance(str1, str2);
string n = BackTracke(str1.length()+1, str2.length()+1);
cout<<n<<endl;
}
return 0 ;
}``````

sa.phoenix
New poster
Posts: 1
Joined: Fri Jan 06, 2012 10:27 pm

### WA for Problem 164: String Computer

Hi all,

My solution for Problem 164 is giving WA on the judge. I have tested my solution with some test cases of my own as well as the testcases posted in the links http://acm.uva.es/board/viewtopic.php?f=1&t=42480 and http://acm.uva.es/board/viewtopic.php?f=1&t=44516 , and my solution produces the correct output for all of them.

I also tried changing the priority for the resultant output from DELETE > INSERT > MATCH to MATCH > INSERT > DELETE as mentioned in http://acm.uva.es/board/viewtopic.php?f=1&t=42480 , but i still get WA.

Can someone point me to a testcase where my code fails to produce the correct output?

My C++ code is posted below:

Code: Select all

``````#include <iostream>
#include <cstring>
#include <cstdio>
#include <string>
#include <sstream>
using namespace std;
#define LET(_x,_a) typeof(_a) _x(_a)
#define FOR(_i, _a, _n) for(LET(_i, _a); _i != _n; ++_i)
#define REP(_i, _n) FOR(_i, 0, _n)
#define sz size()
#define i2s(_x) ({stringstream sout; sout<<_x; sout.str();})
#define s2i(_str) ({stringstream sin(_str); int _x; sin>>_x; _x;})

int main()
{
string line;
while(getline(cin, line))
{
if(line == "#")break;
int spaceindex = line.find(' ');
string first = line.substr(0, spaceindex), second = line.substr(spaceindex+1);
if(first == "#")break; //hopefully, the line == "#" check should itself suffice
//clock_t start = clock();

//Perform the Edit Distance
int M = first.sz, N = second.sz;
int dp[M+1][N+1]; memset(dp, 0, sizeof(dp));
FOR(i, 1, M+1)dp[i] = i;
FOR(j, 1, N+1)dp[j] = j;

FOR(i, 1, M+1)FOR(j, 1, N+1)
{
if(first[i-1] == second[j-1])dp[i][j] = dp[i-1][j-1];
else dp[i][j] = dp[i-1][j-1] + 1;

if(dp[i][j] > dp[i-1][j] + 1)dp[i][j] = dp[i-1][j] + 1;

if(dp[i][j] > dp[i][j-1] + 1)dp[i][j] = dp[i][j-1] + 1;
}

//REP(i, M+1){REP(j, N+1)cout<<dp[i][j]<<" "; cout<<endl;}

//Form the resultant output string
string ret = "E";
for(int i = M, j = N; i >= 0 && j >= 0;) //tried changing priority from DELETE > INSERT > MATCH to MATCH > INSERT > DELETE, still WA :(
if(i > 0 && dp[i][j] == dp[i-1][j] + 1)ret = (string)"D" + first[i-1] + (i <= 9 ? "0" : "") + i2s(i) + ret , i--;
else if(j > 0 && dp[i][j] == dp[i][j-1] + 1)ret = (string)"I" + second[j-1] + (j <= 9 ? "0" : "") + i2s(j) + ret, j--;
else if(i > 0 && j > 0 && dp[i][j] == dp[i-1][j-1] + 1 && first[i-1] != second[j-1])ret = (string)"C" + second[j-1] + (j <= 9 ? "0" : "") + i2s(j) + ret, i--, j--;
else i--, j--;

//Fix the index change for Delete operation due to the delete/insert operations.
//Insert is already taken care of because Insert deals with the position in the second string
int numdeletes = 0;
REP(i, ret.sz)
if(ret[i]=='D')
{
int val = 10 * (int)(ret[i+2] - '0') + (int)(ret[i+3] - '0');
val -= numdeletes;
numdeletes++;
if(val > 9)ret[i+2] = (char)(val/10 + '0');
ret[i+3] = (char)(val % 10 + '0');
}
else if(ret[i] == 'I')numdeletes--;

cout<<ret<<endl;
//clock_t end = clock();
//cout<<"Time taken: "<<(double)(end-start)/(double)CLOCKS_PER_SEC<<" seconds"<<endl;
}
return 0;
}

``````

just_yousef
New poster
Posts: 50
Joined: Tue Dec 17, 2013 11:01 pm

### Re: problem 164 .. why WA !! ???

I got 11 WA, Please Help !! Code: Select all

``````AC
``````
Last edited by just_yousef on Tue Aug 12, 2014 11:52 pm, edited 1 time in total.

lighted
Guru
Posts: 587
Joined: Wed Jun 11, 2014 9:56 pm
Location: Kyrgyzstan, Bishkek

### Re: problem 164 .. why WA !! ???

http://online-judge.uva.es/board/viewtopic.php?t=1526
A person who sees the good in things has good thoughts. And he who has good thoughts receives pleasure from life... Bediuzzaman

just_yousef
New poster
Posts: 50
Joined: Tue Dec 17, 2013 11:01 pm

### Re: problem 164 .. why WA !! ???

Thanks lighted, Finally AC jddantes
Learning poster
Posts: 73
Joined: Sat Mar 08, 2014 8:55 am

### Re: 164 - String Computer

AC.
Printed Da instead of D[character] so I got WA.
Last edited by jddantes on Thu Apr 09, 2015 12:56 pm, edited 1 time in total.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 164 - String Computer

Try running your code on the sample input.
Check input and AC output for thousands of problems on uDebug!

jddantes
Learning poster
Posts: 73
Joined: Sat Mar 08, 2014 8:55 am

### Re: 164 - String Computer

Output: If05Cg04Da01E
From input: abcde bcgfe
Isn't this still valid?

abcde

Insert f at 05
abcdfe

Change 04 to g
abcgfe

Delete 01
bcgfe

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 164 - String Computer

It looks like your code isn't terminating on #
http://ideone.com/sGgOsw
Check input and AC output for thousands of problems on uDebug!

jddantes
Learning poster
Posts: 73
Joined: Sat Mar 08, 2014 8:55 am

### Re: 164 - String Computer

http://ideone.com/DEUg65
I've changed to cin instead to accomodate input like this (still WA)

Code: Select all

``````abcde bcgfe
asdf

#
``````
uDebug output:

Code: Select all

``````Da01Ig03Cf04E
Is02Da04Cf04E
``````
My output (verified by hand):
``````If05Cg04Da01E