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 was 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). The approach to solve it is pretty much the same as above.
These are the only two problems I recall doing binary search on the answer (and it reduces to a problem over $$$0$$$'s and $$$1$$$'s), where I'm not really trying to maximize / minimize things. Just curious if this kind of approach has been used for other problems too.
Auto comment: topic has been updated by arvindr9 (previous revision, new revision, compare).
orz
I was in arvindr9's class and i was amazed by this technique too. Pretty cool (He also gave extra credits related to this problem to make sure we remember it well :D )
I was in ygll's class and I was amazed by the technique as well. Pretty cool
I was in Puddles_Penguin's class and I was amazed by his ability to AK div 1 while spinning a yoyo and solving a rubiks cube blindfolded
This USACO problem uses a similar technique
Median Splits
This problem related to medians also involves similar idea (replacing elements <= k with 1 and elements > k with -1). however editorial's approach doesnt involve binary search. But the problem is still tagged binary search i wonder why. Maybe somebody can explain the binary search idea here.
I was in arvindr9 class and i was amazed by this technique too. Pretty cool (He also gave extra credits related to this problem to make sure we remember it well :D )
Also see https://en.wikipedia.org/wiki/Sorting_network#Zero-one_principle, this is the first time I saw the trick documented. To me, I view it as an extension of the binary search technique. They have the same flavor, generally applies the same way (if you look deep enough)
https://codeforces.me/problemset/problem/1486/D
I also want to contribute with these problems:
Atcoder — F. Count Sorted Arrays
Luogu — MX-S2-T4 换
The same approach is also used to solve this problem from IOI 2010: Day 1, Quality Of Living
Similar idea is used here: https://codeforces.me/contest/2128/problem/E1
I used this technique to solve this problem, although it is not a median-related problem.
my sol :380125001
so tuff now i will be able to solve all median-related problems
yes i agree. anyways here's a hot dog
Also 1993D is a nice non-trivial one
This kind of binarization idea is also useful in lot of counting problem and mostly used together with "Tail-Sum Formula"
$$$E[X] = \sum\limits_{k \gt 0} \Pr[X \ge k]$$$
For r.v. that always evaluate to non-negative integers. ($$$\Pr[X \ge k]$$$ essentially tells you only need to separate elements into "$$$ \lt k$$$" and "$$$\ge k$$$", which is the reason why it fit well with binarization)
For example, this problem.