http://codeforces.net/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.
# | User | Rating |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3831 |
3 | Radewoosh | 3646 |
4 | jqdai0815 | 3620 |
4 | Benq | 3620 |
6 | orzdevinwang | 3529 |
7 | ecnerwala | 3446 |
8 | Um_nik | 3396 |
9 | gamegame | 3386 |
10 | ksun48 | 3373 |
# | User | Contrib. |
---|---|---|
1 | cry | 164 |
1 | maomao90 | 164 |
3 | Um_nik | 163 |
4 | atcoder_official | 160 |
5 | -is-this-fft- | 158 |
6 | awoo | 157 |
7 | adamant | 156 |
8 | TheScrasse | 154 |
8 | nor | 154 |
10 | Dominater069 | 153 |
http://codeforces.net/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.
Name |
---|
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.
Thank you, I got AC now :) Didn't quite understand how to calculate the value for each prefix at first.
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 ..
actually I didn't get how to calculate palindrome degrees?
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
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.
When I saw this, I thought: "7-dimensional Palindrome Degree? :O"