I tried this problem (AGC 006D, Median Pyramid Hard) a few months ago. The problem gives an array of $$$N$$$ integers ($$$N \leq 10^5$$$), and makes a pyramid over that, where each entry is the median of the three elements below it. The goal is to find the value at the top cell of the pyramid.

I remembered struggling on it for hours. When nothing was working, I was just trying a bunch of random things and decided to try binary searching on the answer (BSTA). Surprisingly it worked!

The idea is to consider asking the question "Is the answer $$$\geq x$$$?". Then you can treat all the elements $$$\geq x$$$ as ones, and all the elements $$$ \lt x$$$ as zeros. The pyramid can be simplified to consist of zeros and ones, and the goal is to check if the top element can be a one, which is much more doable.

This blew my mind, since in the past, I viewed BSTA as a technique for maximization / minimization problems. But here it could be used to calculate something related to a median. I thought this problem quite cool, so I assigned it as a bonus problem for some of my classes.

It turns out the same technique works for this recent problem (problem D from the recent Spectral Cup, Me When Median Problem). It's pretty much the same as above.

These are the only two problems I recall doing binary search on the answer, where I'm not really trying to maximize / minimize things. Just curious if this kind of approach has been used for other problems too.