stanislav.bezkorovainyi's blog

Codeforces Round #524 (Div. 2) Editorial
By stanislav.bezkorovainyi, history, 6 years 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

»
6 years 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

→ Reply
»
6 years ago, # |
  Vote: I like it +19 Vote: I do not like it

Thank you for the timely editorials stanislav.bezkorovainyi.

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
6 years 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.

→ Reply
»
6 years 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.

→ Reply
  • »
    »
    6 years 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.

    → Reply
»
6 years 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).

→ Reply
  • »
    »
    6 years 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)",,,-_-

    → Reply
»
6 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Wow! this Editorial is so detailed. Thank you.

→ Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it +10 Vote: I do not like it

nice solutions and editorials for me! Thank you!

→ Reply
»
6 years 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 ?

→ Reply
  • »
    »
    6 years 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]

    → Reply
»
6 years 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.

→ Reply
»
6 years 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

→ Reply
»
6 years ago, # |
← Rev. 3   Vote: I like it +18 Vote: I do not like it

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

→ Reply
»
6 years 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)

→ Reply
»
6 years 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

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

best editorial indeed

→ Reply
»
4 years ago, # |
  Vote: I like it -16 Vote: I do not like it

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.

→ Reply