Блог пользователя stanislav.bezkorovainyi

Автор stanislav.bezkorovainyi, история, 6 лет назад, перевод, По-русски
Tutorial is loading...

Решение на С++: 46178226

Tutorial is loading...

Решение на С++: 46178084

Tutorial is loading...

Решение на С++: 46178118

Tutorial is loading...

Решение на С++: 46178228

Tutorial is loading...

Решение на С++: 46178239

Tutorial is loading...

Решение на С++: 46178244

Разбор задач Codeforces Round 524 (Div. 2)
  • Проголосовать: нравится
  • +137
  • Проголосовать: не нравится

»
6 лет назад, # |
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

»
6 лет назад, # |
  Проголосовать: нравится -10 Проголосовать: не нравится

вспомагательного

»
6 лет назад, # |
  Проголосовать: нравится +19 Проголосовать: не нравится

Thank you for the timely editorials stanislav.bezkorovainyi.

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится 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.

»
6 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

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

»
6 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

Wow! this Editorial is so detailed. Thank you.

»
6 лет назад, # |
Rev. 2   Проголосовать: нравится +10 Проголосовать: не нравится

nice solutions and editorials for me! Thank you!

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

за разбор лайк

»
6 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

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

  • »
    »
    6 лет назад, # ^ |
    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]

»
6 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
6 лет назад, # |
Rev. 3   Проголосовать: нравится +18 Проголосовать: не нравится

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

»
6 лет назад, # |
  Проголосовать: нравится +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)

»
6 лет назад, # |
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

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

best editorial indeed

»
4 года назад, # |
  Проголосовать: нравится -16 Проголосовать: не нравится

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.