Editorial for April Fools' Day Contest 1 P8 - NP-Hard

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: maxcruickshanks

Realize that the encryption is not strong since the most significant bit (MSB) differs with $\text{lastAns}$ $lastAns$ for Y and N queries.

Consider the first query:

If the answer to the first query is Y, then the MSB will be the $30^\text{th}$ $30^{th}$ for the second query.

If the answer to the first query is N, then the MSB will be the $29^\text{th}$ $29^{th}$ for the second query.

This logic can be extended for all queries except the last since the encryption is unknown for the last query.

However, since there are only $2$ $2$ test cases, it suffices to output a random answer for the last query (the probability of AC is $\frac{1}{4}$ $\frac{1}{4}$ ).

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

Comments

There are no comments at the moment.