Page 8 of 9

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

Posted: Fri Dec 04, 2009 7:46 am
btw if u know how to solve this share it

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

Posted: Fri Dec 04, 2009 9:26 am
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 !!

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

Posted: Fri Dec 04, 2009 10:40 am
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

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

Posted: Fri Dec 04, 2009 11:35 am
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

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

Posted: Fri Dec 04, 2009 4:59 pm
??? ?? ?????? ??? ???? ?? ??????? ??
???????? ????? ?? ?? ????? ??? ????? 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[100][100];
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][0] = i ;// deletion
for (j=0 ; j<=source.length() ; j++)
Table[0][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 ;
}``````
???? ?????

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

Posted: Mon Dec 07, 2009 10:10 pm
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[100][100];
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][0] = i ;// deletion
for (j=0 ; j<=source.length() ; j++)
Table[0][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 ;
}``````

### WA for Problem 164: String Computer

Posted: Fri Jan 06, 2012 10:52 pm
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][0] = i;
FOR(j, 1, N+1)dp[0][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;
}

``````

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

Posted: Thu Aug 07, 2014 1:13 am

Code: Select all

``````AC
``````

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

Posted: Thu Aug 07, 2014 11:01 am

http://online-judge.uva.es/board/viewtopic.php?t=1526

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

Posted: Thu Aug 07, 2014 1:24 pm
Thanks lighted, Finally AC

### Re: 164 - String Computer

Posted: Tue Feb 10, 2015 4:16 pm
AC.
Printed Da instead of D[character] so I got WA.

### Re: 164 - String Computer

Posted: Tue Feb 10, 2015 11:45 pm
Try running your code on the sample input.

### Re: 164 - String Computer

Posted: Wed Feb 11, 2015 10:33 am
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

### Re: 164 - String Computer

Posted: Wed Feb 11, 2015 9:15 pm
It looks like your code isn't terminating on #
http://ideone.com/sGgOsw

### Re: 164 - String Computer

Posted: Thu Feb 12, 2015 9:55 am
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