|
|
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. Sorry, i understand my mistake Edited by author 01.04.2014 01:43 Edited by author 04.05.2011 02:28 Edited by author 14.11.2009 00:52 Subj Please, give me example for n = 1..5 Please, help... n=1 ==> a (or b) n=2 ==> ab (or ba) n=3 ==> aab n=4 ==> aaba n=5 ==> aabab n=6 ==> aababb the solution is "ab" or "ba" 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 :))) 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 You wrote possible decomposition, but it not minimal. The complexity of a name is defined as the minimal number of palindromes into which it can be decomposed. 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. |
|
|