Editorial for COCI '09 Contest 6 #5 Holmes
Submitting an official solution before solving the problem yourself is a bannable offence.
This task cannot be solved by simply finding dominators for the graph. But it's not far away. The following example illustrates the problem with dominators:
4 4 1
1 3
2 3
1 4
2 4
3
Event 3 is proven by the Yard. Event 3 can be caused by either event 1, event 2 or both. Even though we do not know which one, note that one of them had to be. Since event 4 can be caused by either event 1, event 2 or both, this means that event 4 is also part of the solution. Even though we do not know the exact cause.
Let us see how we can approach this problem. First, we add all events proven by Scotland Yard to the solution. This is a no-brainer. Then, we flood fill from them, adding all "consequences" of proven events to the solution. This leaves "causes" and "consequences of causes". For each not yet proven event, we try to prove it by contradiction. We start by supposing that event X could not have happened. Then we optimistically presume all other events that do not cause event X to happen to have happened. This now leaves a set of events leading to X and some leading from X marked as "did not happen". If one of the proven events ends up "not happened" this is a contradiction and we can surmise that event X had to have happened.
How can we check this quickly? For each event X, we can iterate through all other events Y. If the set of "causes" of X contains all "causes" of Y then Y must not have happened. "causes" is the minimal set of events that can cause X. Note that all "causes" do not contain entry edges. Causes for each event can be precomputed ahead of time.
On a side note, talking in past perfect conditional tense in English is extremely confusing.
Comments