10617 - Again Palindrome

[Dreamer#1]

Any hints on how this problem has to be solved?

It has to be a mathematical solution, can't find it.

Hope someone will help.

[subbu]

Count the number of palindromes that can be made out of
subsets of the characters of the
given string,
maintaining the order(no permutations allowed).
(same characters at different positions are considered different).

For every palindrome u find in the above way,
there is a unique way of scoring out the letters.


Hope this helps.
Subbu.

[HidWalker]

I first try to use brute force to solve this problem,
but I got TLE...
I thick there's a better algo, but I still can't find out,
Can someone give me a tip,
What algo should be used here??
Thx.

[Eduard]

I solve this problem using DP(Dinamic Programming).

Eduard.

[muvee]

Hello guys.

If any of the 'Accepted' guys could give me their output for :

13
AMERFAZALRAHMAN
MIRANDA
GTAVICECITY
GRANDTHEFTAUTO
INTRODUCTIONTOALGORITHMSTHOMASCORMENCHARLESRONALDCLIFFORD
LOWPRICEEDITION
THECLASSICWORK
T
MSNMESSENGER
AAAAAAAA
AAAA
AAABBB
BBBAAA

174
10
35
40
637196
61
22
1
50
255
15
14
14

Many Thanks

[muvee]

No need now guys .. I found my mistake seconds after posting this.

For anybody who attempts this question in the future, you need to use long long !!

[Niaz]

I do also understand the problem. But feeling uneasy to solve ! From another thread, I came to know that this problem can be solved by using DP. But I am really very weak in DP. Is there any one who can tell me the procedure of solving this problem using DP ? Is it an Edit Distance problem ?
Waiting for the help....

[d91-lek]

f(BAOBAB) = 1 + f(AOBA) + f(BAOBA) + f(AOBAB) - f(AOBA)

The first and last character are either the same or not. Above they are the same and form 1 + f(AOBA) palindromes plus the ones where only one or the other of them is member minus the interval counted twice.

Memoization, keeping a lookup table of function values, is always a soon implemented alternative to Dynamic Programming if you have the simple recursive function written down.

[serur]

Also if you use Pascal comp type becomes a must(int64), and therefore also you should write output function manually(at least I did so..),for comp can't be written with writeln(? am I right?)

[d91-lek]

Good point. Usual integer is not big enough. I didn't think of this at first and then worried I had to use my bignum routines. It was close but C can manage.

Biggest test case

Code: Select all

1
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA

Answer

Code: Select all

1152921504606846975

8 bytes are needed to store 2^60 palindromes. This datatype is commonly called long long int or quad, 4 original 16 bit ints also called words,

To declare and print in C:

Code: Select all

long long int i;
printf("%lld", i);

Pascal I have not tested but on this page http://gnu-pascal.de/gpc/Main-Branch-Integer-Types.html it says GNU Pascal calls this 64 bit datatype LongInt so I presume Writeln can handle it. I hope I have not made you sad, serur, it is never unnecessary to build your own bignum code.

[ar2rd]

Can someone explain me how is the answer for ABA 5?
I counted 4 :
1. leave as it is
2. remove B
3. remove A and A
4. remove everything

[Jan]

Dont open a new thread if there is one already. Use an existing thread.

What if you remove A and B?

[pdwd]

Some hints for this problem:

- I used 3 spaces of subproblems;
- Complexity of my algorithm is O(n^2) where n is the length of the word;

Hope it helps, by complexity you can try to guess one space and then find the dependencies.