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)th tester can be forced to vote yes if the first i testers vote yes and another tester c, c>i votes yes.

Full Solution

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

Time Complexity: O(N)

Comments

There are no comments at the moment.