164 - String Computer

[snar]

Hi all,
I was trying to solve this probem a year ago, I got WA, but I got AC for 526 which is the same problem as 164, expect the output format. Then I found that it was wrong judged. Did anybody solve this problem? Is it allright, or my solution is really wrong?

NOTE: I'm 90% sure that my solution is right.

Best Regards,

[Igor9669]

In all my tests my program gives a correct answers? I don't know why WA???

test:
abcde bcgfe
a accdd
accdd a
abcxdefxghix abcyydefyyghiyy
ddppqq dapaqaaa
aab aab
(space)dddd
dddd(space)

abcdefghijklxyztpr pacdfeoomnrdffrr
#

answer:
Da01Cg03If04E
Ic02Ic03Id04Id05E
Dc02Dc02Dd02Dd02E
Cy04Iy05Cy09Iy10Cy14Iy15E
Ca02Ca04Ca06Ia07Ia08E
E
Id01Id02Id03Id04E
Dd01Dd01Dd01Dd01E
E
Ip01Db03De05Ce06Co07Co08Cm09Cn10Cr11Cd12Cf13Cf14Cr15Dp16E


please check them!!!

[mf]

First of all, you forgot to mention which problem you're trying to solve. (Though I guess it's one of the find-smallest-edit-script problems)

It's far more likely that *your* program has a bug, than judge's tests. Thousands of people have already solved it, do you think they've all got it wrong?

[Igor9669]

this is a problem #164!!!
Are my answers correct???

[mf]

My accepted program's output is the same for all your tests except the last one. And the length of the output for the last one is the same, so that means it's probably also okay.

[Igor9669]

I had changed the priority from DELETE->INSERT->MATCH to MATCH->INSERT->DELETE and got Accepted!
I think it is very very strange.......

[behyyyy]

hi
can you explain about alghoritm of (164-string computer) program ?
why do you use 2 dimination arrays(b[j]-d[j])?
tanks for your help...
please tell me because very i need...

[alirezanoori]

Of course the problem is wrong! It says "Any solution that satisfies these criteria will be accepted" but its really obvious that it doesn't. I think instead of checking the answer with a program, the judge test your answer with a pre-defined answer that has this priority MATCH-INSERT-DELETE!

[hotwxn711]

for an instance
a acc
your answer is: D02cD03c
But it should be D02cD02c

[aia]

Hi ,
I don't know where is the bufg in my code but I suggest the bug is in this function when back track to read the statement
Could Anyone help me ?

Code: Select all

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

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

and I don't know the meaning of " Each will consist of a program in X9091 language "...


Thanks in advance

[Mans]

hello all

i had solve string computer problem several times in uva .. but i get WA
and i cann't know why my code is not acceptable !! ..
i wonder if anybody can help me with this code ! .. or give me some test cases to test my code ?:)

Code: Select all

#include <iostream>
#include <string>
#include <vector>	
#include <sstream>
using namespace std;

string S1,S2;
int table[1000][1000];
char instruction[1000][1000];

void cacl()
{
	for(unsigned int i=0;i<=S2.size();i++)
		{
			for(unsigned int j=0; j<=S1.size();j++)
			{
				if(i==0)
				{
					table[i][j]=j;//remove
					instruction[i][j]='D';
				}
				else if(j==0)
				{
					table[i][j]=i;//add
					instruction[i][j] = 'I';
				}
				else if(S1[j-1]==S2[i-1])//equal
				{
					table[i][j] = table[i-1][j-1];
					instruction[i][j] = 'E';
				}
				else
				{
					int minm ;
					minm = min(table[i-1][j-1],min(table[i-1][j],table[i][j-1]))+1;//replace
					table[i][j] = minm;
					
					 if(minm == table[i][j-1]+1)
						instruction[i][j] = 'D';
					else if(minm == table[i-1][j]+1)
						instruction[i][j] = 'I';
					else if(minm == table[i-1][j-1]+1)
						instruction[i][j] = 'C';
				}
			}
		}
}
void display()
{
	vector<string> result;
		int i = S2.size();
		int j = S1.size();
		for(int k=0 ; k<table[S2.size()][S1.size()];)
		{
			string temp ="";
			
			if(instruction[i][j]=='E')
			{
				
				i--;
				j--;
			}
			else if(instruction[i][j]=='D')
			{
				temp+="D";
				temp +=S1[j-1];
 				ostringstream oss;
				oss<<(i+1);
				if((i+1)<10)
				temp+="0";
				temp+= oss.str();
				result.push_back(temp);
		
				j--;
				k++;
			}
			else if(instruction[i][j]=='I')
			{
				temp+="I";
				temp +=S2[i-1];
 				ostringstream oss;
				oss<<i;
				if(i<10)
				temp+="0";
				temp+= oss.str();
				result.push_back(temp);
				i--;
				k++;
			}
			else
			{
				temp+="C";
				temp +=S2[i-1];
 				ostringstream oss;
				oss<<i;
				if(j<10)
				temp+="0";
				temp += oss.str();
				result.push_back(temp);

				int R1 = table[i-1][j-1];
				int R2 = table[i][j-1];
				int R3 = table[i-1][j];
				int chos = min(R1,min(R2,R3));
				if(chos == R1)
				{
					i--;
					j--;
				}else if(chos == R2)
				{
					j--;
				}
				else
				{
					i--;
				}

				k++;
			}

		}
		for(int i=result.size()-1;i>=0;i--)
			cout<<result[i];
		cout<<"E\n";
}

int main()
{
	while(cin>>S1>>S2&&S1!="#"&&S2!="#")
	{
		cacl();
		display();
	}
	return 0;
}

this is a sample form input and output from my program :

Code: Select all

input:
abcxdefxghix abcyydefyyghiyy
hhsagggg jjjhhhh
yyyyww hhqkkkj
iiyyash hhj
q hkakkkkkkk
ml l
wrrr awwsa
ooiiyy  mmnnvv
#

output:

Cy04Iy05Cy09Iy10Cy14Iy15E
Cj01Cj02Cj03Ch04Ch05Ch06Ch07Dg08E
Ch01Ch02Cq03Ck04Ck05Ck06Ij07E
Ch01Ch02Cj03Dy04Da04Ds04Dh04E
Ch01Ik02Ia03Ik04Ik05Ik06Ik07Ik08Ik09Ik10E
Dm01E
Ia01Cw03Cs04Ca05E
Cm01Cm02Cn03Cn04Cv05Cv06E
Press any key to continue . . .

thanks in advance:)

[5olio]

????? ?? ???? :D

[RehabReda]

@Mans
why you use this large size in the array?
int table[1000][1000];
char instruction[1000][1000];

and i also get wrong answer
this is my code

Code: Select all

#include<iostream>
using namespace std;
#include<string>
int EditDistance[30][30];
int Tracing[30][30];
string FirstString,SecondString;
int NoOfDeletions , NoOfAdditions;

int FindMin(int a,int b,int c,int i,int j)
{
	if(a<b&&a<c)
	{
		Tracing[i][j]=2;//Means Replace  
		return a;
	}
	else if(a<c)
	{
		Tracing[i][j]=3;//Means Delete
		return b;
	}
	else if(b<c)
	{
		Tracing[i][j]=3;//Means Delete
		return b;
	}
	else 
	{
		Tracing[i][j]=4;//Means Add
		return c;
	}
}

void printChanges(int i,int j)
{

	if ( (i==0&& j==0) || (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);  NoOfDeletions++;
		cout<<"D"<<FirstString[j-1];
		if(j+NoOfAdditions-NoOfDeletions<10)
			cout<<"0";
		cout<<j+NoOfAdditions-NoOfDeletions+1;
	}
	else if (Tracing[i][j]==4)//Means Add
	{
	
		printChanges(i-1,j);	NoOfAdditions++;
		cout<<"I"<<SecondString[j-1];
		if(j+NoOfAdditions-NoOfDeletions<10)
			cout<<"0";
		cout<<j+NoOfAdditions-NoOfDeletions;
	}
}

int main()
{
	cin>>FirstString>>SecondString;
while (FirstString!="#")
	{
	 NoOfDeletions=0;
	NoOfAdditions=0;

	int Operation1,Operation2,Operation3;

	int LengthOfFirstString=FirstString.length();
	int LengthOfSecondString=SecondString.length();

	EditDistance[0][0]=0;
	for(int i=1;i<=LengthOfSecondString;i++)
	{
	EditDistance[i][0]=EditDistance[i-1][0]+1;
	Tracing[i][0]=4;
	}
	for(int i=1;i<=LengthOfFirstString;i++)
	{
		EditDistance[0][i]=EditDistance[0][i-1]+1;
		Tracing[0][i]=3;
	}
	for(int i=1;i<=LengthOfFirstString;i++)
	{
		
		for(int j=1;j<=LengthOfSecondString;j++)
		{
			
				if(FirstString[i-1]==SecondString[j-1])//compare two letters 
				{ 
				

					EditDistance[j][i]=EditDistance[j-1][i-1];


					Tracing[j][i]=1;
					//this when the two letters are equal 
					//tracing [i][j]=1 means that we have copied the letter and not making any changes 
				}
			else 
			{
				
				
					Operation1=EditDistance[j-1][i-1]+1;//replace
				
				
					Operation3=EditDistance[j-1][i]+1;//add
				
				
					Operation2=EditDistance[j][i-1]+1;//delete
			
					EditDistance[j][i]=FindMin(Operation1,Operation2,Operation3,j,i);
				//get the min distance 
				//Operation 1 :replace d
				//Operation 2 :delete
				//Operation 3 :add

			}


		}
	}

	printChanges(LengthOfSecondString,LengthOfFirstString);//this function is a recursive function that print exactly the changes 
	cout<<"E"<<endl;//means finito (we have finished from changing string 1 to string 2)

	//cout<<EditDistance[LengthOfSecondString][LengthOfFirstString];
	cin>>FirstString>>SecondString;
	}




}

[Mans]

@5olio
it's a global forum ,don't be Local

@Mans
why you use this large size in the array?
int table[1000][1000];
char instruction[1000][1000];

and i also get wrong answer

: 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

Ia01Cw03Cs04Ca05E

[RehabReda]

: 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
the right answer:
Iw06Iw07E