I started competing in contests a while back to get an edge in interviews. After enough practice, I got what I wanted — but now I'm at a phase where I'm looking for things to do, to find some meaning in day-to-day life.

I've found that my motivation to sit the full duration of a contest and try my hardest to solve what challenges me is gone, since my biggest initial motivation was achieved.

I want to hear why you compete, in the hope that I can resonate with it and find new resolve to compete and take it as seriously as I once used to.

Hi,

I've seen a large chunk of my upsolving/practice time goes into trying to learn how to implement algorithms or data structures from scratch (like KMP/suffix arrays etc) when I encounter these new algorithms.

I understand — albeit at a high level — how/why the implementations work, but is it important to spend time perfecting one's ability to implement these from scratch when I already know how to apply them to most applications?

What are the scenarios where not knowing how to implement from scratch handicaps you where a template won't save you? Algorithmic interviews? Would I ever need to worry about implementing such algorithms there?

While solving this problem from CSES — Hamming Distance — I was surprised to see that my O(N^2) solution passed where N = 2e4. The solution wasn't pruned so I'm sure it must've taken ~ N^2 operations.

What exactly is a good estimate on number of operations allowed? I believed 3e7 operations was a good estimate, but clearly this isn't the case, so what is the actual threshold?

Hi, I was trying to solve atcoder's ABC191 problem D

Problem statement - Given X, Y, R that define a circle centered at (X, Y) with radius R, find the number of grid points whose x- and y-coords are integers, that lie within or on the circle.

Constraints are: |X|, |Y|, R < 1e5 (X, Y, and R can be floating point values upto 4 decimal places)

Approach used -

The equation of a circle is (x-a)^2 + (y-b)^2 = R^2 for a circle centered at (a, b)

So I figure the qn wants me to solve the integral solutions to (x-a)^2 + (y-b)^2 <= R^2

I isolate (y-b)^2 and iterate over all candidate values of x from [-a-R-1, a+R+1] and compute the lower and upper bound of y and add them all up and output them.

For some reason this fails on some tests — I observed this is also pretty different from the editorial approach. Is there something fundamentally wrong with my idea/code?

Code -

a, b, r = [float(i) for i in input().split()]
'''
(x-a)^2 + (y-b)^2 <= r^2
=> (y-b)^2 <= r^2 - (x-a)^2

k = r^2 - (x-a)^2
y <= sqrt(K)+b
y >= b-sqrt(K)
'''
ans = 0
from math import floor, ceil
for x in range(-int(a)-int(r)-2, int(a)+int(r)+3):
    k = r*r - (x-a)**2
    if k<0:
        continue
    ans += max(0, 1 + floor(k**0.5 + b) - ceil(b-(k**0.5)))
print(ans)

Reading through this DP blogpost by zscoder — https://codeforces.me/blog/entry/47764

In the "open and close interval" section, the blogpost explains this problem — https://codeforces.me/contest/626/problem/F

The explanation says -

"Suppose there are j open sets. When we add a[i], the sum a[i] - a[i - 1] will contribute to each of the j open sets, so we increase the current imbalance by j(a[i] - a[i - 1])."

But doesn't this imply that all j open sets contain a[i-1]?

Shouldn't the correct net increase in imbalance be - sum(a[i] - max(cur_open_set)) // (assuming we somehow tracked the max for each cur_open_set)

But for my equation to be equal to j*(a[i]-a[i-1]), all the current open sets would need to have a[i-1] in them. So how does this work?

Basically I'm unable to understand the transition of the 3rd state in the DP equation in the blogpost. If anyone can help clarify my misunderstanding or explain it in a different way, I'd be grateful!

Please help! Thanks!