526 - String Distance and Transform Process

[brianfry713]

http://uva.onlinejudge.org/index.php?op ... category=7
You can see a yellow check next to 526, that means there is a special judge, and there are multiple correct outputs.

Your output is correct for sample input #2.

[mostafiz93]

empty string will be given as input.
i got AC after handling it.

[@ce]

Getting WA...plzzz help

Code: Select all

#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<string>
#include<iostream>
#include<algorithm>
#include<vector>
#include<stack>
#include<deque>
#include<queue>
#include<map>
using namespace std;

typedef long long int L;
typedef unsigned long long int U;

int arr[85][85];
char op[85][85];
stack < pair<int,char> >st;
main()
{
      char str1[85], str2[85];
      int first = 1;
      while(gets(str1))
      {
            gets(str2);
            for(int i = 0;i<=strlen(str1);i++)
            {
                  arr[0][i] = i;
                  op[0][i] = 'd';
            }
            for(int i = 0;i<=strlen(str2);i++)
            {
                  arr[i][0] = i;
                  op[i][0] = 'i';
            }
            for(int i = 1;i<=strlen(str2);i++)
            {
                  for(int j = 1;j<=strlen(str1);j++)
                  {
                        arr[i][j] = arr[i-1][j]+1;
                        op[i][j] = 'i';
                        if(arr[i][j-1]+1 < arr[i][j])
                        {
                              arr[i][j] = arr[i][j-1]+1;
                              op[i][j] = 'd';
                        }
                        if(arr[i-1][j-1] + (str2[i-1]!=str1[j-1]) < arr[i][j])
                        {
                              arr[i][j] = arr[i-1][j-1] + (str2[i-1]!=str1[j-1]);
                              op[i][j] = 'r';
                        }
                        //cout<<arr[i][j]<<op[i][j]<<" ";
                  }
                  //cout<<endl;
            }
            if(first)
            	first = 0;
            else
            	printf("\n");
            int x = strlen(str2);
            int y = strlen(str1);
            cout<<arr[x][y]<<endl;;
            int c = 1;
            while(arr[x][y])
            {
                  int val = arr[x][y];
                  char oper = op[x][y];
                  if(op[x][y] == 'r')
                  {
                        x--;
                        y--;
                  }
                  else if(op[x][y] == 'i')
                        x--;
                  else
                        y--;
                  if(val > arr[x][y])
                  {
                        if(oper == 'i')
                        	  printf("%d Insert %d,%c\n",c++,min(x+2,y+1),str2[x]);
            			else if(oper == 'd')
                              printf("%d Delete %d\n", c++, y+1);
                        else
                              printf("%d Replace %d,%c\n",c++,y+1, str2[x]);
                  }
            }
      }
}

[brianfry713]

Try input:

Code: Select all

iltvqzunxiumwacpdlwelrufcgsjnioxwhsmiobgxvutxwiahgevzaacgu
vfdsdlmrvbsbanvtmtdmblswmvyqbvdzchrfugwphothdqcpkhdnuvlgslx

Your code is generating this string:

Code: Select all

vfdsdlmrvbsbanvtmtdmblswmvyqbvdzchrfugwphuthdqcpkhdnuvlgslx

[brianfry713]

Input:

Code: Select all

iltvqzunxiumwacpdlwelrufcgsjnioxwhsmiobgxvutxwiahgevzaacgu
vfdsdlmrvbsbanvtmtdmblswmvyqbvdzchrfugwphothdqcpkhdnuvlgslx

AC output:

Code: Select all

57
1 Replace 58,x
2 Replace 57,l
3 Replace 56,s
4 Replace 55,g
5 Replace 54,l
6 Replace 53,v
7 Replace 52,u
8 Replace 51,n
9 Replace 50,d
10 Replace 48,k
11 Replace 47,p
12 Replace 46,c
13 Replace 45,q
14 Replace 44,d
15 Replace 43,h
16 Replace 42,t
17 Replace 41,o
18 Replace 40,h
19 Replace 39,p
20 Replace 38,w
21 Replace 37,g
22 Replace 36,u
23 Replace 35,f
24 Replace 34,r
25 Replace 33,h
26 Replace 32,c
27 Replace 31,z
28 Replace 30,d
29 Replace 29,v
30 Replace 28,b
31 Replace 27,q
32 Replace 26,y
33 Replace 25,v
34 Replace 24,m
35 Replace 23,w
36 Replace 22,s
37 Replace 20,b
38 Replace 19,m
39 Replace 18,d
40 Replace 17,t
41 Replace 16,m
42 Replace 15,t
43 Replace 14,v
44 Replace 13,n
45 Replace 12,a
46 Replace 11,b
47 Replace 10,s
48 Replace 9,b
49 Replace 8,v
50 Replace 7,r
51 Replace 6,m
52 Replace 5,l
53 Replace 4,d
54 Replace 3,s
55 Replace 2,d
56 Replace 1,f
57 Insert 1,v

Mostafizur_cse, your code is generating:

Code: Select all

vfdsdlmrvbsbanvtmtdmblswmvyqbvdzcrfubwphuhdqcpkhdnuvlasgulx