Spheniscine's blog

By Spheniscine, history, 3 years ago,

Spoiler

Spoiler

Spoiler

Spoiler

Spoiler

F – GCD or MIN

Spoiler
• +35

 » 3 years ago, # |   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 ?
•  » » 3 years ago, # ^ |   +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.
•  » » » 3 years ago, # ^ |   0 Thanks for the explanation
 » 3 years ago, # |   0 Spheniscine can you explain why this submission has failed for problem D https://atcoder.jp/contests/abc191/submissions/20025093I followed the editorial but it is still failing on test cases handmade_marginal_00.txt
•  » » 3 years ago, # ^ | ← Rev. 2 →   0 I don't have a C++ debugger handy but might I ask why you have +1 and -1 in these lines:  LL high = Y + 1; LL low = Y - 1; 
•  » » » 3 years ago, # ^ |   0 It might be redundant but I think I added it to be on the safer side
•  » » » » 3 years ago, # ^ | ← Rev. 2 →   0 I don't know if it's safer or might be causing the issue. Note that the partial result for some rows can actually be zero, if the circle crosses the line but doesn't actually include any lattice points.
•  » » » » » 3 years ago, # ^ |   0 Spheniscinewell I tried this and it worked but I don't understand why it was failing earlierhttps://atcoder.jp/contests/abc191/submissions/20025313