164 - String Computer
Moderator: Board moderators
-
- Learning poster
- Posts: 71
- Joined: Thu Aug 21, 2003 1:56 am
-
- Learning poster
- Posts: 71
- Joined: Thu Aug 21, 2003 1:56 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
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
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.
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
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.
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....
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.

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.

-
- Learning poster
- Posts: 99
- Joined: Sun Apr 06, 2003 5:53 am
- Location: Dhaka, Bangladesh
- 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
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.

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

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.
Where's the "Any" key?
-
- 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. :-/
thanks in advance for your help.
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.
-
- Learning poster
- Posts: 76
- Joined: Thu Mar 13, 2003 5:12 am
- Location: Russia
-
- 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.
-
- Learning poster
- Posts: 76
- Joined: Thu Mar 13, 2003 5:12 am
- Location: Russia
-
- Experienced poster
- Posts: 151
- Joined: Tue Nov 16, 2004 7:23 pm
- Location: Norway
- Contact: