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 will equal 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.