Decent contest. Started 6 min late bc I lost track of time while debugging some cses problem :/ but it was fine..

ABC were basically trivial, C had a pretty simple pattern (provable by optimal-choice argument) which I got relatively quickly. D was an adventure, though.

Task essentially asks us to determine in a 2d bitfield the first set bit encountered when starting at some cell and moving purely up, down, left, or right. For some reason I thought first of some binlift-adjacent approach, but that was obviously too much work and not really worth it to impl. Spent a while writing up some bashy sol that mantained a segment tree for each row and column. I spent way too long implementing this AND ALSO got 3 RE because I swapped X bound and Y bound in coordinate bounds check. smh.

E was pretty interesting, but I didn't see the dp. F was another dp that I couldn't think of a speedup for, and G was basically impossible.

"binlift search"

Because of my semi-attempt at using not exactly binlifting on D, my binary search (to find closest unset cell on segment) ended up looking somewhat like this:

int i = initial;

for(int p = 20; p; --p)
    if(works(i + (1<<p))) i += 1<<p;

// to search backwards, replace + with -

Is this faster than normal binsearch? The operations are probably mostly identical, but idk. probably no difference. It actually reminds me a lot of fenwick search, but this is simpler surely..

Additionally, it can be made branchless pretty easily, I think:

int i = initial;

for(int p = 20; p; --p)
    i += works(i + (1<<p)) << p;

idk how well this works with cache and stuff though. Definitely loses to Algorithmica's eytzinger-layout based binary search.

tags: programming atcoder contest-logs