10739 - String to Palindrome

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

Moderator: Board moderators

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

10739 - String to Palindrome

Post by miras » Thu Oct 07, 2004 12:13 pm

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
Regrads
Miras

gvcormac
Problemsetter & Reviewer
Posts: 194
Joined: Fri Mar 15, 2002 2:00 am
Contact:

Post by gvcormac » Thu Oct 07, 2004 2:33 pm

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

Post by Eduard » Thu Oct 07, 2004 2:51 pm

I use DP for this problem. :wink:
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

Post by miras » Fri Oct 08, 2004 11:50 pm

Eduard .... how did u get that... ??
how does your DP look like ??
Remember Never Give Up
Regrads
Miras

Eduard
Experienced poster
Posts: 183
Joined: Fri Sep 26, 2003 2:54 pm
Location: Armenia,Yerevan

Post by Eduard » Sat Oct 09, 2004 6:02 pm

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

Post by miras » Sat Oct 09, 2004 6:55 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
Regrads
Miras

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

:)

Post by Miguel Angel » Sun Oct 10, 2004 3:23 am

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

Eduard
Experienced poster
Posts: 183
Joined: Fri Sep 26, 2003 2:54 pm
Location: Armenia,Yerevan

Post by Eduard » Sun Oct 10, 2004 9:53 am

You are right Miguel Angel.I got AC 0.00.047sc.And I'm one of fastests.(And my program is on Pascal) :D
someone who like to solve informatic problems.
http://acm.uva.es/cgi-bin/OnlineJudge?AuthorInfo:29650

User avatar
GVahe
New poster
Posts: 17
Joined: Thu Aug 05, 2004 6:04 pm
Location: Armenia
Contact:

Post by GVahe » Sun Oct 10, 2004 10:10 am

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
Experienced poster
Posts: 183
Joined: Fri Sep 26, 2003 2:54 pm
Location: Armenia,Yerevan

Post by Eduard » Sun Oct 10, 2004 1:32 pm

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]
someone who like to solve informatic problems.
http://acm.uva.es/cgi-bin/OnlineJudge?AuthorInfo:29650

User avatar
GVahe
New poster
Posts: 17
Joined: Thu Aug 05, 2004 6:04 pm
Location: Armenia
Contact:

Post by GVahe » Sun Oct 10, 2004 4:31 pm

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

Post by Repon kumar Roy » Wed Dec 31, 2014 5:58 pm

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 :D

Post Reply

Return to “Volume 107 (10700-10799)”