### StasyaCat's blog

By StasyaCat, history, 8 months ago, ,

C++ code: 46178226

C++ code: 46178084

C++ code: 46178118

C++ code: 46178228

C++ code: 46178239

C++ code: 46178244

• +137

 » 8 months ago, # | ← Rev. 2 →   -17 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
•  » » 8 months ago, # ^ | ← Rev. 2 →   +9 Sorry for that :(The solution codes will be added shortly.
•  » » 8 months ago, # ^ |   +24 They were added.
 » 8 months ago, # |   +19 Thank you for the timely editorials StasyaCat.
 » 8 months ago, # |   0 too stupid to remember the meaning of problem D ....
 » 8 months ago, # |   0 Did anyone solve E using binary search? I tried and get TLE, reason was modulo operator of get hash function.
•  » » 8 months ago, # ^ |   +3 I got AC with O((nm)^2) 46184585.
•  » » 8 months ago, # ^ |   +3 46184740 after a little change, AC 420ms !!!
•  » » » 8 months ago, # ^ |   0 maybe the data is random,so you can AC it
•  » » 8 months ago, # ^ |   0 I solved E with decimal search.
 » 8 months ago, # |   0 Can anyone help me with a WA on problem E? 46186783I 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.
•  » » 8 months ago, # ^ |   0 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.
 » 8 months ago, # |   +5 Interesting note: on problem D, for n larger than 35 you can just output "YES (n — 1)" in O(1).
•  » » 8 months ago, # ^ |   +11 Note:for n larger than 31 ,you can just output "YES (n-1)",,,-_-
 » 8 months ago, # |   +5 Wow! this Editorial is so detailed. Thank you.
 » 8 months ago, # | ← Rev. 2 →   +10 nice solutions and editorials for me! Thank you!
 » 8 months ago, # |   +5 So overall, the complexity for E will be 26×n^3 or n^3 only ?
•  » » 8 months ago, # ^ | ← Rev. 2 →   0 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]
•  » » » 8 months ago, # ^ |   0 Alright, thank you !!!
 » 8 months ago, # |   +3 I solved F with an overly complicated sqrt decomposition in 46236775. I feel so silly.
 » 8 months ago, # |   0 I solved problem F using a normal segment tree in O(q*logn*logk). 46262923
 » 8 months ago, # | ← Rev. 3 →   +18 StasyaCat your editorials are very detailed and well explained, for a newbie like me detailed editorials matter a lot. Thanks!
•  » » 8 months ago, # ^ |   +13 Thank you!It feels so good when community appreciates your job (^-^)
 » 8 months ago, # |   +5 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)
•  » » 8 months ago, # ^ |   +10 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-3U0CCHope the proof is good and my English is not that bad :)
•  » » » 8 months ago, # ^ |   +5 Thanks, so straightforward
•  » » » » 8 months ago, # ^ |   0 You are welcome)
 » 7 months ago, # | ← Rev. 2 →   0 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