Editorial for The Contest Contest 1 P6 - A Typical DMOPC Problem

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

Subtask 1

For the remainder of the editorial, we'll let $\text{deg}(x)$ ~\text{deg}(x)~ denote the degree of node $x$ ~x~.

Since the graph is a tree, there exists a unique path from node $1$ ~1~ to $N$ ~N~. Observe that in order for Alice to always reach node $N$ ~N~, this path must be a line graph. That is, $\text{deg}(1) = 1$ ~\text{deg}(1) = 1~ and every intermediate node on the path must have degree $2$ ~2~.

Why is this? Consider what happens if Alice arrives at a node $n \ne N$ ~n \ne N~ with $\text{deg}(n) \ne 2$ ~\text{deg}(n) \ne 2~. If $\text{deg}(n) = 1$ ~\text{deg}(n) = 1~, Alice is at a dead end and can't continue. If $\text{deg}(n) \ge 3$ ~\text{deg}(n) \ge 3~, Alice chooses between two edges, of which only one of them is on the path to node $N$ ~N~. No matter how Alice reaches node $n$ ~n~, there is always the possibility of Alice not taking the edge on the path to node $N$ ~N~.

Once we determine if the path satisfies the above requirements, any assignment of edge weights should suffice since Alice's path is already predetermined.

Time Complexity: $\mathcal{O}(N)$

Subtask 2 Hint

Build a graph where every node can reach node $N$ ~N~.

Subtask 2

In this subtask, Alice always chooses between $2$ ~2~ edges at each node.

Consider a directed acyclic graph $G$ ~G~ of maximal size with the following properties:

Node $N$ ~N~ is in $G$ ~G~ and has an outdegree of $0$ ~0~
Every node $x \in G$ ~x \in G~ excluding node $N$ ~N~ has an outdegree of exactly $2$ ~2~

It follows that if Alice starts at a node in $G$ ~G~, she can always be forced to reach node $N$ ~N~ since we can set the $2$ ~2~ outgoing edges to be the min and max edge at her current node. Furthermore, if Alice doesn't start in $G$ ~G~, we cannot guarantee that Alice can always reach node $N$ ~N~. Why? Since no matter how she got to that node, she will choose between $2$ ~2~ edges, of which at most $1$ ~1~ of them takes her into $G$ ~G~. This means she can always take an edge to some node not in $G$ ~G~. This results in an infinite loop, so Alice can never reach node $N$ ~N~.

Thus, we want to determine if node $1$ ~1~ is in $G$ ~G~. This inspires us to run our own version of topological sort.

We try to construct $G$ ~G~, which initially only contains node $N$ ~N~. On each iteration, we find a node $x$ ~x~ that has at least $2$ ~2~ edges connecting to nodes in $G$ ~G~. If such an $x$ ~x~ exists, we add it and the $2$ ~2~ edges we used to $G$ ~G~, where the $2$ ~2~ edges become outgoing edges from $x$ ~x~. We repeat this process until node $1$ ~1~ is in $G$ ~G~ or there are no more nodes to add.

How can we assign edge weights to maintain these properties? When we add the $2$ ~2~ edges to $G$ ~G~, we can set their weights to be the minimum and maximum unused edge weights (call them $a$ ~a~ and $b$ ~b~ respectively with initial values of $1$ ~1~ and $M$ ~M~). This works because when we label the remaining edges that connect to node $x$ ~x~, they will have a weight strictly between $a$ ~a~ and $b$ ~b~. Hence Alice will still pick the same edges, no matter how she arrived at node $x$ ~x~.

If node $1$ ~1~ is in $G$ ~G~ after running the "topological sort", we simply label the remaining edges with weights in the interval $[a,b]$ ~[a,b]~ and we're done. Otherwise, there is no solution.

Time Complexity: $\mathcal{O}(N+M)$

Subtask 3 Hint

What happens if Alice visits node $1$ ~1~ again? When would this make a difference?

Subtask 3

In this subtask, the number of edges Alice chooses at each node can vary. We let $c(x)$ ~c(x)~ represent the number of edges Alice could take if she was at node $x$ ~x~. We have:

$\displaystyle c(x) = \begin{cases} \min(\text{deg}(x), 2) & \text{if } x = 1 \\ \min(\text{deg}(x)-1, 2) & \text{otherwise} \end{cases}$

To accomodate this, we modify the second requirement of $G$ ~G~ so that every node $x \in G, x \ne N$ ~x \in G, x \ne N~ has an outdegree of exactly $c(x)$ ~c(x)~.

We first run the same process described in subtask 2 but with some slight modifications to account for when $c(x) \ne 2$ ~c(x) \ne 2~. If this does not yield a solution, there is one remaining case to check for. To see it, we make the following observations:

Let's examine node $1$ ~1~ and the definition of $c(1)$ ~c(1)~. When Alice is initially at node $1$ ~1~, $c(1) = \min(\text{deg}(x), 2)$ ~c(1) = \min(\text{deg}(x), 2)~. However, if Alice arrives at node $1$ ~1~ again, we now have $c(1) = \min(\text{deg}(1)-1, 2)$ ~c(1) = \min(\text{deg}(1)-1, 2)~. In particular, the value of $c(1)$ ~c(1)~ changes if $\text{deg}(1) = 1$ ~\text{deg}(1) = 1~ or $\text{deg}(1) = 2$ ~\text{deg}(1) = 2~. If $\text{deg}(1) = 1$ ~\text{deg}(1) = 1~, Alice will stop at node $1$ ~1~ so this doesn't work. If $\text{deg}(1) = 2$ ~\text{deg}(1) = 2~, there are two cases. Let $g(x)$ ~g(x)~ denote the number of edges that connect a node $x \notin G$ ~x \notin G~ to a node in $G$ ~G~. If $g(1) = 0$ ~g(1) = 0~, there is still no solution. However, if $g(1) = 1$ ~g(1) = 1~, a solution may exist. Starting from node $1$ ~1~, Alice could either take the edge that leads to $G$ ~G~ or take the other edge. If Alice takes the latter edge, it is possible for Alice to eventually be forced to either take an edge that goes into $G$ ~G~ or take this edge back to node $1$ ~1~, which forces her into $G$ ~G~.

To check for this case, we again run the "topological sort" described in subtask 2, except this time we define $c(1)$ ~c(1)~ to be $\min(\text{deg}(1)-1, 2) = 1$ ~\min(\text{deg}(1)-1, 2) = 1~. Furthermore, we let $\text{ins}(x)$ ~\text{ins}(x)~ denote the order of when node $x$ ~x~ was added to $G$ ~G~. Thus, $G$ ~G~ has the following additional properties:

$\text{ins}(N) = 1$ ~\text{ins}(N) = 1~
For all $x \in G$ ~x \in G~, the $c(x)$ ~c(x)~ outgoing edges from node $x$ ~x~ connect to nodes with lower $\text{ins}$ ~\text{ins}~ values.

We claim that a solution exists if and only if the following conditions hold:

There exists an edge $e$ ~e~ connecting nodes $u$ ~u~ and $v$ ~v~, where $u,v \in G$ ~u,v \in G~ and $e \notin G$ ~e \notin G~. WLOG $\text{ins}(u) < \text{ins}(v)$ ~\text{ins}(u) < \text{ins}(v)~.
Let $\{s_i\}_{i \in \mathbb{N}}$ ~\{s_i\}_{i \in \mathbb{N}}~ represent the sequence of nodes on a path of length $k$ ~k~ from node $1$ ~1~ to node $u$ ~u~ ( $s_1 = 1$ ~s_1 = 1~ and $s_k = u$ ~s_k = u~), where $\text{ins}(s_1) < \text{ins}(s_2) < \ldots < \text{ins}(s_k)$ .
Then let $\{p_i\}_{i \in \mathbb{N}}$ ~\{p_i\}_{i \in \mathbb{N}}~ denote the sequence of edges on this path, where $p_i$ ~p_i~ is the edge she takes to get from node $s_i$ ~s_i~ to $s_{i+1}$ ~s_{i+1}~. This path must exist and $\{s_i\}, \{p_i\} \in G$ ~\{s_i\}, \{p_i\} \in G~.

In addition, we have a process of determining such $\{s_i\}, \{p_i\}$ ~\{s_i\}, \{p_i\}~, if they exist.

Proof of claim and outline of process

Consider the following process of determining a possible $\{s_i\}$ ~\{s_i\}~ and $\{p_i\}$ ~\{p_i\}~:

The base case is when Alice starts at node $s_1 = 1$ ~s_1 = 1~. Recall that $\text{deg}(1) = 2$ ~\text{deg}(1) = 2~ so she has two choices:

Take the edge that connects to the node in $G$ ~G~ with the lower $\text{ins}$ ~\text{ins}~ value. She is now guaranteed to reach node $N$ ~N~.
Take the edge that connects to a node in $G$ ~G~ with the higher $\text{ins}$ ~\text{ins}~ value. Call this node $s_2$ ~s_2~.

Now suppose that Alice is at some node $s_i$ ~s_i~, $i \ge 2$ ~i \ge 2~, where $p_{i-1}$ ~p_{i-1}~ (the edge she took to get to $s_i$ ~s_i~) is in $G$ ~G~ and $\text{ins}(s_i) > \text{ins}(s_{i-1})$ ~\text{ins}(s_i) > \text{ins}(s_{i-1})~. Notice that there are now $c(s_i)-1$ ~c(s_i)-1~ outgoing edges Alice could take to be guaranteed to reach node $N$ ~N~, since $p_{i-1}$ ~p_{i-1}~ is one of the $c(s_i)$ ~c(s_i)~ outgoing edges and she can't take the same edge consecutively. Hence, Alice could take one other edge. Call this edge and the node it leads to as $p_i$ ~p_i~ and $s_{i+1}$ ~s_{i+1}~ respectively. We consider the possible cases:

Case 1: $p_i \in G$ ~p_i \in G~
We have $s_{i+1} \in G$ ~s_{i+1} \in G~ and $\text{ins}(s_{i+1}) > \text{ins}(s_i)$ ~\text{ins}(s_{i+1}) > \text{ins}(s_i)~, so we continue the process with node $s_{i+1}$ ~s_{i+1}~.
Case 2: $p_i \notin G$ ~p_i \notin G~
Observe that this edge must connect to a node in $G$ ~G~ (that is, $s_{i+1} \in G$ ~s_{i+1} \in G~). If this wasn't the case, when Alice arrives at node $s_{i+1}$ ~s_{i+1}~ she is not guaranteed to reach node $N$ ~N~ (recall that a node is in $G$ ~G~ iff she is guaranteed to reach node $N$ ~N~ from that node). Next, observe that if Alice took edge $p_i$ ~p_i~ to $s_{i+1}$ ~s_{i+1}~, she is guaranteed to reach node $N$ ~N~ since she can be forced to take any of the $c(s_{i+1})$ ~c(s_{i+1})~ outgoing edges from node $s_{i+1}$ ~s_{i+1}~. We take $k$ ~k~ to be $i$ ~i~, $u$ ~u~ to be $s_i$ ~s_i~, $v$ ~v~ to be $s_{i+1}$ ~s_{i+1}~, $e$ ~e~ to be $p_i$ ~p_i~ and we're done.

Since $G$ ~G~ is finite and $\text{ins}(s_1) < \text{ins}(s_2) < \ldots < \text{ins}(s_i) < \ldots$ , at some point we must reach case 2 and terminate the process.

Using the process outlined in the above proof, we can find a possible $\{s_i\}$ ~\{s_i\}~ and $\{p_i\}$ ~\{p_i\}~ by performing a DFS traversal starting from node $1$ ~1~. Implementation is left as an exercise to the reader. If such $\{s_i\}$ ~\{s_i\}~ and $\{p_i\}$ ~\{p_i\}~ exist, we rerun "topological sort" in order to relabel the edges. The following modifications are made:

Initialize $b$ ~b~ (recall $b$ ~b~ is the maximum unused edge weight) as $M-k+1$ ~M-k+1~, since we reserve $M-k+2,\ldots,M$ ~M-k+2,\ldots,M~ for labelling edges in $\{p_i\}$ ~\{p_i\}~.
$c(1) = \min(\text{deg}(1)-1, 2) = 1$ ~c(1) = \min(\text{deg}(1)-1, 2) = 1~
If the current node $x = s_i$ ~x = s_i~ for some $i \ge 2$ ~i \ge 2~, we know that one of the outgoing edges is $p_{i-1}$ ~p_{i-1}~. Set the weight of $p_{i-1}$ ~p_{i-1}~ to be $M-i+1$ ~M-i+1~. If $c(x) = 2$ ~c(x) = 2~, set the other edge to be the minimum unused edge. After labelling, the edges $p_1, p_2, \ldots, p_{i-2}, p_{i-1}, e$ ~p_1, p_2, \ldots, p_{i-2}, p_{i-1}, e~ will have weights of $M, M-1, \ldots, M-k+3, M-k+2, M-k+1$ ~M, M-1, \ldots, M-k+3, M-k+2, M-k+1~ respectively.

This assignment of edge weights guarantees that Alice must always reach node $N$ ~N~, the proof of which is left as an exercise for the reader.

Time Complexity: $\mathcal{O}(N+M)$ ~\mathcal{O}(N+M)~

Comments

There are no comments at the moment.