Motivation: Some people enquired me how could I write a six-line code to solve this problem. Here's the intuition... ↵
↵
<spoiler summary="Spoiler">↵
↵
↵
**Visualizing the Playoffs as a tree**, ↵
↵
I devised a necessary condition for 'x' to be a winner.↵
↵
Let's consider the case of ones, as the case of zeroes is analogous.↵
↵
Define **skill(x) = s(x)** . ↵
↵
Define **n(l) = No. of players with skill less than x, who lost at lth (one)level from the top**.↵
↵
- At the highest **one**, x defeated a player x1 with s(x1) < s(x). [n(1) = 1 = 2^0]↵
↵
- Now, consider the second highest **one**, both x and x1 must have defeated players x2 and x3 with skill s(x2)<s(x) and s(x3)<s(x1). This also implies that s(x)>s(x3), s(x2). So at this level, we get 2 more players with smaller skills than x. [n(2)= 2 = 2*n(1)]↵
↵
- Inductively, we can see that [n(h) = 2*n(h-1) = 2^(h-1)], where h is the number of ones in the binary string given.↵
↵
So, We get that x is greater than a set of numbers with cardinality at least 1 + 2^1 + 2^2 + ... + 2^(h-1).↵
↵
↵
↵
Similarly in **zeroes**,↵
We get that x is smaller than a set of numbers with cardinality at least 1 + 2^1 + 2^2 + ... + 2^(z-1). where z is the number of zeroes in the binary string given.↵
↵
↵
</spoiler>↵
↵
↵
<spoiler summary="Spoiler">↵
↵
↵
**Visualizing the Playoffs as a tree**, ↵
↵
I devised a necessary condition for 'x' to be a winner.↵
↵
Let's consider the case of ones, as the case of zeroes is analogous.↵
↵
Define **skill(x) = s(x)** . ↵
↵
Define **n(l) = No. of players with skill less than x, who lost at lth (one)level from the top**.↵
↵
- At the highest **one**, x defeated a player x1 with s(x1) < s(x). [n(1) = 1 = 2^0]↵
↵
- Now, consider the second highest **one**, both x and x1 must have defeated players x2 and x3 with skill s(x2)<s(x) and s(x3)<s(x1). This also implies that s(x)>s(x3), s(x2). So at this level, we get 2 more players with smaller skills than x. [n(2)= 2 = 2*n(1)]↵
↵
- Inductively, we can see that [n(h) = 2*n(h-1) = 2^(h-1)], where h is the number of ones in the binary string given.↵
↵
So, We get that x is greater than a set of numbers with cardinality at least 1 + 2^1 + 2^2 + ... + 2^(h-1).↵
↵
↵
↵
Similarly in **zeroes**,↵
We get that x is smaller than a set of numbers with cardinality at least 1 + 2^1 + 2^2 + ... + 2^(z-1). where z is the number of zeroes in the binary string given.↵
↵
↵
</spoiler>↵
↵
