164 - String Computer
Moderator: Board moderators
Misadventure
Well that was a bit messed up...Maxim wrote: I'm not total newbie to DP as I seem to be.

HELP ME .. WA 164......?
Code: Select all
#include <fstream.h>
#include <string.h>
char a[1000],b[1000];
int d[1000][1000],p[1000][1000],lena,lenb;
int x[1000], y[1000], cnt;
int delta;
void main()
{
int i,j, k = 0;
while(1){
cin >> a;
if(strcmp(a,"#")==0)break;
cin >> b;
// if (k == 1) cout << endl;
lena=strlen(a);
lenb=strlen(b);
for(i=1;i<=lenb;i++){
for(j=1;j<=lena;j++){
d[i][j]=0;
p[i][j]=0;
}
}
for(i=0;i<=lenb;i++){
d[i][0]=i;
p[i][0]=3;
}
for(i=0;i<=lena;i++){
d[0][i]=i;
p[0][i]=4;
}
for(i=1;i<=lenb;i++){
for(j=1;j<=lena;j++){
if(d[i][j]>=d[i-1][j]+1){
d[i][j]=d[i-1][j]+1;
p[i][j]=3;
}
//if(d[i][j]>=d[i][j-1]+1){
d[i][j]=d[i][j-1]+1;
p[i][j]=4;
//}
if(a[j-1]==b[i-1] && d[i][j] >= d[i-1][j-1]){
d[i][j]=d[i-1][j-1];
p[i][j]=1;
}
else if (d[i][j] >= d[i-1][j-1]+1){
d[i][j]=d[i-1][j-1]+1;
p[i][j]=2;
}
}
}
cout << d[lenb][lena] << endl;
delta = 0;
cnt = 0;
i = lenb;
j = lena;
while (i != 0 || j != 0) {
switch(p[i][j]) {
case 2: x[cnt] = j; y[cnt++] = i;
case 1: --i; --j; break;
case 3: x[cnt] = j; y[cnt++] = i; --i; break;
case 4: x[cnt] = j; y[cnt++] = i; --j; break;
}
}
for (i = cnt-1; i >= 0; i--) {
switch(p[y[i]][x[i]]){
case 2:
cout << "C" << b[y[i]-1];
if(x[i]+delta<10){
cout << "0" << x[i]+delta;
}
else{
cout << x[i]+delta;
}
break;
case 3:
cout << "I" << b[y[i]-1];
if(x[i]+1+delta<10){
cout << "0" << x[i]+1+delta++;
}
else{
cout << x[i]+1+delta++;
}
break;
case 4:
cout << "D" << a[x[i]-1];
if(x[i]+delta<10){
cout << "0" << x[i]+delta--;
}
else{
cout << x[i]+delta--;
}
break;
}
}
if(d[lenb][lena]!=0)cout << "E" << endl;
//if (k == 0) k++;
}
}
Help me...
164 HELP!! ME [WA]
Code: Select all
#include <fstream.h>
#include <string.h>
char a[1000],b[1000];
int d[1000][1000],p[1000][1000],lena,lenb;
int x[1000], y[1000], cnt;
int delta;
void main()
{
int i,j, k = 0;
while(1){
cin >> a;
if(strcmp(a,"#")==0)break;
cin >> b;
// if (k == 1) cout << endl;
lena=strlen(a);
lenb=strlen(b);
for(i=1;i<=lenb;i++){
for(j=1;j<=lena;j++){
d[i][j]=0;
p[i][j]=0;
}
}
for(i=0;i<=lenb;i++){
d[i][0]=i;
p[i][0]=3;
}
for(i=0;i<=lena;i++){
d[0][i]=i;
p[0][i]=4;
}
for(i=1;i<=lenb;i++){
for(j=1;j<=lena;j++){
if(d[i][j]>=d[i-1][j]+1){
d[i][j]=d[i-1][j]+1;
p[i][j]=3;
}
//if(d[i][j]>=d[i][j-1]+1){
d[i][j]=d[i][j-1]+1;
p[i][j]=4;
//}
if(a[j-1]==b[i-1] && d[i][j] >= d[i-1][j-1]){
d[i][j]=d[i-1][j-1];
p[i][j]=1;
}
else if (d[i][j] >= d[i-1][j-1]+1){
d[i][j]=d[i-1][j-1]+1;
p[i][j]=2;
}
}
}
cout << d[lenb][lena] << endl;
delta = 0;
cnt = 0;
i = lenb;
j = lena;
while (i != 0 || j != 0) {
switch(p[i][j]) {
case 2: x[cnt] = j; y[cnt++] = i;
case 1: --i; --j; break;
case 3: x[cnt] = j; y[cnt++] = i; --i; break;
case 4: x[cnt] = j; y[cnt++] = i; --j; break;
}
}
for (i = cnt-1; i >= 0; i--) {
switch(p[y[i]][x[i]]){
case 2:
cout << "C" << b[y[i]-1];
if(x[i]+delta<10){
cout << "0" << x[i]+delta;
}
else{
cout << x[i]+delta;
}
break;
case 3:
cout << "I" << b[y[i]-1];
if(x[i]+1+delta<10){
cout << "0" << x[i]+1+delta++;
}
else{
cout << x[i]+1+delta++;
}
break;
case 4:
cout << "D" << a[x[i]-1];
if(x[i]+delta<10){
cout << "0" << x[i]+delta--;
}
else{
cout << x[i]+delta--;
}
break;
}
}
if(d[lenb][lena]!=0)cout << "E" << endl;
//if (k == 0) k++;
}
}




HELP ME
164 Why WA!! Please Help me.. T_T Help me!!!!!!!!!!!!!!!!!!!
Code: Select all
#include <fstream.h>
#include <string.h>
char a[1000],b[1000];
int d[1000][1000],p[1000][1000],lena,lenb;
int x[1000], y[1000], cnt;
int delta;
void main()
{
int i,j, k = 0;
while(1){
cin >> a;
if(strcmp(a,"#")==0)break;
cin >> b;
// if (k == 1) cout << endl;
lena=strlen(a);
lenb=strlen(b);
for(i=1;i<=lenb;i++){
for(j=1;j<=lena;j++){
d[i][j]=0;
p[i][j]=0;
}
}
for(i=0;i<=lenb;i++){
d[i][0]=i;
p[i][0]=3;
}
for(i=0;i<=lena;i++){
d[0][i]=i;
p[0][i]=4;
}
for(i=1;i<=lenb;i++){
for(j=1;j<=lena;j++){
if(d[i][j]>=d[i-1][j]+1){
d[i][j]=d[i-1][j]+1;
p[i][j]=3;
}
//if(d[i][j]>=d[i][j-1]+1){
d[i][j]=d[i][j-1]+1;
p[i][j]=4;
//}
if(a[j-1]==b[i-1] && d[i][j] >= d[i-1][j-1]){
d[i][j]=d[i-1][j-1];
p[i][j]=1;
}
else if (d[i][j] >= d[i-1][j-1]+1){
d[i][j]=d[i-1][j-1]+1;
p[i][j]=2;
}
}
}
cout << d[lenb][lena] << endl;
delta = 0;
cnt = 0;
i = lenb;
j = lena;
while (i != 0 || j != 0) {
switch(p[i][j]) {
case 2: x[cnt] = j; y[cnt++] = i;
case 1: --i; --j; break;
case 3: x[cnt] = j; y[cnt++] = i; --i; break;
case 4: x[cnt] = j; y[cnt++] = i; --j; break;
}
}
for (i = cnt-1; i >= 0; i--) {
switch(p[y[i]][x[i]]){
case 2:
cout << "C" << b[y[i]-1];
if(x[i]+delta<10){
cout << "0" << x[i]+delta;
}
else{
cout << x[i]+delta;
}
break;
case 3:
cout << "I" << b[y[i]-1];
if(x[i]+1+delta<10){
cout << "0" << x[i]+1+delta++;
}
else{
cout << x[i]+1+delta++;
}
break;
case 4:
cout << "D" << a[x[i]-1];
if(x[i]+delta<10){
cout << "0" << x[i]+delta--;
}
else{
cout << x[i]+delta--;
}
break;
}
}
if(d[lenb][lena]!=0)cout << "E" << endl;
//if (k == 0) k++;
}
}
T_T










PLEASE HELP ME..
164 String Computer,WA
Can anybody say why I am getting WA?
I'm using Edit(Levenshtein) Distance method and then I'm tracing back using recursion. Maybe I've mistaken in taking array of positions. Every time when I'm deleting or inserting new character I'm changing elements in array "pos" (elements that are righter than position of deletion or insertion). Isn't that true?
Here is my code below.
I'm using Edit(Levenshtein) Distance method and then I'm tracing back using recursion. Maybe I've mistaken in taking array of positions. Every time when I'm deleting or inserting new character I'm changing elements in array "pos" (elements that are righter than position of deletion or insertion). Isn't that true?
Here is my code below.
Code: Select all
// 164 String Computer - Edit (Levenshtein) Distance - Dynamic Programming
#include <stdio.h>
#include <string.h>
// the maximum length of strings
#define MAX 22
int d[MAX][MAX],b[MAX][MAX],pos[MAX],r,c,k;
char s[MAX], t[MAX];
// tracing back using recursive function
void print(int i, int j){
if (i==0&&j==0) return;
if (b[i][j]==1){
print(i,j-1);
if (pos[i-1] < 10)
printf("I%c0%d",t[j-1],pos[i-1]+1);
else
printf("I%c%d",t[j-1],pos[i-1]+1);
for (k=i; k<r; k++) pos[k]++;
}
else if (b[i][j]==2){
print(i-1,j-1);
if (d[i][j]!=d[i-1][j-1])
if (pos[i-1] < 10)
printf("C%c0%d",t[j-1],pos[i-1]);
else
printf("C%c%d",t[j-1],pos[i-1]);
}
else
{
print(i-1,j);
if (pos[i-1] < 10)
printf("D%c0%d",s[i-1],pos[i-1]);
else
printf("D%c%d",s[i-1],pos[i-1]);
for (k=i; k<r; k++) pos[k]--;
}
}
// LevenshteinDistance function
int LevenshteinDistance(){
int cost,i,j;
r = strlen(s);
c = strlen(t);
for(i=0 ; i<=r ; i++){
d[i][0]=i;
b[i][0]=3;
}
for(j=1 ; j<=c ; j++){
d[0][j]=j;
b[0][j]=1;
}
for(i=1 ; i<=r ; i++)
for(j=1 ; j<=c ; j++)
{
cost = (s[i-1]==t[j-1]) ? 0 : 1;
if (d[i][j-1]<=d[i-1][j] && d[i][j-1]+1<=d[i-1][j-1]+cost){
d[i][j] = d[i][j-1]+1;
b[i][j] = 1;
} else if (d[i-1][j-1]+cost<=d[i-1][j]){
d[i][j] = d[i-1][j-1]+cost;
b[i][j] = 2;
}else
{
d[i][j] = d[i-1][j]+1;
b[i][j] = 3;
}
}
for (i=0; i<r; i++) pos[i]=i+1;
print(r, c);
printf("E\n");
return d[r][c];
}
void main()
{
char ln[MAX];
int i,j;
while (gets(ln), strcmp(ln, "#"))
{
i=0;
j=0;
while (ln[i] && ln[i] != ' ')
s[j++] = ln[i++];
s[j]='\0';
while (ln[i] && ln[i] == ' ')
i++;
j=0;
while (ln[i])
t[j++] = ln[i++];
t[j]='\0';
LevenshteinDistance();
}
}
Narek Saribekyan
Look Here!
I got accepted for problem 526 which is very familiar to this one. Anyway, I'm still getting WA for this problem. I fixed my mistakes in code above and wrote it just like problem 526(with some changes in output).
"yiuyuho" wrote
Anyway, I tried the trick with empty strings too, but that didn't help.
So I can't understand were I made a mistake (or there is something incorrect at the judge)
Is there anyone that can look at my code and help me?
"yiuyuho" wrote
I tried this too, but I'm still getting WA. I would like to know, is there anyone that haven't took care about empty strings and got AC?.This is strange:
I calculated the distance and back track:
I track for IDC and I got WA, but when I track in the order DIC I get AC, then I discover:
IDC, DCI, CID --> WA
DIC, ICD, CDI --> AC
The procedures of tracking is exactly identical, only the if-statements order is altered, how can that alter the outcome?
It there something wrong with the judge?
Anyway, I tried the trick with empty strings too, but that didn't help.
So I can't understand were I made a mistake (or there is something incorrect at the judge)
Is there anyone that can look at my code and help me?
Code: Select all
// 164 String Computer - Edit (Levenshtein) Distance - Dynamic Programming
#include <stdio.h>
#include <string.h>
// the maximum length of strings
#define MAX 22
#define min(a, b) (((a) < (b)) ? (a) : (b))
int d[MAX][MAX],b[MAX][MAX],pos[MAX],r,c,k;
char s[MAX], t[MAX];
// tracing back using recursive function
void print(int i, int j){
if (i==0&&j==0) return;
if (b[i][j]==1){
print(i,j-1);
if (pos[i-1] < 10)
printf("I%c0%d",t[j-1],pos[i]+1);
else
printf("I%c%d",t[j-1],pos[i]+1);
for (k=i; k<=r; k++) pos[k]++;
}
else if (b[i][j]==2){
print(i-1,j-1);
if (d[i][j]!=d[i-1][j-1])
if (pos[i-1] < 10)
printf("C%c0%d",t[j-1],pos[i]);
else
printf("C%c%d",t[j-1],pos[i]);
}
else
{
print(i-1,j);
if (pos[i-1] < 10)
printf("D%c0%d",s[i-1],pos[i]);
else
printf("D%c%d",s[i-1],pos[i]);
for (k=i; k<=r; k++) pos[k]--;
}
}
// LevenshteinDistance function
int LevenshteinDistance(){
int cost,i,j;
r = strlen(s);
c = strlen(t);
d[0][0]=0;
for(i=1 ; i<=r ; i++){
d[i][0]=i;
b[i][0]=3;
}
for(j=1 ; j<=c ; j++){
d[0][j]=j;
b[0][j]=1;
}
for(i=1 ; i<=r ; i++)
for(j=1 ; j<=c ; j++)
{
cost = (s[i-1]==t[j-1]) ? 0 : 1;
d[i][j] = min(d[i-1][j-1]+cost,min(d[i-1][j]+1,d[i][j-1]+1));
if (d[i][j]==d[i][j-1]+1)
b[i][j] = 1;
else if (d[i][j]==d[i-1][j-1]+cost)
b[i][j] = 2;
else
b[i][j] = 3;
}
for (i=0; i<=r; i++) pos[i]=i;
print(r, c);
printf("E\n");
return d[r][c];
}
void main()
{
while (scanf("%s",s) && strcmp(s,"#") && scanf("%s",t)) LevenshteinDistance();
}
Narek Saribekyan
164 i can't understand .. why WA
i'm getting WA....
i can't understand...
i try already IDC,ICD ...all of cases.. and i can't get AC..
what is wrong in my source...
is there any special case like blank line??
plz help me...
#include <iostream>
#include <string>
#include <vector>
#include <stdio.h>
using namespace std;
void main(){
int in, ta, i, j, cost, min;
string input, target, str;
int d[100][100], s[100][100];
vector < pair<int,int> > v;
getline(cin,str);
while(str.compare("#")!=0){
input = str.substr(0,str.find(' '));
target = str.substr(str.find(' ') + 1, str.length());
in = input.length();
ta = target.length();
v.clear();
if(in==0) for(i=0;i<ta;i++) printf("I%c%02d",target,i+1);
else if(ta==0) for(i=0;i<in;i++) printf("D%c%02d",input,1);
else{
for(i=0;i<=in;i++){d[0] = i;s[0]=1;}
for(i=1;i<=ta;i++){d[0] = i;s[0]=0;}
for(j=1;j<=in;j++){
for(i=1;i<=ta;i++){
if(input[j-1]==target[i-1]) cost = 0;
else cost = 1;
min = 999999;
if(min > d[j-1] + 1){
min = d[j-1] + 1;
s[j] = 1;
}
if(min > d[i-1][j] + 1){
min = d[i-1][j] + 1;
s[j] = 0;
}
if(min > d[i-1][j-1] + cost){
min = d[i-1][j-1] + cost;
s[i][j] = 2;
}
d[i][j] = min;
}
}
while(!(in==0 && ta==0)){
v.push_back(pair<int,int>(ta,in));
if(s[ta][in]==0) ta--;
else if(s[ta][in]==1) in--;
else if(s[ta][in]==2) {ta--;in--;}
}
v.push_back(pair<int,int>(0,0));
for(i=v.size()-1;i>0;i--){
if(d[v[i-1].first][v[i-1].second]!=d[v[i].first][v[i].second]){
if(s[v[i-1].first][v[i-1].second]==0){
printf("I%c%02d",target[v[i-1].first-1],v[i-1].first);
}
else if(s[v[i-1].first][v[i-1].second]==1){
printf("D%c%02d",input[v[i-1].second-1],v[i-1].second);
}
else{
printf("C%c%02d",target[v[i-1].first-1],v[i-1].first);
}
}
}
}
cout<<"E"<<endl;
getline(cin,str);
}
}
i can't understand...
i try already IDC,ICD ...all of cases.. and i can't get AC..
what is wrong in my source...
is there any special case like blank line??
plz help me...
#include <iostream>
#include <string>
#include <vector>
#include <stdio.h>
using namespace std;
void main(){
int in, ta, i, j, cost, min;
string input, target, str;
int d[100][100], s[100][100];
vector < pair<int,int> > v;
getline(cin,str);
while(str.compare("#")!=0){
input = str.substr(0,str.find(' '));
target = str.substr(str.find(' ') + 1, str.length());
in = input.length();
ta = target.length();
v.clear();
if(in==0) for(i=0;i<ta;i++) printf("I%c%02d",target,i+1);
else if(ta==0) for(i=0;i<in;i++) printf("D%c%02d",input,1);
else{
for(i=0;i<=in;i++){d[0] = i;s[0]=1;}
for(i=1;i<=ta;i++){d[0] = i;s[0]=0;}
for(j=1;j<=in;j++){
for(i=1;i<=ta;i++){
if(input[j-1]==target[i-1]) cost = 0;
else cost = 1;
min = 999999;
if(min > d[j-1] + 1){
min = d[j-1] + 1;
s[j] = 1;
}
if(min > d[i-1][j] + 1){
min = d[i-1][j] + 1;
s[j] = 0;
}
if(min > d[i-1][j-1] + cost){
min = d[i-1][j-1] + cost;
s[i][j] = 2;
}
d[i][j] = min;
}
}
while(!(in==0 && ta==0)){
v.push_back(pair<int,int>(ta,in));
if(s[ta][in]==0) ta--;
else if(s[ta][in]==1) in--;
else if(s[ta][in]==2) {ta--;in--;}
}
v.push_back(pair<int,int>(0,0));
for(i=v.size()-1;i>0;i--){
if(d[v[i-1].first][v[i-1].second]!=d[v[i].first][v[i].second]){
if(s[v[i-1].first][v[i-1].second]==0){
printf("I%c%02d",target[v[i-1].first-1],v[i-1].first);
}
else if(s[v[i-1].first][v[i-1].second]==1){
printf("D%c%02d",input[v[i-1].second-1],v[i-1].second);
}
else{
printf("C%c%02d",target[v[i-1].first-1],v[i-1].first);
}
}
}
}
cout<<"E"<<endl;
getline(cin,str);
}
}
Oders in problem 164(String Computer)
There was a topic about this problem that there is a wrong judge and it's possible to get WA in some cases. I tried to control orders (for example like DIC). That means, if you have more that one choice, you must first do Delete then Insert and finally Change, right?.
I'm not sure about doing all this, so I would like to know your opinion about my method.
So, what I'm doing?
I'm taking two 2-dimensional arrays("d and "b"). "d" for minimal distances and "b"-for tracing back(parent information).
b[j] == 1 <=> INSERT;
b[j] == 2 <=> CHANGE;
b[j] == 3 <=> DELETE;
I can change priority using this method. In the sample above I wrote orders for ICD. So, If I want to change it to DIC, I can wrote like this.
After that I'm tracing back using recursice function.
I tried all possible combinations, but that didn't help.
What do you think? Does this seem to be a correct solution?
I'm not sure about doing all this, so I would like to know your opinion about my method.
So, what I'm doing?
I'm taking two 2-dimensional arrays("d and "b"). "d" for minimal distances and "b"-for tracing back(parent information).
b[j] == 1 <=> INSERT;
b[j] == 2 <=> CHANGE;
b[j] == 3 <=> DELETE;
Code: Select all
for(i=1 ; i<=r ; i++)
for(j=1 ; j<=c ; j++)
{
cost = (s[i-1]==t[j-1]) ? 0 : 1;
d[i][j] = min(d[i-1][j-1]+cost,d[i-1][j]+1,d[i][j-1]+1);
if (d[i][j]==d[i][j-1]+1)// Insert
b[i][j] = 1;
else if (d[i][j]==d[i-1][j-1]+cost)// Change
b[i][j] = 2;
else// Delete
b[i][j] = 3;
}
Code: Select all
if (d[i][j]==d[i-1][j]+1)// Delete
b[i][j] = 3;
else if (d[i][j]==d[i][j-1]+1)// Insert
b[i][j] = 1;
else// Change
b[i][j] = 2;
Code: Select all
void print(int i, int j){
if (i==0&&j==0) return;
if (b[i][j]==1){
print(i,j-1);
if (pos[i-1] < 10)
printf("I%c0%d",t[j-1],pos[i]+1);
else
printf("I%c%d",t[j-1],pos[i]+1);
for (k=i; k<=r; k++) pos[k]++;
}
else if (b[i][j]==2){
print(i-1,j-1);
if (d[i][j]!=d[i-1][j-1])
if (pos[i-1] < 10)
printf("C%c0%d",t[j-1],pos[i]);
else
printf("C%c%d",t[j-1],pos[i]);
}
else
{
print(i-1,j);
if (pos[i-1] < 10)
printf("D%c0%d",s[i-1],pos[i]);
else
printf("D%c%d",s[i-1],pos[i]);
for (k=i; k<=r; k++) pos[k]--;
}
}
What do you think? Does this seem to be a correct solution?
Narek Saribekyan
Please Help me!! ACM164 WA!!!!!!!!!!!
Code: Select all
#include <fstream.h>
#include <string.h>
char a[1000],b[1000];
int d[1000][1000],p[1000][1000],lena,lenb;
int x[1000], y[1000], cnt;
int delta;
void main()
{
int i,j, k = 0;
while(1){
cin >> a;
if(strcmp(a,"#")==0)break;
cin >> b;
// if (k == 1) cout << endl;
lena=strlen(a);
lenb=strlen(b);
for(i=1;i<=lenb;i++){
for(j=1;j<=lena;j++){
d[i][j]=0;
p[i][j]=0;
}
}
for(i=0;i<=lenb;i++){
d[i][0]=i;
p[i][0]=3;
}
for(i=0;i<=lena;i++){
d[0][i]=i;
p[0][i]=4;
}
for(i=1;i<=lenb;i++){
for(j=1;j<=lena;j++){
if(d[i][j]>=d[i-1][j]+1){
d[i][j]=d[i-1][j]+1;
p[i][j]=3;
}
//if(d[i][j]>=d[i][j-1]+1){
d[i][j]=d[i][j-1]+1;
p[i][j]=4;
//}
if(a[j-1]==b[i-1] && d[i][j] >= d[i-1][j-1]){
d[i][j]=d[i-1][j-1];
p[i][j]=1;
}
else if (d[i][j] >= d[i-1][j-1]+1){
d[i][j]=d[i-1][j-1]+1;
p[i][j]=2;
}
}
}
cout << d[lenb][lena] << endl;
delta = 0;
cnt = 0;
i = lenb;
j = lena;
while (i != 0 || j != 0) {
switch(p[i][j]) {
case 2: x[cnt] = j; y[cnt++] = i;
case 1: --i; --j; break;
case 3: x[cnt] = j; y[cnt++] = i; --i; break;
case 4: x[cnt] = j; y[cnt++] = i; --j; break;
}
}
for (i = cnt-1; i >= 0; i--) {
switch(p[y[i]][x[i]]){
case 2:
cout << "C" << b[y[i]-1];
if(x[i]+delta<10){
cout << "0" << x[i]+delta;
}
else{
cout << x[i]+delta;
}
break;
case 3:
cout << "I" << b[y[i]-1];
if(x[i]+1+delta<10){
cout << "0" << x[i]+1+delta++;
}
else{
cout << x[i]+1+delta++;
}
break;
case 4:
cout << "D" << a[x[i]-1];
if(x[i]+delta<10){
cout << "0" << x[i]+delta--;
}
else{
cout << x[i]+delta--;
}
break;
}
}
if(d[lenb][lena]!=0)cout << "E" << endl;
//if (k == 0) k++;
}
}



164 - WA
Hello,
I have watched the whole forum for help to solve this problem. I have fixed my code many times but that didn't help - I'm getting WA again and again.
Anybody? I need help.
Note that I have solved the problem 526 and my problem is (OJ's problem) which one of solutions to print out when there is more than one solutions.
And please, do not link me to another topic - I have travelled trought all topics in this forum. Just take a moment to look at my code, please.
I think you'll understand it momentary if you have solved this problem.
Thanks in advance
I have watched the whole forum for help to solve this problem. I have fixed my code many times but that didn't help - I'm getting WA again and again.

Note that I have solved the problem 526 and my problem is (OJ's problem) which one of solutions to print out when there is more than one solutions.
And please, do not link me to another topic - I have travelled trought all topics in this forum. Just take a moment to look at my code, please.
I think you'll understand it momentary if you have solved this problem.
Code: Select all
// 164 String Computer - Edit (Levenshtein) Distance - Dynamic Programming
#include <stdio.h>
#include <string.h>
// the maximum length of strings
#define MAX 22
#define min(a, b) (((a) < (b)) ? (a) : (b))
int d[MAX][MAX],b[MAX][MAX],pos[MAX],r,c,k;
char s[MAX], t[MAX];
// tracing back using recursive function
void print(int i, int j){
if (i==0&&j==0) return;
if (b[i][j]==1){
print(i,j-1);
if (pos[i-1] < 10)
printf("I%c0%d",t[j-1],pos[i]+1);
else
printf("I%c%d",t[j-1],pos[i]+1);
for (k=i; k<=r; k++) pos[k]++;
}
else if (b[i][j]==2){
print(i-1,j-1);
if (d[i][j]!=d[i-1][j-1])
if (pos[i-1] < 10)
printf("C%c0%d",t[j-1],pos[i]);
else
printf("C%c%d",t[j-1],pos[i]);
}
else
{
print(i-1,j);
if (pos[i-1] < 10)
printf("D%c0%d",s[i-1],pos[i]);
else
printf("D%c%d",s[i-1],pos[i]);
for (k=i; k<=r; k++) pos[k]--;
}
}
// LevenshteinDistance function
int LevenshteinDistance(){
int cost,i,j;
r = strlen(s);
c = strlen(t);
d[0][0]=0;
for(i=1 ; i<=r ; i++){
d[i][0]=i;
b[i][0]=3;
}
for(j=1 ; j<=c ; j++){
d[0][j]=j;
b[0][j]=1;
}
for(i=1 ; i<=r ; i++)
for(j=1 ; j<=c ; j++)
{
cost = (s[i-1]==t[j-1]) ? 0 : 1;
d[i][j] = min(d[i-1][j-1]+cost,min(d[i-1][j]+1,d[i][j-1]+1));
if (d[i][j]==d[i][j-1]+1)
b[i][j] = 1;
else if (d[i][j]==d[i-1][j-1]+cost)
b[i][j] = 2;
else
b[i][j] = 3;
}
for (i=0; i<=r; i++) pos[i]=i;
print(r, c);
printf("E\n");
return d[r][c];
}
void main()
{
while (scanf("%s",s) && strcmp(s,"#") && scanf("%s",t)) LevenshteinDistance();
}
Narek Saribekyan
-
- New poster
- Posts: 44
- Joined: Tue Jun 06, 2006 6:44 pm
- Location: Nova Scotia, Canada
- Contact:
164 WA
I have tested my solution with many inputs, and cannot find a problem. Although my outputs are very different from most of the ones I found, they all contained the correct Levenstien Distance # of commands, and when I went through those commands, they all turned x into y.
Here is my source code:
P.S:
I got the levenstien distance algo from wiki, and adapted it to give the commands, I understand it well -- accept for this code:
can anyone explain this?
Here is my source code:
Code: Select all
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
string makeindex ( int n )
{
return string("") + (char)('0' + (n/10)) + string("")+
(char)('0' + (n%10));
}
int main ( void )
{
string x, y;
while ((cin >> x >> y) && x[0] != '#')
{
int i, j;
x = string(" ") + x;
y = string(" ") + y;
int D[22][22] = { 0 };
int DS[22][22] = { 0 };
int a = x.length(), b = y.length();
for (i=0; i<=a; i++)
D[i][0] = i;
for (i=0; i<=b; i++)
D[0][i] = i;
for (i=1; i<=a; i++)
for (j=1; j<=b; j++)
{
int cost = (x[i-1] == y[j-1]) ? 0 : 1;
int cC = D[i-1][j-1] + cost;
int cI = D[i][j-1] + 1;
int cD = D[i-1][j] + 1;
int m = min(min(cC, cI), cD);
D[i][j] = m;
if (m == cI)
DS[i][j] = (2+(i<<8)+((j-1)<<16));
else if (m == cC)
DS[i][j] = (1+((i-1)<<8)+((j-1)<<16));
else if (m == cD)
DS[i][j] = (3+((i-1)<<8)+(j<<16));
}
i = a; j = b;
while (DS[i][j])
{
int xx = DS[i][j];
int cmd = xx&0xff;
int ni = (xx>>8)&0xff;
int nj = xx>>16;
if (x[ni] != y[nj])
{
if (cmd == 1)
cout << "C" << y[nj] << makeindex(ni);
else if (cmd == 2)
cout << "I" << y[nj] << makeindex(ni);
else if (cmd == 3)
cout << "D" << x[ni] << makeindex(ni);
}
i = ni; j = nj;
}
cout << "E" << endl;
}
return 0;
}
I got the levenstien distance algo from wiki, and adapted it to give the commands, I understand it well -- accept for this code:
Code: Select all
for (i=0; i<=a; i++)
D[i][0] = i;
for (i=0; i<=b; i++)
D[0][i] = i;
- Chris Adams
-
- New poster
- Posts: 44
- Joined: Tue Jun 06, 2006 6:44 pm
- Location: Nova Scotia, Canada
- Contact:
AC by adding 9 characters of code too my solution.
I found my error after writing this small program to check output:
I found my error after writing this small program to check output:
Code: Select all
#include <iostream>
#include <string>
using namespace std;
int main ( void )
{
string x, y, cmd;
while (cin >> x >> y >> cmd)
{
int len = (cmd.length()-1)/4;
int i;
for (i=0; i<(len*4); i+=4)
{
char c = cmd[i];
char l = cmd[i+1];
int in = (cmd[i+2]-'0')*10 + (cmd[i+3]-'0');
if (c == 'C')
x[in-1] = l;
else if (c == 'I')
x.insert(in-1, string("")+l);
else if (c == 'D')
x.erase(in-1, 1);
}
if (x != y) cout << "*";
cout << x << " " << y << endl;
}
}
- Chris Adams