I tried [this problem (AGC 006D, Median Pyramid Hard)](https://atcoder.jp/contests/agc006/tasks/agc006_d) 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 $< x$ as zeros. The pyramid can be simplified to consist of zeros and ones, and the goal is to check if the top elementcan be awill 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)](https://codeforces.me/contest/2229/problem/D). 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.
↵
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 $< x$ as zeros. The pyramid can be simplified to consist of zeros and ones, and the goal is to check if the top element
↵
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)](https://codeforces.me/contest/2229/problem/D). 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.
