Why for n=6

aababbaa is OK
abbaabaa is WA ?

Who understands the statement or have AC please explain me
statement on some examples or say what does it mean

"The complexity of a name is defined as the minimal number of palindromes into which it can be decomposed. Help Vasechkin to invent the most complex name for his problem."

Thank you in advance

aa bab b aa - 4 palindromes
abba aba a - 3 palindromes

4 is max number of palindromes in all string with length 8.

Edited by author 28.10.2009 17:03

what about

a|a|b|a|b|b|a|a - 8 polyndromes :)))

You wrote possible decomposition, but it not minimal.

Let's define F(S) as complexity of a string S.
F(S) is equal to minimal number of palindromes
into wicth it can be decomposed.
for example consider string "abbaabaa"
it can be decomposed in different ways
a|bb|aabaa - 3 pflimdromes
a|bb|a|aba|a - 5 pflindromes
a|b|b|a|a|b|a|a - 8 palindromes
the minimal number is 3, so F("abbaabaa") = 3

We must to find string S of given length N
such that F(S) is maximal possible for all
strings with legth N.