USACO 2022 US Open Contest, Platinum Problem 2. Hoof and Brain

USACO 2022 US Open Contest, Platinum Problem 2. Hoof and Brain

Given a directed graph with NN vertices and MM edges (2≤N≤1052≤N≤105, 1≤M≤2⋅1051≤M≤2⋅105), Farmer John's cows like to play the following game with two players.

Place two tokens on distinct nodes in the graph. Each turn, one player, the brain, will choose a token that must be moved along an outgoing edge. The other player, the hoof, will choose which edge to move the token along. The two tokens can never be on the same node. If at some point the hoof can't make a valid move, the brain wins. If the game continues indefinitely, the hoof wins.

You are given QQ queries (1≤Q≤1051≤Q≤105) indicating the starting nodes of the two tokens. For each query, output which player will win.

 

INPUT FORMAT (input arrives from the terminal / stdin):
The first line contains NN and MM.The next MM lines each contain two integers aa and bb, denoting an edge from aa to bb.

The graph does not contain self-loops or multiple edges.

The next line contains QQ.

The final QQ lines each contain two integers xx and yy satisfying 1≤x,y≤N1≤x,y≤N and x≠yx≠y, indicating the starting nodes of the tokens.
OUTPUT FORMAT (print output to the terminal / stdout):
A string of length QQ, where each character is B for the brain winning and H for the hoof winning.
**Note: the time limit for this problem is 4s, twice the default.**

 

SAMPLE INPUT:
9 10
1 2
2 3
3 4
4 7
3 5
1 6
6 8
8 9
9 6
7 2
4
1 5
1 2
1 6
2 4

SAMPLE OUTPUT:
BHHB

The brain can win the first game by selecting node 5; then the hoof has no valid move.

The brain can win the last game by selecting node 4 and then node 7; then the hoof has no valid move.

The hoof wins the other games.

 

SCORING:
Test cases 2-3 satisfy N≤100N≤100, M≤200M≤200.
Test cases 4-9 satisfy N≤5000N≤5000.
Test cases 10-21 satisfy no additional constraints.

Problem credits: Danny Mittal

USACO 2021 December Contest, Gold Problem 2. HILO 题解(翰林国际教育提供，仅供参考)

题解请注册或登录查看

[/hide]

(Analysis by Danny Mittal)Subtask 1: N≤100N≤100, M≤200M≤200

We can solve this subtask by creating a new graph of pairs of nodes from the old graph, where each pair (a,b)(a,b) represents a game state where one token is on aa and one token is on bb. We can perform a search where we repeatedly remove nodes that are winning for the brain.

In order to do this, we maintain for each pair (a,b)(a,b) the amount of remaining pairs (c,b)(c,b) such that a→ca→c is an edge in the original graph, and a similar amount of remaining pairs (a,c)(a,c). In the process of removing pairs, if one of these amounts becomes 00 for a certain pair (a,b)(a,b), then the brain can choose that token in order to win, so we remove (a,b)(a,b) as well, then decrement the amounts for the appropriate other pairs by looking at incoming edges to aa and bb.

At the end of this process, any remaining pairs represent game states from which the brain cannot win. We can then answer queries by simply checking whether they are a pair that was removed or not.

The bottleneck in this algorithm is the part after removing a pair when we decrement the other appropriate pairs' amounts. Each edge a→ca→c is potentially considered as part of pairs (c,b)(c,b) and (b,c)(b,c) for all bb, making the worst case runtime O(N)O(N) per edge and so O(NM)O(NM) overall. This is far under the time limit, so less efficient variants of this solution could also have passed.

Subtask 2: N≤5000N≤5000

First note that if a node with a token on it has no outgoing edges, then the brain can win by simply choosing the token on that node to leave the hoof without any moves. This means that we can mark the nodes as such and then simply remove them from the graph. Furthermore, any nodes that now have no outgoing edges also represent a win for the brain, because the brain can repeatedly choose the token on those nodes, and eventually the token will reach a node with no outgoing edges. Therefore, we can repeatedly remove all nodes with no outgoing edges from the graph until all nodes remaining have at least one outgoing edge.

Now, consider a node aa with only a single outgoing edge to a different node bb. Any token on aa can clearly be moved to bb. This means that we don't need to really consider aa as being separate from bb; if the brain can force the hoof to lose by making it so that both tokens would end up at aa, the brain can also just force the hoof to lose by making it so that both tokens would end up at bb, by making each token move once more. Therefore, we can "merge" aa into bb, meaning that bb inherits all of aa's incoming edges. Then, just like before, some new nodes may now have only one outgoing edge because they previously had edges only to aa and bb, so we can merge those as well. At the end of this process, all nodes remaining in the graph will either have at least two outgoing edges, or a single edge to themself.

We now make the critical observation that in a graph where every node has at least two outgoing edges, if the tokens start at different nodes, then no matter which token the brain picks each time, the hoof always has a valid node to move it into that isn't the location of the other node, and so the hoof always wins. This extends to graphs that also have nodes with only a single edge to themselves, because the hoof can just move the token across that single edge back to the same node, since the other token is at a different node.

Therefore, after applying the above two reductions, we can answer a query for starting nodes aa and bb as follows:

If either aa or bb was removed from the graph in the first reduction, then the brain wins. Otherwise, if aa and bb became the same node after the merging process in the second reduction, the brain still wins. Otherwise, the hoof wins.

The two above reductions can be done fairly straightforwardly in O(N2)O(N2) by maintaining a set of incoming edges and a set of outgoing edges for each node, then using DFS or BFS. Each query is answered in constant time, for an overall runtime of O(N2+Q)O(N2+Q).

Subtask 3: No additional constraints

The first reduction should actually already run in linear time if you use sets as suggested above. To improve the runtime of the second reduction, we can use small to large merging and union find. When we merge aa into bb, instead of simply adding all of aa's incoming edges to bb's, we add whichever set is smaller to whichever set is larger. This means that each edge is added to a set at most lgNlg⁡N times. We then use union find to keep track of which node each node has been merged into. Whenever we find a node aa to merge into a node bb, we need to make sure to instead merge the union find root of aa into the union find root of bb.

As each edge is merged at most lgNlg⁡N times, the overall runtime becomes O(MlgN+Q)O(Mlg⁡N+Q).

Java code:

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.Set;
import java.util.Stack;
import java.util.StringTokenizer;

public class HoofAndBrain {
static int[] union;

static int find(int u) {
if (union[u] != union[union[u]]) {
union[u] = find(union[u]);
}
return union[u];
}

public static void main(String[] args) throws IOException {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer tokenizer = new StringTokenizer(in.readLine());
int n = Integer.parseInt(tokenizer.nextToken());
int m = Integer.parseInt(tokenizer.nextToken());
Set<Integer>[] adj = new Set[n + 1];
Set<Integer>[] rev = new Set[n + 1];
union = new int[n + 1];
for (int a = 1; a <= n; a++) {
adj[a] = new HashSet<>();
rev[a] = new HashSet<>();
union[a] = a;
}
for (; m > 0; m--) {
tokenizer = new StringTokenizer(in.readLine());
int a = Integer.parseInt(tokenizer.nextToken());
int b = Integer.parseInt(tokenizer.nextToken());
adj[a].add(b);
rev[b].add(a);
}
Stack<Integer> stack = new Stack<>();
for (int a = 1; a <= n; a++) {
if (adj[a].isEmpty()) {
stack.push(a);
}
}
while (!stack.isEmpty()) {
int a = stack.pop();
union[a] = 0;
for (int b : rev[a]) {
adj[b].remove(a);
if (adj[b].isEmpty()) {
stack.push(b);
}
}
}
for (int a = 1; a <= n; a++) {
if (adj[a].size() == 1) {
stack.push(a);
}
}
while (!stack.isEmpty()) {
int a = stack.pop();
int c = 0;
for (int b : adj[a]) {
c = b;
}
a = find(a);
c = find(c);
if (a != c) {
if (rev[a].size() > rev[c].size()) {
int temp = a;
a = c;
c = temp;
}
for (int b : rev[a]) {
adj[b].remove(a);
adj[b].add(c);
if (adj[b].size() == 1) {
rev[c].remove(b);
stack.push(b);
} else {
rev[c].add(b);
}
}
union[a] = c;
}
}
StringBuilder out = new StringBuilder();
for (int q = Integer.parseInt(in.readLine()); q > 0; q--) {
tokenizer = new StringTokenizer(in.readLine());
int a = Integer.parseInt(tokenizer.nextToken());
int b = Integer.parseInt(tokenizer.nextToken());
int u = find(a);
int v = find(b);
if (u == 0 || v == 0 || u == v) {
out.append('B');
} else {
out.append('H');
}
}
System.out.println(out);

}
}

Exercise: Solve the problem where the hoof wins by not having a valid move, and the brain wins by the game continuing indefinitely.
[/hide]