Intuition behind Problem D of Educational Codeforces Round 140
Difference between en1 and en2, changed 120 character(s)
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>↵

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English Kohinoor 2022-12-17 07:13:23 120 (Edit) Motivation
en1 English Kohinoor 2022-12-17 06:19:26 1222 First publish (published)