Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official. ×

StasyaCat's blog

By StasyaCat, history, 3 weeks ago, In English,
Tutorial is loading...

C++ code: 46178226

Tutorial is loading...

C++ code: 46178084

Tutorial is loading...

C++ code: 46178118

Tutorial is loading...

C++ code: 46178228

Tutorial is loading...

C++ code: 46178239

Tutorial is loading...

C++ code: 46178244

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

»
3 weeks ago, # |
Rev. 2   Vote: I like it -17 Vote: I do not like it

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

»
3 weeks ago, # |
  Vote: I like it +19 Vote: I do not like it

Thank you for the timely editorials StasyaCat.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

too stupid to remember the meaning of problem D ....

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Did anyone solve E using binary search? I tried and get TLE, reason was modulo operator of get hash function.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

»
3 weeks ago, # |
  Vote: I like it +5 Vote: I do not like it

Interesting note: on problem D, for n larger than 35 you can just output "YES (n — 1)" in O(1).

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    Note:for n larger than 31 ,you can just output "YES (n-1)",,,-_-

»
3 weeks ago, # |
  Vote: I like it +5 Vote: I do not like it

Wow! this Editorial is so detailed. Thank you.

»
3 weeks ago, # |
Rev. 2   Vote: I like it +10 Vote: I do not like it

nice solutions and editorials for me! Thank you!

»
3 weeks ago, # |
  Vote: I like it +5 Vote: I do not like it

So overall, the complexity for E will be 26×n^3 or n^3 only ?

  • »
    »
    3 weeks ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    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]

»
3 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

I solved F with an overly complicated sqrt decomposition in 46236775. I feel so silly.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I solved problem F using a normal segment tree in O(q*logn*logk). 46262923

»
3 weeks ago, # |
Rev. 3   Vote: I like it +18 Vote: I do not like it

StasyaCat your editorials are very detailed and well explained, for a newbie like me detailed editorials matter a lot. Thanks!

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

    Thank you!

    It feels so good when community appreciates your job (^-^)

»
3 weeks ago, # |
  Vote: I like it +5 Vote: I do not like it

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)

»
12 days ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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