Editorial for DMOPC '17 Contest 4 P5 - Revised IOI - Olympiads Online Judge

Editorial for DMOPC '17 Contest 4 P5 - Revised IOI

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

The key observation to this problem is that if the four contestants answer the exact same answers to two different questions, then the answers to those two questions should be the same in the optimal answer key. Since there are only $2^4$ $2^{4}$ possible ways for the contestants to answer a question, we can reduce the number of variables from $N$ $N$ to $2^4$ $2^{4}$ , each of which can only be $-1$ $- 1$ or $1$ $1$ . As such, there are $2^{2^4}$ $2^{2^{4}}$ answer keys which should be checked.

Time Complexity: $\mathcal O(2^{2^M}+N)$ $O (2^{2^{M}} + N)$

where $M$ $M$ is the number of contestants (a constant in this problem).

Comments

There are no comments at the moment.