#164 I think there is a bug in your tests!!!

[Igor9669]

In all my tests my program gives a correct answers? I don't know why WA???

test:
abcde bcgfe
a accdd
accdd a
abcxdefxghix abcyydefyyghiyy
ddppqq dapaqaaa
aab aab
(space)dddd
dddd(space)

abcdefghijklxyztpr pacdfeoomnrdffrr
#

answer:
Da01Cg03If04E
Ic02Ic03Id04Id05E
Dc02Dc02Dd02Dd02E
Cy04Iy05Cy09Iy10Cy14Iy15E
Ca02Ca04Ca06Ia07Ia08E
E
Id01Id02Id03Id04E
Dd01Dd01Dd01Dd01E
E
Ip01Db03De05Ce06Co07Co08Cm09Cn10Cr11Cd12Cf13Cf14Cr15Dp16E


please check them!!!

[mf]

First of all, you forgot to mention which problem you're trying to solve. (Though I guess it's one of the find-smallest-edit-script problems)

It's far more likely that *your* program has a bug, than judge's tests. Thousands of people have already solved it, do you think they've all got it wrong?

[Igor9669]

this is a problem #164!!!
Are my answers correct???

[mf]

My accepted program's output is the same for all your tests except the last one. And the length of the output for the last one is the same, so that means it's probably also okay.

[Igor9669]

I had changed the priority from DELETE->INSERT->MATCH to MATCH->INSERT->DELETE and got Accepted!
I think it is very very strange.......

[behyyyy]

hi
can you explain about alghoritm of (164-string computer) program ?
why do you use 2 dimination arrays(b[i][j]-d[i][j])?
tanks for your help...
please tell me because very i need...

[alirezanoori]

Of course the problem is wrong! It says "Any solution that satisfies these criteria will be accepted" but its really obvious that it doesn't. I think instead of checking the answer with a program, the judge test your answer with a pre-defined answer that has this priority MATCH-INSERT-DELETE!

[aia]

plz could anyone help me to know the bug in my code in this Problem
this is my code :

Code: Select all

#include<iostream>
#include<vector>
#include<string>
//#include<fstream>
#include<math.h>
using namespace std ;
//fstream fin ("IN.txt");
//fstream fout("Out.txt");
string str1 , str2;
int Table[100][100];
int i , j ;
int minimum(int x ,int y,int  z)
{
   int result ;
   result = min(x , y);
   result= min(result , z);
   return result;
}

string convert(int num)
{
   string number="" ;
   int tempnum =num ;
   int i=0 ;
   while(num!=0)
   {
      if(num>=1 && num<=9)
         number+=num+'0' ;
      else
         number+=(num%10)+'0' ;
      num/=10 ;
      i++;
   }
   string temp = number ;
   if(tempnum>=1 &&tempnum<=9)
   {
      number = "0"+temp;
   }
   else
   {
      for(int j=0 ;j<number.length() ; j++)
         number[j] = temp[temp.length()-1-j];
   }
   return number ;
}

int EditDistance(string dist , string source)
{
   for ( i=0 ; i<=dist.length() ; i++)
      Table[i][0] = i ;// deletion
   for (j=0 ; j<=source.length() ; j++)
      Table[0][j] = j; // insertion
   for (j= 1 ;j<=source.length() ; j++)
   {
      for ( i=1 ; i<=dist.length() ; i++)
      {
         if( dist[i-1] == source[j-1])
            Table[i][j] = Table[i-1][ j-1];
         else
         {
            Table[i][j]= minimum
               (
               Table[i-1][j] + 1,  // deletion
               Table[i][j-1] + 1,  // insertion
               Table[i-1][j-1] + 1 // substitution
               );
         }
      }
   }

   return Table[dist.length()][source.length()];
}


string BackTracke(int x , int y)
{
   string temp ;
   string number;
   if(x==str1.length()+1&&y==str2.length()+1)
   {
      return BackTracke(x-1 , y-1)+"E";
   }
   if(x>0&&y==0)
   {
      number = convert(x);
      temp="D" ;
      temp.append(1 , str1[x-1]);
      temp+=number ;
      return BackTracke(x-1 , y)+temp;
   }
   else if(x==0 &&y>0)
   {
      number = convert(y);
      temp="I" ;
      temp.append(1 , str2[y-1]);
      temp+=number ;
      return BackTracke(x , y-1)+temp;
   }
   else if(x==0 &&y>0)
   {
      number = convert(y);
      temp="D" ;
      temp.append(1 , str2[y-1]);
      temp+=number ;
      return BackTracke(x , y-1)+temp;
   }
   else if(x==0 ||y==0)
      return"";
   else if(str1[x-1]==str2[y-1])
      return BackTracke(x-1 , y-1);
   else
   {
      if(Table[x][y]==Table[x-1][y] + 1)//delete
      {
         number = convert(y+1);
         temp="D" ;
         temp.append(1 , str1[x-1]);
         temp+=number ;
         return BackTracke(x-1 , y)+temp;
      }
      else if(Table[x][y]==Table[x][y-1]+1)//insertion
      {
         number = convert(y);
         temp="I" ;
         temp.append(1 , str2[y-1]);
         temp+=number ;
         return BackTracke(x, y-1)+temp;
      }
      else if(Table[x][y]==Table[x-1][y-1]+1) //change Table[x-1][y-1] + 1
      {
         number = convert(y);
         temp="C" ;
         temp.append(1 , str2[y-1]);
         temp+=number ;
         return BackTracke(x-1 , y-1)+temp;
      }
      
      
   }
}
int main()
{
   int s ;
   while(cin>>str1)
   {
      if(str1=="#")
         break;
      cin>>str2;
      s= EditDistance(str1, str2);
      string n = BackTracke(str1.length()+1, str2.length()+1);
      cout<<n<<endl;
   }
   return 0 ;
}

Thanks in advance