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]