Editorial for The Contest Contest 1 P1 - A Typical Codeforces Problem - Olympiads Online Judge

Editorial for The Contest Contest 1 P1 - A Typical Codeforces Problem

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: linx

Hint

The $(i + 1)^{\text{th}}$ ~(i + 1)^{\text{th}}~ tester can be forced to vote yes if the first $i$ ~i~ testers vote yes and another tester $c$ ~c~, $c > i$ ~c > i~ votes yes.

Full Solution

For every tester $k$ ~k~ that votes yes, it is possible to force every tester $i$ ~i~, $i < k$ ~i < k~ to vote yes. By selecting only tester $k$ ~k~ for the interval, there is one yes and so tester $1$ ~1~ must vote yes. From the hint, it follows that tester $2$ ~2~ can be forced to vote yes, then tester $3$ ~3~, and so on until tester $k$ ~k~. Therefore, it is possible to force a majority of the testers to vote yes if there exists a tester $c$ ~c~, $c > \lfloor \frac{N}{2} \rfloor$ ~c > \lfloor \frac{N}{2} \rfloor~ who votes yes.

Time Complexity: $\mathcal{O}(N)$

Comments

There are no comments at the moment.