## 10739 - String to Palindrome

Moderator: Board moderators

miras
Learning poster
Posts: 98
Joined: Sat Jun 14, 2003 1:45 pm

### 10739 - String to Palindrome

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..
Remember Never Give Up
Miras

gvcormac
Problemsetter & Reviewer
Posts: 194
Joined: Fri Mar 15, 2002 2:00 am
Contact:
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
Last edited by gvcormac on Sun Oct 10, 2004 7:01 pm, edited 1 time in total.

Eduard
Experienced poster
Posts: 183
Joined: Fri Sep 26, 2003 2:54 pm
Location: Armenia,Yerevan
I use DP for this problem.
someone who like to solve informatic problems.
http://acm.uva.es/cgi-bin/OnlineJudge?AuthorInfo:29650

miras
Learning poster
Posts: 98
Joined: Sat Jun 14, 2003 1:45 pm
Eduard .... how did u get that... ??
how does your DP look like ??
Remember Never Give Up
Miras

Eduard
Experienced poster
Posts: 183
Joined: Fri Sep 26, 2003 2:54 pm
Location: Armenia,Yerevan
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.
someone who like to solve informatic problems.
http://acm.uva.es/cgi-bin/OnlineJudge?AuthorInfo:29650

miras
Learning poster
Posts: 98
Joined: Sat Jun 14, 2003 1:45 pm
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
Remember Never Give Up
Miras

Miguel Angel
Learning poster
Posts: 60
Joined: Tue Aug 13, 2002 2:39 am
Location: Mexico

### :)

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

Eduard
Experienced poster
Posts: 183
Joined: Fri Sep 26, 2003 2:54 pm
Location: Armenia,Yerevan
You are right Miguel Angel.I got AC 0.00.047sc.And I'm one of fastests.(And my program is on Pascal)
someone who like to solve informatic problems.
http://acm.uva.es/cgi-bin/OnlineJudge?AuthorInfo:29650

GVahe
New poster
Posts: 17
Joined: Thu Aug 05, 2004 6:04 pm
Location: Armenia
Contact:
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
fillchar(a,sizeof(a),0);
for r:=1 to t do
begin
i:=0;
while c in ['a'..'z'] do
begin
inc(i);
s:=c;
end;
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
Experienced poster
Posts: 183
Joined: Fri Sep 26, 2003 2:54 pm
Location: Armenia,Yerevan
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
fillchar(a,sizeof(a),0);
for r:=1 to t do
begin
i:=0;
while c in ['a'..'z'] do
begin
inc(i);
s:=c;
if eoln then break; <----------This line you need
end;
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]
someone who like to solve informatic problems.
http://acm.uva.es/cgi-bin/OnlineJudge?AuthorInfo:29650

GVahe
New poster
Posts: 17
Joined: Thu Aug 05, 2004 6:04 pm
Location: Armenia
Contact:
Yes, I got AC
Thank's for help

Repon kumar Roy
Learning poster
Posts: 96
Joined: Tue Apr 23, 2013 12:54 pm

### Re: 10739 - String to Palindrome

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