10453

Tobbi · Post by **Tobbi** » Thu Feb 27, 2003 1:20 am

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!

Larry · Post by **Larry** » Thu Feb 27, 2003 2:45 am

Code: Select all

abcd
aaaa
abc
aab
abababaabababa
pqrsabcdpqrs
aaab
acaaaba
zzzaaazz
pooq
aoob

Gives:

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

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..)

prom · Post by **prom** » Sun Mar 02, 2003 12:14 pm

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

Tobbi · Post by **Tobbi** » Sun Mar 02, 2003 4:38 pm

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...

prom · Post by **prom** » Sun Mar 02, 2003 5:08 pm

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.

Larry · Post by **Larry** » Mon Mar 03, 2003 6:18 am

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

junjieliang · Post by **junjieliang** » Sat May 03, 2003 2:05 pm

Solved... sorry

junjieliang · Post by **junjieliang** » Sun May 04, 2003 9:42 am

Solved

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

Dmytro Chernysh · Post by **Dmytro Chernysh** » Mon May 05, 2003 7:17 pm

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.

Nak · Post by **Nak** » Tue May 06, 2003 3:54 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.

Dmytro Chernysh · Post by **Dmytro Chernysh** » Tue May 06, 2003 4:04 am

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

Nak · Post by **Nak** » Tue May 06, 2003 4:20 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.

anupam · Post by **anupam** » Sat Jul 12, 2003 12:32 pm

Hey gyes, what's the answer???

Plz help

Larry · Post by **Larry** » Sat Jul 12, 2003 3:19 pm

I get :

Code: Select all

5 azbzcezdzeczbza

anupam · Post by **anupam** » Sat Jul 12, 2003 3:33 pm

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.
--
Please describe your alg in short plz.
advanced thabnks to all.

OJ Board

10453 - Make Palindrome

10453 - Make Palindrome

10453 - Make palindrome

Thanks!