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

Abednego
A great helper
Posts: 281
Joined: Tue Sep 10, 2002 5:14 am
Location: Mountain View, CA, USA
Contact:

Post by Abednego »

Your solution takes C*n^3 time, where C is a very large constant. Instead of working with a matrix of strings, try to convert it to a matrix of integers and then rebuild the string at the very end. Then you will have an n^2 algorithm.
If only I had as much free time as I did in college...

tRipper
New poster
Posts: 22
Joined: Sun Mar 13, 2005 5:04 pm
Location: out there

Post by tRipper »

Thank you very much..
I completley forgot that comparation and concetation of strings don't take O(1) time.
A stupid mistake.
If I am out of my mind, it's all right with me.

worm3959
New poster
Posts: 4
Joined: Tue Nov 29, 2005 5:49 am
Contact:

Misadventure

Post by worm3959 »

Maxim wrote: I'm not total newbie to DP as I seem to be.
Well that was a bit messed up... 8)8)

sds1100
Learning poster
Posts: 95
Joined: Sat Dec 10, 2005 2:09 pm

HELP ME .. WA 164......?

Post by sds1100 »

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++; 
   } 
} 
I got Ac 526
Help me...

chunyi81
A great helper
Posts: 293
Joined: Sat Jun 21, 2003 4:19 am
Location: Singapore

Post by chunyi81 »


sds1100
Learning poster
Posts: 95
Joined: Sat Dec 10, 2005 2:09 pm

164 HELP!! ME [WA]

Post by sds1100 »

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++; 
   } 
} 
WHY WA :cry: :cry: :cry: :cry:
HELP ME

sds1100
Learning poster
Posts: 95
Joined: Sat Dec 10, 2005 2:09 pm

164 Why WA!! Please Help me.. T_T Help me!!!!!!!!!!!!!!!!!!!

Post by sds1100 »

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++; 
   } 
} 
why WA!!
T_T
:cry: :cry: :cry: :cry: :cry: :cry: :cry: :cry: :cry: :cry:
PLEASE HELP ME..

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

164 String Computer,WA

Post by snar »

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.

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

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

Look Here!

Post by snar »

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
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?
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?.

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

yolongyi
New poster
Posts: 5
Joined: Mon Jan 16, 2006 9:19 pm
Location: Korea

164 i can't understand .. why WA

Post by yolongyi »

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);
}
}

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

Oders in problem 164(String Computer)

Post by snar »

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;

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;
		}
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.

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;
After that I'm tracing back using recursice function.

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]--;
	}	
}
I tried all possible combinations, but that didn't help.
What do you think? Does this seem to be a correct solution?
Narek Saribekyan

sds1100
Learning poster
Posts: 95
Joined: Sat Dec 10, 2005 2:09 pm

Please Help me!! ACM164 WA!!!!!!!!!!!

Post by sds1100 »

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!! :cry: :cry: :cry:

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

164 - WA

Post by snar »

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.

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();		
}
Thanks in advance
Narek Saribekyan

LithiumDex
New poster
Posts: 44
Joined: Tue Jun 06, 2006 6:44 pm
Location: Nova Scotia, Canada
Contact:

164 WA

Post by LithiumDex »

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:

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;
}
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:

Code: Select all

for (i=0; i<=a; i++)
            D[i][0] = i;
        for (i=0; i<=b; i++)
            D[0][i] = i; 
can anyone explain this?
- Chris Adams

LithiumDex
New poster
Posts: 44
Joined: Tue Jun 06, 2006 6:44 pm
Location: Nova Scotia, Canada
Contact:

Post by LithiumDex »

AC by adding 9 characters of code too my solution.

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

Post Reply

Return to “Volume 1 (100-199)”