alphadr's blog

7D Palindrome Degree
By alphadr, 11 years ago, In English

http://codeforces.com/problemset/problem/7/D

Can someone please explain to me the problem ? I don't understand how the result was 6 for the second input case.

  • Vote: I like it
  • +1
  • Vote: I do not like it

Comments Comments (7)
| Write comment?
»
11 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Well, the problem says: "Output the only number — the sum of the polindrome degrees of all the string's prefixes."

So if you get the degree for every prefix you get the following:

"a" — 1; "ab" — 0; "aba" — 2; "abac" — 0; "abaca" — 0; "abacab" — 0; "abacaba" — 3;

So, the sum of all degrees is 6.

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thank you, I got AC now :) Didn't quite understand how to calculate the value for each prefix at first.

    → Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    why "ab" has palindrome degree of 0 I mean , [n/2] prefix = "a" -> 1 [n/2] suffix = "b" -> 1

    Please help me to understand the problem ???

    UPD : I missed The line It should be a palindrome ..

    → Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    actually I didn't get how to calculate palindrome degrees?

    → Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

explanation of second input case as hriss95 said

BTW, I found some solutions which got AC but it gives WA on some test due to bad hashing

for example this submission 3686936 which is the first submission on status list

fails on test:

aobd

→ Reply
  • »
    »
    11 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Thanks for your reply. I got AC using the Z-Algorithm, by concatenating the string with its reverse, didn't use rabin karp hashing. My submission is 4207962.

    → Reply
»
8 years ago, # |
  Vote: I like it +27 Vote: I do not like it

When I saw this, I thought: "7-dimensional Palindrome Degree? :O"

→ Reply