Why can't I construct strings like "aa...a"? There is only one palindrome (the whole string) and it's the minimum value of palindromes obviously. Where is the contradiction the the statement?
Ok, I've found relation between n and maximin palindrome number and several optimal patterns that depend on n mod 12. Only one question has left: how to prove all this stuff?
My AC solution is using n mod 6 to determine the optimal solution.
The proof is rather complicated and heavily relies on some particular pattern of length 6. Apart from that, it's just analysing lots and lots of cases.
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."
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.