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}$ ~\text{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^\text{th}~ for the second query.

If the answer to the first query is N, then the MSB will be the $29^\text{th}$ ~29^\text{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)$ ~\mathcal{O}(Q)~

Comments

There are no comments at the moment.