Editorial for DMOPC '20 Contest 6 P3 - Bread Merchant - Olympiads Online Judge

Editorial for DMOPC '20 Contest 6 P3 - Bread Merchant

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

Subtask 1

We model the cities and routes as a digraph (directed graph). For this subtask, the graph has the special structure constraint $a_j \le b_j$ $a_{j} \leq b_{j}$ . Then all edges are either loops (go from a node to itself) or go from a lower-numbered node to a higher-numbered node. Then if we were to remove the loops, the graph would be acyclic. That is, our graph is nearly a DAG (directed acyclic graph).

The standard way to approach game theory problems on a DAG is by dynamic programming. To do this, we need to iterate down from $i=N$ $i = N$ to $i=1$ $i = 1$ . Our dynamic programming will "mark" nodes where the robber will eventually get caught, if they were to start at that node. A node will be left unmarked if the opposite is the case (i.e. the robber can evade capture). There are multiple ways to formulate the dynamic programming, but the following is especially nice:

We always mark nodes with no outgoing edges.
If $p_i=0$ $p_{i} = 0$ , we mark node $i$ $i$ if all outgoing edges lead to marked nodes.
If $p_i=1$ $p_{i} = 1$ , we mark node $i$ $i$ if at least one outgoing edge leads to a marked node.

The time complexity is $\mathcal O(N+M)$ $O (N + M)$ .

Subtask 2

For this subtask, the robber always chooses which edge to take. Then the robber will be caught if all paths eventually lead to a node with no outgoing edges, and the robber will escape if there is a path leading to a cycle.

We can efficiently find which nodes are which using the standard algorithm for topological sort. At a high level, the algorithm deletes nodes that have no outgoing edges, and edges that go to such nodes. The edge deletions cause new nodes to have no outgoing edges, so they too are deleted. The algorithm repeats this until all remaining nodes have at least one outgoing edge. Then starting at any of the remaining nodes, there will always be an edge to take that goes to another of the remaining nodes, thereby allowing the robber to escape forever.

The implementation is the same as is typical for topological sort. We maintain the current out-degrees of all nodes, a set (e.g. a queue) of nodes we are processing. The algorithm uses a "reverse adjacency list" (i.e. an adjacency list of the digraph with edges reversed) to efficiently update the out-degrees.

The time complexity is $\mathcal O(N+M)$ $O (N + M)$ .

Subtask 3

For this subtask, the police always choose which edge to take. So the robber will be caught if and only if a node with no outgoing edges is reachable by any path.

Call the nodes with no outgoing edges the set $S$ $S$ . Consider the digraph obtained by reversing all edges. Then the nodes where a robber will be caught are precisely the nodes reachable starting from $S$ $S$ in the reverse digraph. To find these nodes, it suffices to do a graph search (e.g. BFS).

The time complexity is $\mathcal O(N+M)$ $O (N + M)$ .

Subtask 4

Like in Subtask 1, we will aim to mark exactly the nodes where the robber will eventually get caught. We will use the same three rules:

We mark nodes with no outgoing edges.
If $p_i=0$ $p_{i} = 0$ , we mark node $i$ $i$ if all outgoing edges lead to marked nodes.
If $p_i=1$ $p_{i} = 1$ , we mark node $i$ $i$ if at least one outgoing edge leads to a marked node.

Our algorithm will be to proceed in phases. In each phase, we look at each unmarked node and see if we can apply the rule to mark the node. We stop when a phase makes no changes. Then since a node can be marked only once, there are at most $N$ $N$ phases.

Starting from the unmarked nodes, the robber will be able to escape. This is because for every unmarked node, there is at least one outgoing edge, and the outgoing edge chosen will always go to another unmarked node (whether or not $p_i=0$ $p_{i} = 0$ or $p_i=1$ $p_{i} = 1$ ).

Depending on the implementation, the time complexity will be something like $\mathcal O(NM)$ $O (N M)$ . This approach is similar to the Bellman-Ford algorithm.

Subtask 5

The full solution combines the ideas of Subtasks 2, 3, and 4. That is, the idea of marking nodes, and the proof of correctness, is the same as Subtask 4. However, the implementation is very similar to a combination of topological sort and a graph search, seen in Subtasks 2 and 3.

The implementation first builds an adjacency list of the reverse digraph. It also maintains the marked nodes, the set of nodes yet to be processed (e.g. in a queue), and the current out-degrees of the unmarked nodes. We begin by marking all nodes with no outgoing edges. Then when processing any marked node, we examine all nodes $i$ $i$ with an edge leading into it. If $p_i=1$ $p_{i} = 1$ , then we mark node $i$ $i$ . Otherwise $p_i=0$ $p_{i} = 0$ , and we update the out-degree of $i$ $i$ , and mark it if it changes to zero.

If properly implemented, the time complexity is $\mathcal O(N+M)$ $O (N + M)$ .

Notes

This problem shows that topological sort and typical graph searches (e.g. BFS and DFS) are both special cases of a broader type of algorithm. The algorithm has a specific value $r_u$ $r_{u}$ for each node $u$ $u$ , and visits $u$ $u$ after there are at least $r_u$ $r_{u}$ edges leading to it from already visited nodes.

This problem is an easier version of problem H on the 2018 BAPC contest. That problem has weighted edges, and requires a generalization of Dijkstra's algorithm (like how this algorithm generalizes BFS).

If you want a harder game theory problem on a graph, check out Toy Train. By solving this problem, you have a good foundation to approach it.

Comments

There are no comments at the moment.