You know the author does not bother about contributions when he/she does not attach nice solution codes with the editorial. (Although the explanations are quite good).
Can anyone help me with a WA on problem E? 46186783
I am doing the anagram hashing by assigning a prime to each letter of the alphabet and multiplying them modulo a big prime. I tried different primes, so it's probably not a collision.
OK, I found it. Previously I thought when I "disable" a row, I can just subtract one. But the palindrome centered on the disabled row can be of course bigger.
But I still had WA on later tests. Turns out scientific notation (like 1e17) is for floating point constants. So my const prime wasn't prime, because double can store integers only up to 1e15.
26*n^3 passes, but you can get rid of this factor. When you increment a letter's count for a row, you can check if you increment the count from odd to even or from even to odd. So alongside eg. letter_count[n][26] you can keep odd_occurences[n]
Seriously, what the f###? How can a div2 round consist of Manacher algorithm as E and then persistent segtree as F??? In div2 rounds, focus should be on thinking problems and atmost lazy-segtree is allowed. A very bad round.
You know the author does not bother about contributions when he/she does not attach nice solution codes with the editorial. (Although the explanations are quite good).
UPDATE: Now they are added
Sorry for that :(
The solution codes will be added shortly.
They were added.
вспомагательного
Thank you for the timely editorials stanislav.bezkorovainyi.
too stupid to remember the meaning of problem D ....
Did anyone solve E using binary search? I tried and get TLE, reason was modulo operator of get hash function.
I got AC with O((nm)^2) 46184585.
46184740 after a little change, AC 420ms !!!
maybe the data is random,so you can AC it
I solved E with decimal search.
Can anyone help me with a WA on problem E? 46186783
I am doing the anagram hashing by assigning a prime to each letter of the alphabet and multiplying them modulo a big prime. I tried different primes, so it's probably not a collision.
OK, I found it. Previously I thought when I "disable" a row, I can just subtract one. But the palindrome centered on the disabled row can be of course bigger.
But I still had WA on later tests. Turns out scientific notation (like
1e17
) is for floating point constants. So my const prime wasn't prime, becausedouble
can store integers only up to 1e15.Interesting note: on problem D, for n larger than 35 you can just output "YES (n — 1)" in O(1).
Note:for n larger than 31 ,you can just output "YES (n-1)",,,-_-
Wow! this Editorial is so detailed. Thank you.
nice solutions and editorials for me! Thank you!
за разбор лайк
So overall, the complexity for E will be 26×n^3 or n^3 only ?
26*n^3 passes, but you can get rid of this factor. When you increment a letter's count for a row, you can check if you increment the count from odd to even or from even to odd. So alongside eg.
letter_count[n][26]
you can keepodd_occurences[n]
Alright, thank you !!!
I solved F with an overly complicated sqrt decomposition in 46236775. I feel so silly.
I solved problem F using a normal segment tree in O(q*logn*logk). 46262923
stanislav.bezkorovainyi your editorials are very detailed and well explained, for a newbie like me detailed editorials matter a lot. Thanks!
Thank you!
It feels so good when community appreciates your job (^-^)
Can you explain/prove this equation for me?
W(a, b, c, d) = w(c, d) − w(a − 1, d) − w(c, b − 1) + w(a − 1,b − 1)
Maybe one day I'll learn how to manage pictures in codeforces' comments, but for now here is the link:
https://drive.google.com/open?id=1NhVlMIdhtSjGo4Djhygypd_8U4-3U0CC
Hope the proof is good and my English is not that bad :)
Thanks, so straightforward
You are welcome)
Can anyone help me with my solution for D. I am not able to figure out what my mistake is. Link to My code . TIA
best editorial indeed
Seriously, what the f###? How can a div2 round consist of Manacher algorithm as E and then persistent segtree as F??? In div2 rounds, focus should be on thinking problems and atmost lazy-segtree is allowed. A very bad round.