Think this is supposed to translate to "you can't beat amortized O(log)".

It's unclear to me how you can think of these as independent, particularly since ball $$$b_i$$$ may be overtaken by some other ball than $$$i$$$. Are you making some sort of implicit claim about swapping $$$b_i$$$'s identity with the one that overtook it if that happens? (sort of having $$$b_i$$$ change pointer to wtv ball is right before it rn)?

I think it's super important in G to note that $$$g(0)=0$$$ is a choice one needs to make since once a $$$0$$$ comes along in $$$d$$$, you normally need to take it out. It is then crucial that even if you temporarily kept it in (just for the computation of $$$h$$$), under our assumption of how $$$f$$$ looks like, $$$f(d_1\ldots d_k, 0, d_{k+1}\ldots d_{m-1})=f(d_1\ldots d_{m-1})$$$.

Arguing local behavior is not enough to ensure global optimality. One needs to argue that the function is convex (both for B2 as well as here, but here it's easy to see it by taking cases) for that to be enough (which can be done), but I found that the most important part that I almost missed.

Yes, you are overthinking. For every two intervals to intersect, all of them must intersect. Hence, you can just fix a point, count the intervals containing that point and take the maximum value obtained this way. So (up to normalization), you get Nlog (or even linear if you assume them to be normalized).

Have you tried trading companies? I doubt you aren't aware of them, but check here for a subset of them (I know this is for internships, but they all offer new grad positions as well, and don't know how to navigate the full-time data on levels). I think those appreciate CP much more than others, but getting in is pretty competitive.

I also totally recommend making a linkedin account, from my experience, as you grow your network, you'll be contacted by plenty of recruiters regarding at least vaguely interesting opportunities. I know of people with less interesting backgrounds getting good jobs this way. Regarding visa, it's always easier in Europe than the US so consider applying there as well if you feel adventurous.

Same here. It was an absolutely miserable experience.