Editorial for DMOPC '21 Contest 7 P3 - Whack-an-Ishigami

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

Subtask 1

Since the graph is a DAG, we never have cycles that would cause us to lose. We maintain a boolean array, initially empty, indicating the parity of the number of times each node has been flipped. Then we process nodes in order, and flip if the flip parity differs from the initial state of the node.

Subtask 2

We can repeat the following process: use BFS/DFS to determine which node to flip. If node $B$ is reachable from $A$ , it is optimal to flip $A$ instead of $B$ (similar to Subtask 1). If during the BFS of $A$ we find any sort of cycle, and $A$ is up at the beginning, output -1. Once we decide what node to flip, we can flip any one of them, and use BFS to update the counts. Make sure to keep a visited array at each step to avoid degrading into $\mathcal O(N^3)$ . Furthermore, note that we only need to perform the previous step at most $N$ times.

Hint

What do we know about nodes of outdegree $0$ ?

Hint 2

What happens if we repeatedly prune nodes with outdegree $0$ ?

Subtask 3

Note that if a node has outdegree $0$ , then it clearly can't cause us to lose if we flip it. Furthermore, if all children of a node can't cause us to lose, then neither can flipping this node. Basically, we can prune nodes of outdegree $0$ until we don't have any nodes with such degree left. Now, flipping any node in the graph we have left will cause us to lose. We can check that all of the remaining nodes are flipped down. Then, it remains to process the nodes we removed to count the minimum number of flips. Note that the nodes we removed must form a DAG. Thus, we can process them like Subtask 1. Note that of the nodes pruned in the first step, parents are always pruned after their children, so we can process in reverse-pruned-order, just as we did in Subtask 1.

Comments

There are no comments at the moment.