Spheniscine's blog

By Spheniscine, history, 3 years ago, In English

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
  • Vote: I like it
  • +35
  • Vote: I do not like it

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

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 ?

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

    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.

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

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