164 - String Computer

[howardcheng]

What is the trick here? I used DP and trace the solution but I get WA all the time. I did the operations from the end of the string (so insert and delete don't mess up the indices).

[howardcheng]

Never mind. I managed to get my program accepted by fooling around with the tie-breaking conditions as others have noted.

[jackie]

After many many WA, i got AC.

I use DP algorithm .
Firstly compute the minimal operations that must be done, then traceback to find the way.

i don't understand why this leads to AC.
[cpp]case 3:
printf("D%c%02d", d1[i-1], offset + i);
traceBack(i - 1, j);
--offset;
break;[/cpp]
this leads to infinite WA

[cpp]case 3:
traceBack(i - 1, j);
printf("D%c%02d", d1[i-1], offset + i);

--offset;
break;[/cpp]

and other operations are

[cpp] case 1:
traceBack(i - 1, j - 1);
if (d1[i-1] != d2[j-1])
printf("C%c%02d", d2[j-1], offset + i);
break;
case 2://insert
traceBack(i,j-1);
printf("I%c%02d", d2[j-1], offset + i + 1);
++offset;
break;[/cpp]

obviously, they have the same number of operations

i code a sample programe to simulate the "String Computer"'s operation.

they all turn the first string into the second.

strange for me, anyone who know the answer, plz send me the answer via private message or mail to: jackie@hit.edu.cn

thks

[jackie]

BTW

i think there isn't empty strings in the input file.

after use many assert,

i only use while (scanf("%s %s", d1, d2) == 2)
for the input.

hope it can help

[jackie]

i use the same code(only modified for output) to do 526 and got AC

the two sequence listed above both got AC.

maybe the special judge program used in 164 has some falut or there is some constraint for the problem to which i don't pay attention.

if you got any idea, plz contact me

thks

[epsilon0]

hello,

i solved this problem a long time ago. someone suggested your string should not exceed the maximum length (20 i think) at any moment. this might be true. some other people talked about the judge only accepting backtracking in a certain order (DCI or whatever). i dont think so. maybe their backtracking order affected the solution, or the maximum length.

[Cosmin.ro]

the judge of the problem is wrong it accepts only certain orders ... if you are sure your sol is ok, you should try every order and see wich one gets acc.

[Noim]

It is very annoying about the behavior of the judge for this problem 164.
i got many WA and after that i have to read the board to do The backtracking as C-D-I and got ACC. isn't it silly? i just change some if-else statement's order.

and also C-D-I is ordered when i backtrack , it is not actually the first answer in sorting list ordered as C-D-I order.

and also , is there anything about not to be length of the string more than 20 of the indermediate string in the problem statement? any way i AC code also outputs the position more the 20 for certain input i made.

So, there must have error in the judge and judge should re-code.

[yiuyuho]

hey peeps,

I think I know why the judge only AC certain orders now:
you must ensure i>0 to track (i-1,j)
j>0 before track (i,j-1)
and (i>0 && j>0) before track (i-1,j-1)

if you didn't check.....then chances are some index off bounce (in certain order) did not cause correctness error, and thus AC is some order.

[Solaris]

I was also receiving WA in this problem. But atlast got it right. I dont think the reason was the sequence of operations. After gettin AC I submitted my code with all possible configurations of C, I, D ; all got accepted.

My problem was in the printing part. Recursive call is not required for this problem. What I mean is this

instead of

Cd01Cf02E

you can also right

Cf02Cd01E

If you move from the right there is a great advantage. The changes made due to insertion and deletion does not affect indices of the left positions

Hope this will help those who are still having problem.

[Experimenter]

hi, guys!
could you look at the code and tell me why I get WA?
it appears to be pretty simple, but still.
I used my countryman's Levenshtein algorithm for finding distance between words. I don't know where I could make a mistake. :-/

Code: Select all

#include <string>
#include <iostream>
#include <vector>
#define  min2(a,b)  (a) < (b) ? (a) : (b)
#define  min3(a,b,c) min2(a,min2(b,c))

using namespace std;
vector <int > Distance(0);
const int MAX_SIZE = 30;
int d[MAX_SIZE][MAX_SIZE];

int LevenshteinDistance(const string&s,const string& t);
int main()
{
	string s,t;
	while(true){
		cin>>s;
		if(s=="#") break;
		cin>>t;
		Distance.push_back(LevenshteinDistance(s,t)+1);
	}
	for(int k=0;k < Distance.size(); k+= 1)
		cout<<Distance[k]<<endl;
	return 0;
}
int LevenshteinDistance(const string&s,const string& t)
{
	int ls,lt,i,j,cost;		
	ls = s.length(), lt = t.length();
	for(i=0;i <= ls;i++) d[i][0] = i;
	for(j=0;j <= lt;j++) d[0][j] = j;
	for(i=1;i <= ls;i++)
	{
		for(j=1;j <= lt; j++)
		{
			cost = (s[i] != t[j]); 
			d[i][j] = min3(d[i-1][j  ] + 1,		// erase ith symbol and get i-1->j
						   d[i  ][j-1] + 1,		// get from i->j-1 and insert jth
						   d[i-1][j-1] + cost);	// i-1->j-1 and change ith to jth if necessecary 
		}
	}
	return d[ls][lt];
}

thanks in advance for your help.

[Experimenter]

that's cheating!i have a version of this problem demanding only the number and all of a sudden it asks for the commands too!

[Experimenter]

guys, could you please help me with this WA I keep on getting. are there any tricks?

Code: Select all

#include <string>
#include <iostream>
#include <vector>
#include <stdio.h>

#define  min2(a,b)  ((a) < (b) ? (a) : (b))
#define  min3(a,b,c) min2(a,min2(b,c))

using namespace std;
vector <string > Commands(0);
vector <string > commands;

string instr; 
const int MAX_SIZE = 25;
int  d  [MAX_SIZE][MAX_SIZE];
char buf[MAX_SIZE];
int ls,lt,i,j,cost,D,k;		

const string& LevenshteinDistance(const string&s,const string& t);
int main()
{
	
	string s,t;
	commands.reserve(30);
	instr.reserve(4*20);
	while(true){
		cin>>s;
		if(s=="#") break;
		cin>>t;
		Commands.push_back(LevenshteinDistance(s,t));
	}

	for(k=0;k < Commands.size(); k+= 1)
		cout<<Commands[k]<<endl;
	return 0;
}

const string& LevenshteinDistance(const string&s,const string& t)
{
	ls = s.length(), lt = t.length();
	for(i=0;i <= ls;i++) d[i][0] = i;
	for(j=0;j <= lt;j++) d[0][j] = j;
	for(i=1;i <= ls;i++)
	{
		for(j=1;j <= lt; j++)
		{
			cost = (s[i-1] != t[j-1]); 
			d[i][j] = min3(d[i-1][j  ] + 1,		// erase ith symbol and get i-1->j
						   d[i  ][j-1] + 1,		// get from i->j-1 and insert jth
						   d[i-1][j-1] + cost);	// i-1->j-1 and change ith to jth if necessecary 
		}
	}
	i = ls, j = lt;
	commands.clear();
	
	// backtracking
	while(i>0 && j>0){
		if(d[i-1][j] + 1== d[i][j]){
			sprintf(buf,"D%c%02d",s[i-1],j+1);
			i--;
		}
		else if(d[i][j-1]+1 == d[i][j]){
			sprintf(buf,"I%c%02d",t[j-1],j);
			j--;
		}
		else {
			if(s[--i] != t[--j])sprintf(buf,"C%c%02d",t[j],j+1);
			else				continue;
		}
		commands.push_back(string(buf));
	}
	while(i>0){
		sprintf(buf,"D%c%02d",s[--i],1);
		commands.push_back(string(buf));
	}
	while(j>0){
		sprintf(buf,"I%c%02d",t[j-1],j);
		commands.push_back(string(buf));
		j--;
	}
	instr = "";
	for(k = commands.size()-1;k >= 0;k--)
		instr += commands[k];
	instr += 'E';
	return instr;
}

[Experimenter]

guys, I really don't understand why it takes ages for people to reply. is there any secret?
I can see couple of dozens of people have looked at this post and it turns out nobody has anything to say.why is that? I cannot understand it. really.

[stubbscroll]

Maybe none of the readers were able to help. Who knows.

The best tip I can give (without testing the code) is to test the output. Try to convert the first string to the second one with the output. It's easy to mess up the indices on this problem.