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

snar
New poster
Posts: 44
Joined: Thu Sep 01, 2005 12:14 pm
Location: Yerevan, Armenia

164 Fixed or not?

Post by 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,
Narek Saribekyan

Igor9669
Learning poster
Posts: 85
Joined: Sun Jun 08, 2008 12:58 pm

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

Post by 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!!!
Last edited by Igor9669 on Fri Nov 14, 2008 4:58 pm, edited 2 times in total.

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

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

Post by 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
Learning poster
Posts: 85
Joined: Sun Jun 08, 2008 12:58 pm

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

Post by Igor9669 »

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

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

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

Post by 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
Learning poster
Posts: 85
Joined: Sun Jun 08, 2008 12:58 pm

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

Post by 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
New poster
Posts: 1
Joined: Fri Feb 13, 2009 4:47 pm

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

Post by 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
New poster
Posts: 26
Joined: Fri Jan 02, 2009 12:41 am

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

Post by 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
New poster
Posts: 3
Joined: Tue Jul 21, 2009 1:02 am

Re: 164 WA

Post by hotwxn711 »

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

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

164-string computer

Post by 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
New poster
Posts: 4
Joined: Wed Dec 02, 2009 6:21 am

problem 164 .. why WA !! ???

Post by 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
New poster
Posts: 4
Joined: Wed Jun 18, 2008 1:23 pm

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

Post by 5olio »

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

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

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

Post by 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 :D :D
this is my code :D :D

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
New poster
Posts: 4
Joined: Wed Dec 02, 2009 6:21 am

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

Post by Mans »

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

RehabReda wrote:@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 :D
: 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
New poster
Posts: 5
Joined: Thu Dec 03, 2009 8:25 pm

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

Post by 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 :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

Post Reply

Return to “Volume 1 (100-199)”