Блог пользователя Spheniscine

Автор Spheniscine, история, 4 года назад, По-английски

A – Vanishing Pitch

Spoiler

B – Remove It

Spoiler

C – Digital Graffiti

Spoiler

D – Circle Lattice Points

Spoiler

E – Come Back Quickly

Spoiler

F – GCD or MIN

Spoiler
  • Проголосовать: нравится
  • +35
  • Проголосовать: не нравится

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

Spheniscine For problem F -> how is the rough bound O(M^(1/3)) ? I don't understand the maximum bound of D can someone explain ?

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

    It's just a rough "rule of thumb", the exact values can be found on this page.

    The divisor function is hard to describe usefully in terms of big $$$O$$$, but it can be proven to always be $$$< 3.528 M ^ {1/3}$$$, which can be considered $$$O(M ^ {1/3})$$$

    In theoretical terms it's actually $$$O(M^\varepsilon)$$$ for all $$$\varepsilon > 0$$$, but it converges really slowly.

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

Spheniscine can you explain why this submission has failed for problem D https://atcoder.jp/contests/abc191/submissions/20025093

I followed the editorial but it is still failing on test cases handmade_marginal_00.txt