10739 - String to Palindrome

[miras]

Hello ..

I tried to solve this problem diuring then contest... but i couldn't ..

Do yuo have any hints how to solve it.. It's quite nice tasdk and i would like to do it..

[gvcormac]

The comments below refer to the problem named "Help!" (number 10728).

You can search the web for "Unification" to get a full description of an algorithm to solve this problem. (Actually, full unification works on trees not just strings, and if finds the "most general unifier" which transforms the patterns into a common pattern such that a string matches the unified pattern if and only if it matches both the original patterns.)

Here are some hints:

- as shown in the example, the two pattern matching problems are independent, so you should rename the variables in one pattern so that they are different from the variables in the other

- compare the two patterns a word at a time (any order, left-to-right will do)

- whenever a variable must match a word, replace all instances of the variable by the word in both patterns

- whenever a variable must match a variable, replace one by the other (doesn't matter which)

- whenever two words must match, if they're equal, fine; otherwise the match is impossible

[Eduard]

I use DP for this problem.

[miras]

Eduard .... how did u get that... ??
how does your DP look like ??

[Eduard]

I will explaine it using matrix,but you will see that you can solve it just using 2 arrays.Let take a matrix a[n,n].a[i,j] means how many moves we must do for making word S polindrom(were S is our word without last j characters and without first i caracters).Our answer will be a[0,0].
You must find elements of half of this matrixt(this matrix is simetrically)
diagonally.
a[i,i]=0 for all 0<=i<=n.
Now if we want to find element a[i,j] for word s[1..n] then
1. If s[i+1]=s[n-j] then a[i,j]=a[i+1,j+1]
2. if s<>s[j] then a[i,j]=min(a[i,j+1],a[i+1,j],a[i+1,j+1])+1
For example let take word s='abccda'(n=6) at first we have matrix a[n,n].

0.0 0 0 0 0 0 0
1.0 0 0 0 0 0 0
2.0 0 0 0 0 0 0
3.0 0 0 0 0 0 0
4.0 0 0 0 0 0 0
5.0 0 0 0 0 0 0
6.0 0 0 0 0 0 0

We must find elements of green ones.
At fisrt we must start finding them in this way(a[0,n-1] a[1,n-2] a[2,n-3]..)
for finding a[0,5] we must see if s[0+1]=s[1]='a' is equal to s[6-5]=s[1]='a' than a[0,5]=a[1,6]=0(Its not hard to see that a[i,n-i-1]=0 for all 0<=i<n.
Now for a[0,4].S[1]='a' s[6-4]=s[2]='b' than a[0,4]=min(a[1,4],a[0,5],a[1,5])+1 a[0,4]=1. Then we must find a[1,3] then a[2,2] then a[3,1] then a[4,0] then a[0,3] then a[1,2] and so on.And you will get a[0,0](for this test case a[0,0]=1).
This is all.

[miras]

thanks...
i think your solution is hm... very intresting but i solved this task using sth. like greedy... but once again thanks for your answere becouse thanks to that i will learn sth. morwe

[Miguel Angel]

DP solution in fact works very well for this problem, and you don't need so much memory as Eduard said .

[Eduard]

You are right Miguel Angel.I got AC 0.00.047sc.And I'm one of fastests.(And my program is on Pascal)

[GVahe]

Hi Eduard, can you explain me why I get WA for this problem.
I can't find the mistake
Here is my code
[pascal]var i,j,k,l,n,m,p,r,t:integer;
a:array[1..1001,0..1001] of integer;
c:char;
s:array[1..1001] of char;
function min(a,b,c:integer):integer;
var m:integer;
begin
if a<b then m:=a else m:=b;
if c<m then m:=c;
min:=m;
end;
begin
readln(t);
fillchar(a,sizeof(a),0);
for r:=1 to t do
begin
read(c);
i:=0;
while c in ['a'..'z'] do
begin
inc(i);
s:=c;
read(c);
end;
read(c);
n:=i;
for j:=2 to n do
for i:=1 to n-j+1 do
if s=s[i+j-1] then a[i,j]:=a[i+1,j-2] else
a[i,j]:=1+min(a[i+1,j-2],a[i,j-1],a[i+1,j-1]);
writeln('Case ',r,': ',a[1,n]);
end;
end.
[/pascal]

[Eduard]

At first you are using to much memory.And you are reading not right.
this code is getting AC.
[pascal]
var i,j,k,l,n,m,p,r,t:integer;
a:array[1..1001,0..1001] of integer;
c:char;
s:array[1..1001] of char;
function min(a,b,c:integer):integer;
var m:integer;
begin
if a<b then m:=a else m:=b;
if c<m then m:=c;
min:=m;
end;
begin
readln(t);
fillchar(a,sizeof(a),0);
for r:=1 to t do
begin
read(c);
i:=0;
while c in ['a'..'z'] do
begin
inc(i);
s:=c;
if eoln then break; <----------This line you need
read(c);
end;
readln; <----------And this(not read(c))
n:=i;
for j:=2 to n do
for i:=1 to n-j+1 do
if s=s[i+j-1] then a[i,j]:=a[i+1,j-2] else
a[i,j]:=1+min(a[i+1,j-2],a[i,j-1],a[i+1,j-1]);
writeln('Case ',r,': ',a[1,n]);
end;
end. [/pascal]

[GVahe]

Yes, I got AC
Thank's for help

[Repon kumar Roy]

Algo : Recursive DP

Code: Select all

if( s[b] == s[e]) {
                // If s[b] == s[e] , no insert or delete
                return  dp[b][e] = cal(b + 1, e - 1);
        }
else {
                return dp[b][e] = 1 + min ( cal(b, e - 1) , min(cal(b + 1 , e) , cal(b+1,e-1)));
        }

With initial contidion , easy to get AC