## 10453 - Make Palindrome

Moderator: Board moderators

### 10453 - Make Palindrome

I'm using a doubly linked list and look from the beginning and the end to put in the missing characters to make it a palindrome. Though I get the correct example inputs, I always get a WA from the judge. Could please someone with an AC post some further examples? Thanks a ton!
Tobbi
New poster

Posts: 17
Joined: Sat Jan 25, 2003 3:06 pm
Location: Europe

Code: Select all
`abcdaaaaabcaababababaabababapqrsabcdpqrsaaabacaaabazzzaaazzpooqaoob`

Gives:
Code: Select all
`3 abcdcba0 aaaa2 abcba1 baab0 abababaabababa9 pqrsabcdpqrqpdcbasrqp1 baaab2 acbaaabca1 zzzaaazzz2 pqooqp2 abooba`

It's specially graded, so your actual palindrome may vary... it's a dynamic programming problem, so you should probably do it that way.. =)

(I had posted some 2000 character examples, but it's too long for this post.. maybe you should try those too..)
Larry
Guru

Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City

this problem is very similiar to well known problem -- optimal matrix multiplication
prom
New poster

Posts: 10
Joined: Thu Jul 25, 2002 11:58 pm
Location: Poland

Which problem do you mean exactly, Prom?

I suppose you mean some variation of optimal matrix chain multiplication that can be solved by dynamic programming...
Last edited by Tobbi on Sun Mar 02, 2003 5:54 pm, edited 1 time in total.
Tobbi
New poster

Posts: 17
Joined: Sat Jan 25, 2003 3:06 pm
Location: Europe

Consider a string x1x2x3...xn, s[1,n] is our optimal solution, then

s[m,n] = s[m+1,n-1], if xm=xn,
min(s[m+1,n],s[m,n-1])+1, otherwise

Maybe it is not exacly optimal matrix chain multiplication, but method of solving is similiar.

optimal matrix chain multiplication is O(n^3) .

Hope this helps.
prom
New poster

Posts: 10
Joined: Thu Jul 25, 2002 11:58 pm
Location: Poland

I did it using LCS, but maybe there's a faster solution..
Larry
Guru

Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City

### 10453 - Make palindrome

Solved... sorry
Last edited by junjieliang on Sun May 04, 2003 9:44 am, edited 1 time in total.
junjieliang
Experienced poster

Posts: 169
Joined: Wed Oct 31, 2001 2:00 am
Location: Singapore

Solved
Thanks anyway to all who read. And for all who have problems try this test: azbzczdzez
junjieliang
Experienced poster

Posts: 169
Joined: Wed Oct 31, 2001 2:00 am
Location: Singapore

### 10453

How did you find palidrome? Because it's easy to find the number, but to build palindrome is not so easy...
Dmytro Chernysh
Experienced poster

Posts: 146
Joined: Sat Apr 26, 2003 2:51 am

I used dynamic programming to solve
this. Let f(s) be the shortest
palindrome created from the string
s. There are two cases:

If the first and last character of
s is the same, say s=a[...]a, then
f(s) = af([...])a

Otherwise, say s=a[...]b, then
f(s) = af([...]b)a or bf(a[...])b,
whichever is shorter.

If f is memoized it is fast enough.
Hope this helps.
Nak
New poster

Posts: 14
Joined: Sat Oct 26, 2002 5:59 am
Location: Sweden

### Thanks!

But don't really undrestand the method
Sure, dynamic programming should be applied, but...
I'll be very thankful
Dmytro Chernysh
Experienced poster

Posts: 146
Joined: Sat Apr 26, 2003 2:51 am

I think the easiest method is to
make a function which takes a
string and two indices as
arguments (start and end index of
a substring). Since these indices
will both be smaller than 1000 you
can make a memo-table which is
1000*1000 elements large and store
values from old function calls.
Then you pretty much just implement
the recursive "formula" in my
previous post. Of course you need
to stop when start>=end.

I don't want to post my working
code here, but if you like i can
mail it to you.
Nak
New poster

Posts: 14
Joined: Sat Oct 26, 2002 5:59 am
Location: Sweden

Plz help
"Everything should be made simple, but not always simpler"
anupam
A great helper

Posts: 405
Joined: Wed Aug 28, 2002 6:45 pm

I get :

Code: Select all
`5 azbzcezdzeczbza`
Larry
Guru

Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City

will you please tell me the method(algorithm) you used. bcz i used a very inefficient alg i think and got wa.
but can't understand why.
--
"Everything should be made simple, but not always simpler"
anupam
A great helper

Posts: 405
Joined: Wed Aug 28, 2002 6:45 pm

Next