Editorial for TLE '17 Contest 5 P6 - Circuits
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.
Submitting an official solution before solving the problem yourself is a bannable offence.
Author:
This problem was taken from problem G of the 2001 ACM Central Europe Programming Contest.
A solution with explanation at the top is available here.
It was chosen due to the almost intentionally misleading setup: this type of mental twists are quite hard to set.
In retrospect the main trickiness in this problem are:
- The answer always being 0 or 1
xsignificantly changes the problem. - One has to almost guess the format of the answer based on 1.
- Instead of examining the circuit component by component (via some kind of backwards dynamic program), the solution treats it as a black box and searches over it.
Comments