r/codeforces • u/leetgoat_dot_io • Mar 02 '26
meme Qinshi Wang is the legend you've never heard of
In 2016 a problem called "Aliens" appeared at the IOI - the world championships of competitive programming. Out of the 300+ people who competed in this two-day tournament, only one scored full points on this question.
"Aliens" became so famous that the technique used to solve it became known as the "alien trick". It's a form of lagrangian relaxation and binary search, which drops a complexity factor on hard dynamic programming questions. It took me 4 hours to understand this weekend.
Except "alien trick" was not new. It had been discovered 4 years earlier. Qinshi Wang published a paper about it in 2012 when he was 17. In China, it was known as "WQS binary search", named after his initials.
Here's some problems you can solve with WQS binary search:
https://cses.fi/problemset/task/2087/ https://leetcode.com/problems/minimum-partition-score/description/ https://codeforces.com/contest/321/problem/E https://cses.fi/problemset/task/2087/
