10739  String to Palindrome
Moderator: Board moderators
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..
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
Regrads
Miras
Regrads
Miras
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, lefttoright 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
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, lefttoright 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.
I use DP for this problem.
someone who like to solve informatic problems.
http://acm.uva.es/cgibin/OnlineJudge?AuthorInfo:29650
http://acm.uva.es/cgibin/OnlineJudge?AuthorInfo:29650
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[nj] 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,n1] a[1,n2] a[2,n3]..)
for finding a[0,5] we must see if s[0+1]=s[1]='a' is equal to s[65]=s[1]='a' than a[0,5]=a[1,6]=0(Its not hard to see that a[i,ni1]=0 for all 0<=i<n.
Now for a[0,4].S[1]='a' s[64]=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.
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[nj] 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,n1] a[1,n2] a[2,n3]..)
for finding a[0,5] we must see if s[0+1]=s[1]='a' is equal to s[65]=s[1]='a' than a[0,5]=a[1,6]=0(Its not hard to see that a[i,ni1]=0 for all 0<=i<n.
Now for a[0,4].S[1]='a' s[64]=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/cgibin/OnlineJudge?AuthorInfo:29650
http://acm.uva.es/cgibin/OnlineJudge?AuthorInfo:29650

 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
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/cgibin/OnlineJudge?AuthorInfo:29650
http://acm.uva.es/cgibin/OnlineJudge?AuthorInfo:29650
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 nj+1 do
if s=s[i+j1] then a[i,j]:=a[i+1,j2] else
a[i,j]:=1+min(a[i+1,j2],a[i,j1],a[i+1,j1]);
writeln('Case ',r,': ',a[1,n]);
end;
end.
[/pascal]
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 nj+1 do
if s=s[i+j1] then a[i,j]:=a[i+1,j2] else
a[i,j]:=1+min(a[i+1,j2],a[i,j1],a[i+1,j1]);
writeln('Case ',r,': ',a[1,n]);
end;
end.
[/pascal]
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 nj+1 do
if s=s[i+j1] then a[i,j]:=a[i+1,j2] else
a[i,j]:=1+min(a[i+1,j2],a[i,j1],a[i+1,j1]);
writeln('Case ',r,': ',a[1,n]);
end;
end. [/pascal]
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 nj+1 do
if s=s[i+j1] then a[i,j]:=a[i+1,j2] else
a[i,j]:=1+min(a[i+1,j2],a[i,j1],a[i+1,j1]);
writeln('Case ',r,': ',a[1,n]);
end;
end. [/pascal]
someone who like to solve informatic problems.
http://acm.uva.es/cgibin/OnlineJudge?AuthorInfo:29650
http://acm.uva.es/cgibin/OnlineJudge?AuthorInfo:29650

 Learning poster
 Posts: 96
 Joined: Tue Apr 23, 2013 12:54 pm
Re: 10739  String to Palindrome
Algo : Recursive DP
With initial contidion , easy to get AC
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,e1)));
}