Palindromes

[klopyrev]

Here is an interesting problem that I have no idea how to solve. I didn't think about it for very long, but all the DP solutions I thought about have flaws in them. If you know how to solve it, feel free to tell me (please).

Given a string, find the number of UNIQUE palindromes that are subsequences (not substrings). For example, given MADAM:

M, A, D, MM, AA, MAM, MDM, ADA, MAM, MAAM, MADAM. (Hopefully, I didn't miss any)

Have fun and good luck.

KL

PS: Sometimes, its good to misread problems. You come up with new and harder ones. Refer to: http://acm.uva.es/problemset/v3/353.html

[bugzpodder]

its easy, brute force it.

[bugzpodder]

this may or may not work. im hoping it will

code:

f(string x)   if x.length==0 return 0   int cnt=0;   for (i=0;i<x.length;i++)      for (j=0;j<i;j++) if (x[i]==x[j]) break;      if (j==i) for (j=x.length-1;j>i;j--) if (x[i]==x[j])        cnt+=f(x[i+1..j-1]);   return cnt

[ericfourfour]

Would AMDMA count as well?

Here is my way of thinking:

It is easy to find palindromes, if the word is already a palindrome.

For example, in any palindrome, when the letters are labelled 1 through the length:

Singles (ex. M):
1 is a palindrome
2 is a palindrome
... ceil (length / 2)

Doubles (ex. MM):
1 + length is a palindrome
2 + length - 1 is a palindrome
Essentially, (1 + i) + (length - i) is a palindrome, if i starts at 0 and ends at floor (length / 2) - 1

Also, if you break the palindrome into substrings (sort of following what was done for doubles), you can find all of the visible palindromes like ADA.

That only covers singles, doubles and the visible palindromes. For any palindromes like MMMM, in MADAMIMADAM, or MAAM, in MADAM, I guess, you will have to rearrange the word.

[klopyrev]

lol, Thankful Users??? What is that? hmm... I've never even seen that feature. Anyway, erikfourfour, nice try!!! (Too bad doesn't work for anything other than singles, doubles or visible palindromes) Thanks for the suggestion. As for bugzpodder: I am too damn tired to understand your solution right now. Just finished solving the first 2 problems of the TopCoder Qualification Round 3! 1000 pointer seems easier than the 500 pointer, doesn't it??? (At least it requires less code) Anyway, congrats on 16th place. You were slipping for the last two contests there. I was wondering how it was possible that I had a higher rating than you. Now, everything is back in order.

KL

[Drakain Zeil]

not real code/is psuedo.

code:

mkstrs(string z) /divides the string into N! strings {fac = factorial(length(z)) string a[fac]; string b[]; ... you'd grab a tree structure and just toss all it's values in, I got lasy and don't feel like writing the code, when I can sleep :)   for (i=1;i<=fac;i++)     if (ispal(a[i]))         then b[j++]=a[i] } ispal(string x) { //checks if string is a pal.    check = 1    len=length(x)    for (i=1;i<=len;i++)      if (x[i] != x[len-i]) then        check *=0   return check; }