Пожалуйста, подпишитесь на официальный канал Codeforces в Telegram по ссылке https://t.me/codeforces_official. ×

Блог пользователя alphadr

7D Palindrome Degree
Автор alphadr, 11 лет назад, По-английски

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.

  • Проголосовать: нравится
  • +1
  • Проголосовать: не нравится

»
11 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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.

→ Ответить
  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    → Ответить
  • »
    »
    9 лет назад, # ^ |
    ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    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 ..

    → Ответить
  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    → Ответить
»
11 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить
  • »
    »
    11 лет назад, # ^ |
    ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    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.

    → Ответить
»
8 лет назад, # |
  Проголосовать: нравится +27 Проголосовать: не нравится

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

→ Ответить