526 - String Distance and Transform Process

All about problems in Volume 5. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 526 String Editing

Post by brianfry713 » Tue Jul 24, 2012 10:35 pm

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.
Check input and AC output for thousands of problems on uDebug!

mostafiz93
New poster
Posts: 31
Joined: Thu Nov 24, 2011 12:08 am

Re: 526 String Editing

Post by mostafiz93 » Wed Jul 25, 2012 12:59 am

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

User avatar
@ce
Learning poster
Posts: 71
Joined: Mon May 28, 2012 8:46 am
Location: Ranchi, India

Re: 526 String Editing

Post by @ce » Sat May 18, 2013 1:00 pm

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]);
                  }
            }
      }
}
-@ce

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 526 String Editing

Post by brianfry713 » Wed May 22, 2013 2:27 am

Try input:

Code: Select all

iltvqzunxiumwacpdlwelrufcgsjnioxwhsmiobgxvutxwiahgevzaacgu
vfdsdlmrvbsbanvtmtdmblswmvyqbvdzchrfugwphothdqcpkhdnuvlgslx
Your code is generating this string:

Code: Select all

vfdsdlmrvbsbanvtmtdmblswmvyqbvdzchrfugwphuthdqcpkhdnuvlgslx
Check input and AC output for thousands of problems on uDebug!

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 526 - String Distance and Transform Process

Post by brianfry713 » Thu Jan 08, 2015 12:43 am

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
Check input and AC output for thousands of problems on uDebug!

Post Reply

Return to “Volume 5 (500-599)”