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!

 Guru
 Posts: 647
 Joined: Wed Jun 26, 2002 10:12 pm
 Location: Hong Kong and New York City
 Contact:
Code: Select all
abcd
aaaa
abc
aab
abababaabababa
pqrsabcdpqrs
aaab
acaaaba
zzzaaazz
pooq
aoob
Code: Select all
3 abcdcba
0 aaaa
2 abcba
1 baab
0 abababaabababa
9 pqrsabcdpqrqpdcbasrqp
1 baaab
2 acbaaabca
1 zzzaaazzz
2 pqooqp
2 abooba
(I had posted some 2000 character examples, but it's too long for this post.. maybe you should try those too..)
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...
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.

 Experienced poster
 Posts: 169
 Joined: Wed Oct 31, 2001 2:00 am
 Location: Singapore
10453  Make palindrome
Solved... sorry
Last edited by junjieliang on Sun May 04, 2003 9:44 am, edited 1 time in total.

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

 Experienced poster
 Posts: 146
 Joined: Sat Apr 26, 2003 2:51 am
10453
How did you find palidrome? Because it's easy to find the number, but to build palindrome is not so easy...
Please write a discription.
Please write a discription.
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.
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.

 Experienced poster
 Posts: 146
 Joined: Sat Apr 26, 2003 2:51 am
Thanks!
Thanks Nak for reply!
But don't really undrestand the method
Sure, dynamic programming should be applied, but...
Can you show more extact coding.
I'll be very thankful
But don't really undrestand the method
Sure, dynamic programming should be applied, but...
Can you show more extact coding.
I'll be very thankful
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 memotable 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.
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 memotable 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.

 Guru
 Posts: 647
 Joined: Wed Jun 26, 2002 10:12 pm
 Location: Hong Kong and New York City
 Contact:
I get :
Code: Select all
5 azbzcezdzeczbza