
164 - String Computer
Moderator: Board moderators
Re: problem 164 .. why WA !! ???
btw if u know how to solve this share it 

Re: problem 164 .. why WA !! ???
hmmmRehabReda wrote:thanks very much: 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
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
the right answer:
Iw06Iw07E
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 !.
addx fladd
it will add f at 01 and add l at 02 , then remove x from 06 !!
Re: problem 164 .. why WA !! ???
finally i get AC e7l :d lolRehabReda wrote:btw if u know how to solve this share it
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];
if(j+NoOfAdditions-NoOfDeletions<10)
cout<<"0";
cout<<j+NoOfAdditions-NoOfDeletions;
}
else if (Tracing[i][j]==3)//Means Delete
{
printChanges(i,j-1);
cout<<"D"<<FirstString[j-1];
if(j+NoOfAdditions-NoOfDeletions<10)
cout<<"0";
cout<<j+NoOfAdditions-NoOfDeletions;
NoOfDeletions++;
}
else if (Tracing[i][j]==4)//Means Add
{
printChanges(i-1,j);
cout<<"I"<<SecondString[i-1];
if(i<10)
cout<<"0";
cout<<i;
NoOfAdditions++;
}
}
Re: problem 164 .. why WA !! ???
thanks alot i get accepted el7dlMans wrote:finally i get AC e7l :d lolRehabReda wrote:btw if u know how to solve this share it
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 :
and you will get it accepted isA :dCode: 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]; if(j+NoOfAdditions-NoOfDeletions<10) cout<<"0"; cout<<j+NoOfAdditions-NoOfDeletions; } else if (Tracing[i][j]==3)//Means Delete { printChanges(i,j-1); cout<<"D"<<FirstString[j-1]; if(j+NoOfAdditions-NoOfDeletions<10) cout<<"0"; cout<<j+NoOfAdditions-NoOfDeletions; NoOfDeletions++; } else if (Tracing[i][j]==4)//Means Add { printChanges(i-1,j); cout<<"I"<<SecondString[i-1]; if(i<10) cout<<"0"; cout<<i; NoOfAdditions++; } }

thanks ^ infinity ^infinity
Re: problem 164 .. why WA !! ???
??? ?? ?????? ??? ???? ?? ??????? ??
???????? ????? ?? ?? ????? ??? ????? cases ? ??
?? ????? ????? ??? ???? ????????
???? ?????
???????? ????? ?? ?? ????? ??? ????? 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!!!
plz could anyone help me to know the bug in my code in this Problem
this is my code :
Thanks in advance
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 ;
}
-
- 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:
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;
}
-
- 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.
Re: problem 164 .. why WA !! ???
A person who sees the good in things has good thoughts. And he who has good thoughts receives pleasure from life... Bediuzzaman
-
- New poster
- Posts: 50
- Joined: Tue Dec 17, 2013 11:01 pm
Re: problem 164 .. why WA !! ???
Thanks lighted, Finally AC 

Re: 164 - String Computer
AC.
Printed Da instead of D[character] so I got WA.
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.
-
- 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!
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
From input: abcde bcgfe
Isn't this still valid?
abcde
Insert f at 05
abcdfe
Change 04 to g
abcgfe
Delete 01
bcgfe
-
- 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
http://ideone.com/sGgOsw
Check input and AC output for thousands of problems on uDebug!
Re: 164 - String Computer
http://ideone.com/DEUg65
I've changed to cin instead to accomodate input like this (still WA)
uDebug output:
My output (verified by hand):
(adam->asdam->asdm->asdf for second output)
I've changed to cin instead to accomodate input like this (still WA)
Code: Select all
abcde bcgfe
adam
asdf
#
Code: Select all
Da01Ig03Cf04E
Is02Da04Cf04E
(adam->asdam->asdm->asdf for second output)
Code: Select all
If05Cg04Da01E
Da04Cf03Is02E