Editorial for IOI '18 P4 - Mechanical Doll

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.

Subtask 1

Connect triggers without switches.

Subtask 2

Put a switch after each trigger which appears twice.

Subtask 3

For each trigger which appears more than twice, use $3$ ~3~ switches to branch its exit into $4$ ~4~ exits (Imagine a balanced binary tree). For each trigger which appears $3$ ~3~ times, kill one out of the first $3$ ~3~ exits by connecting it to the "root" switch.

Subtask 4

Gather exits of all the triggers into one, and branch it into $16$ ~16~ exits with $15$ ~15~ ( $= 2^4-1$ ~= 2^4-1~) switches.

Subtask 5

(Solution A) ( $2N$ ~2N~ switches, half score) Use $2^k-1$ ~2^k-1~ switches for $k$ ~k~ such that $2N > 2^k \ge N$ ~2N > 2^k \ge N~, and kill excessive exits by connecting them to the "root" switch.
( $N+\log_2 N$ ~N+\log_2 N~ switches, full score) In addition to Solution A, skillfully choose which exits to kill so that they are closely placed in the circuit. Then many switches are now unnecessary because their exits are both connected to the "root" switch.

Subtask 6

( $2N$ ~2N~ switches, half score) Do Solution A for every trigger.
(Solution B) ( $2N$ ~2N~ switches, half score) Gather exits of all the triggers into one, and branch it using Solution A.
( $N+\log_2 N$ ~N+\log_2 N~ switches, full score) In addition to Solution B, save switches by skillfully choosing which exits to kill.

Comments

There are no comments at the moment.