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

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

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

Post by RehabReda »

btw if u know how to solve this share it :D

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

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

Post by Mans »

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 :D
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
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 !.
addx fladd

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

Post by Mans »

RehabReda wrote:btw if u know how to solve this share it :D
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];
          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++;
       }
    }
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 !! ???

Post by RehabReda »

Mans wrote:
RehabReda wrote:btw if u know how to solve this share it :D
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];
          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++;
       }
    }
and you will get it accepted isA :d
thanks alot i get accepted el7dl :D
thanks ^ infinity ^infinity

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

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

Post by aia »

??? ?? ?????? ??? ???? ?? ??????? ??
???????? ????? ?? ?? ????? ??? ????? 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 ; 
}
???? ?????

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

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

Post by aia »

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 ; 
}
Thanks in advance

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

WA for Problem 164: String Computer

Post by sa.phoenix »

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;
}


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

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

Post by just_yousef »

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

Post by lighted »

chunyi81 wrote:Did you read this thread?

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

Post by just_yousef »

Thanks lighted, Finally AC :D

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

Re: 164 - String Computer

Post by jddantes »

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

Post by brianfry713 »

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

Post by jddantes »

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

Post by brianfry713 »

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

Post by jddantes »

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

Code: Select all

abcde bcgfe
 adam
asdf 
 
#
uDebug output:

Code: Select all

Da01Ig03Cf04E
Is02Da04Cf04E
My output (verified by hand):
(adam->asdam->asdm->asdf for second output)

Code: Select all

If05Cg04Da01E
Da04Cf03Is02E

Post Reply

Return to “Volume 1 (100-199)”