## 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

howardcheng
Learning poster
Posts: 71
Joined: Thu Aug 21, 2003 1:56 am
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
Learning poster
Posts: 71
Joined: Thu Aug 21, 2003 1:56 am
Never mind. I managed to get my program accepted by fooling around with the tie-breaking conditions as others have noted.

jackie
New poster
Posts: 47
Joined: Tue May 04, 2004 4:24 am
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
New poster
Posts: 47
Joined: Tue May 04, 2004 4:24 am
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
New poster
Posts: 47
Joined: Tue May 04, 2004 4:24 am
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
Experienced poster
Posts: 112
Joined: Tue Nov 12, 2002 11:15 pm
Location: Paris, France.
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.
We never perform a computation ourselves, we just hitch a ride on the great Computation that is going on already. --Tomasso Toffoli

Cosmin.ro
Learning poster
Posts: 95
Joined: Thu Aug 21, 2003 12:02 am
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
Learning poster
Posts: 88
Joined: Sun Oct 13, 2002 6:11 am

### Stupid judge

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.
__nOi.m....

yiuyuho
A great helper
Posts: 325
Joined: Thu Feb 21, 2002 2:00 am
Location: United States
Contact:
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
Learning poster
Posts: 99
Joined: Sun Apr 06, 2003 5:53 am
Contact:
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

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.
Where's the "Any" key?

Experimenter
Learning poster
Posts: 76
Joined: Thu Mar 13, 2003 5:12 am
Location: Russia

### 164

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];
}
``````
it would be great if you replied this post. really.

Experimenter
Learning poster
Posts: 76
Joined: Thu Mar 13, 2003 5:12 am
Location: Russia
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!
it would be great if you replied this post. really.

Experimenter
Learning poster
Posts: 76
Joined: Thu Mar 13, 2003 5:12 am
Location: Russia
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;
}
``````
Last edited by Experimenter on Fri Dec 24, 2004 7:08 pm, edited 1 time in total.
it would be great if you replied this post. really.

Experimenter
Learning poster
Posts: 76
Joined: Thu Mar 13, 2003 5:12 am
Location: Russia
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.
it would be great if you replied this post. really.

stubbscroll
Experienced poster
Posts: 151
Joined: Tue Nov 16, 2004 7:23 pm
Location: Norway
Contact:
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.