USACO 2022 December Contest Silver Problem 1
Table of Contents
Open Table of Contents
Problem
Approach
Clearly, this problem is a graph problem. Reading further, we see that we are dealing with a simple connected graph with $n-1$ edges on $n$ nodes. This clearly implies that we are dealing with a tree(if it wasn’t obvious from the title of the problem). Trees are nice to deal with because they have some nice properties that can help us when deriving an algorithm:
- Trees have $n-1$ edges exactly
- Trees are minimally connected
- Trees are by definition acyclic
- There exists exactly one distinct path between any two nodes
As you’ll see, those last two properties will help us down the line.
Housekeeping
At the beginning of any problems like this, I usually like to derive some properties about th Ae graph that may come in handy later on. If they aren’t used, I can simply delete them, but any property that is unique to the problem and takes no extra time to compute is good to have around. In this case, the value that would help us the most would be the number of bales we want each node to have equivalently, which we denote $e$. We can easily compute this by dividing the total number of bales by the number of nodes. Note that we are guaranteed that $e$ is an integer by the problem:
$$ e = \frac{\Sigma_{j=1}^n h_j}{n} $$
With $e$ now calculated, we will define two fields for our state:
- Graph $G$ stored as an adjacency list (NOT AN ADJACENCY MATRIX)
- List $H$ that contains $h_i$ at index $i$
We will do one more thing before moving on. USACO often trips people up because their problems seem are written as far as possible from problems you would see in your typical DSA class. However, sometimes it is helpful to try and simplify the problem into something you would see on a DSA exam(stop thinking about haybales and barns). In this case, we would find it helpful to subtract $e$ from every element in $H$. This would allow us to target $0$ instead of $e$ when shifting around hay bales. Not only does this make our code look a little simpler, it makes the visualization and understanding of this problem a lot more intuitive:
- If $h_i < 0$, then $i$ needs more hay bales
- If $h_i = 0$, then $i$ needs no change in hay bales
- If $h_i > 0$, then $i$ needs to get rid of hay bales Now we have a clear signifier on what each nodes needs are.
Algorithm Design
Before we even begin any sort of algorithm, we have a vital piece of information: $e$. The fact that we already know our “target” count for each makes it intuitive to approach this problem in a greedy manner.
Thinking greedily, we see that ideally we should only have to “go through” every edge at most once. This is because we have no limits as to how many hay bales we can push through an edge at the same time. Therefore, if we had one command that sent 5 hay bales from $A \to B$ and then another command that sent 8 bales from $A \to B$ later on, we could just reorder the commands such that we combine them and send 13 hay bales. If we extend this further, we see that there is a “net” change of bales across an edge, so we should only either send hay bales from $A \to B$ or $B \to A$. Therefore, we should never be sending more than $m$ commands(where our graph is $G(n, m)$).
Now we are left with two smaller problems: finding the net change of bales across each edge, and ordering these commands such that we are never sending a number of bales that we don’t have. As before, we can think about these subproblems greedily. And when it comes to graphs, nothing is more greedy than DFS.
Finding Net Change
Let us start with the first subproblem. If we DFS from an arbitrary root node, sending whatever value we have as a “requirement” to our children, then clearly this doesn’t work, as we have no way to tell how to split our nodes requirement amongst its children. However, as we often find with trees, it is more proficient to work upwards from leaves to the node. If we think about an arbitrary internal node in our DFS tree that is not the root, $u$, then we see that it has one parent, $p$, and a set of children, $S$. We see that for each child in $S$, if by the end of our ideal commands, we have sent any bales from $G \setminus S \to S$ or $S \to G \setminus S$, then they will have to go through $u$. Therefore, we can calculate the net change across $u$ by summing the requirements of its children and itself, and then “requesting” that from $p$. If the sum, denoted $sum(u)$, is positive, this implies that $S + u$ has a net “surplus” of bales, and that as a whole, all the nodes in $S + u$ need to send $sum(u)$ bales outward through $u \to p$ in order for all the nodes in $S + u$ to reach $e$. On the contrary, if $sum(u)$ is negative, then we know that $S+u$ has a lacking of bales, and needs to be fed $sum(u)$ bales through the $p \to u$ channel in order for all those nodes to reach $e$.
With a little modification, we can use this concept to create a recursive algorithm of the following format:
dfs(node) {
sum = h[node]
visited[node] = true;
foreach k in N(node) { //N(node) is the neighborhood
if not visited[k] {
sum += dfs(k)
}
}
return sum
}
The base case for this algorithm would be when we reach a leaf. However, we can see that this is already taken care of, as a leaf would only have one neighbor, which is its parent, which would clearly already be visited, so we would just be returning h[node]. Finally, when it comes to the root node, we will be returning the sum of $h_i$ for every $i$, which in theory, should be $n \cdot e$. However, due to the modification we made at the end of our housekeeping section, $e$ should be equal to 0, so our dfs function should return 0.
During the implementation process of this algorithm, right about here is where I would stop and test my code. Our dfs function should always return 0 on a valid graph for this problem, so I would take this chance to test it on multiple graphs, and on multiple of their nodes, making sure it works.
Creating and Ordering Commands
Now that we have full idea of how we can move around the bales, we simply need to generate the commands and order them such that we are never moving around a negative amount of bales.
To do this, we first need to generate the orders. These orders can be stored in whatever datatype you like, but personally I found it most intuitive to use a queue, denoted $Q$. We then simply need to add orders to the queue as we receive them. More specifically, all we need to do is insert a line (in the form of a tuple (from, to, value))Q.add((k, node, v)) where v = dfs(k) if $v \neq 0$ . This is because if we have a return of 0, we are pushing nothing through the path, and therefore should not add an extra command. We are now left with two issues: considering the order of commands, and dealing with negative values.
First, we notice that for any positive value order, we will never run into the issue of moving hay bales that we do not have from a node. This can be proved with some simple induction, but a quick overview is that whenever we return a positive value from a leaf node, that means that that leaf node has a surplus of that many bales, and we are moving those bales back up the tree. Therefore, those bales must now exist in the parent node, which will take the sum of its children, which cannot be more than the number of bales it has. Therefore, we know that all of our positive value orders are already in order.
Now all we have to do is deal with negative value orders. What even are the negative value orders in interpretation?. Well, a negative value order is a “request” of sorts, in which (a, b, -c). Implies that $a$ is requesting $b$ to give it $c$ haybales. If we interpret it this way, we can see that all we need to do is reverse this negative value order into a positive value order, like (a, b, -c) => (b, a, c). This will instead be the same command, just interpreted as $b$ gives $c$ haybales to $a$. Now, we need to deal with the final issue of ordering these haybales. As we know, the current order of these orders is working its way up the tree. However, in the case of requests, we have children requesting bales from their parents to satisfy their children, which means we want to push bales down the tree. Therefore, it would make sense for us to reverse the order of all these negative value orders, so that the parents can supply their children, before those children do the same. Finally, we know that at the end of all the positive value orders are executed, no node in the tree will have a surplus on its hands. Therefore, all we need to do is “push down” the remaining haybales in the nodes such that no node is not at 0. By this line of thinking, it makes sense to append the negative commands to the end of the positive commands.
reorder(Queue Q) {
separate Q by pos/neg into => Queue pos, Stack neg
Queue orders = {}
foreach p in pos {
orders.add(p)
}
foreach n in neg {
n(from, to, value) => (to, from, -value)
orders.add(n)
}
return orders
}
This reordering bit might be a bit confusing, so if it doesn’t click, I suggest doing a few examples, and seeing how you might come to this conclusion yourself and why each of these steps are necessary.
Finally, all you would need to do is output the orders. Make sure that for each order, you add 1 to the from, to nodes as the nodes are 1 indexed, and also add $e$ to the value.
Code
import java.io.*;
import java.util.*;
public class BarnTree {
private static boolean[] visited;
private static HashSet<Integer>[] graph;
private static long[] nodes;
private static int n;
private static Queue<Order> orders;
public static void main(String[] args) {
//input handling
Kattio kattio = new Kattio();
n = kattio.nextInt();
nodes = new long[n];
graph = new HashSet[n];
visited = new boolean[n];
orders = new LinkedList<>();
long sum = 0, e;
for (int i = 0; i < n; i++) {
graph[i] = new HashSet<Integer>();
}
for (int i = 0; i < n; i++) {
nodes[i] = kattio.nextLong();
sum += nodes[i];
}
e = sum / n; //should be a whole number, the targeted average
for (int i = 0; i < n; i++) {
nodes[i] -= e;
}
for (int i = 0; i < n-1; i++) {
int f = kattio.nextInt() - 1;
int t = kattio.nextInt() - 1;
graph[f].add(t);
graph[t].add(f);
}
dfs(0);
Queue<Order> pos = new LinkedList<>();
Stack<Order> neg = new Stack<>();
while (!orders.isEmpty()) {
Order o = orders.poll();
if (o.count > 0) { //pos
pos.add(o);
} else { //neg
neg.add(o);
}
}
kattio.println((pos.size() + neg.size()));
while (!pos.isEmpty()) {
Order o = pos.poll();
kattio.println((o.from + 1) + " " + (o.to + 1) + " " + (o.count));
}
while (!neg.isEmpty()) {
Order o = neg.pop();
kattio.println((o.to + 1) + " " + (o.from + 1) + " " + (o.count * -1));
}
kattio.close();
}
private static class Order {
public int from;
public int to;
public long count;
public Order(int f, int t, long c) {
from = f;
to = t;
count = c;
}
}
//dfs, return value
private static long dfs(int node) { //sum all children and return
long sum = nodes[node];
visited[node] = true;
for (int u : graph[node]) { //for all neighbors
if (visited[u]) {
continue;
}
long val = dfs(u);
if (val != 0) {
sum += val;
orders.add(new Order(u, node, val));
}
}
//ATP, all children nodes in the DFS tree have been set to 0, and this simply needs to be set to 0 and returned
nodes[node] = 0;
return sum;
}
private static class Kattio extends PrintWriter {/* std kattio IO */}
}