From USACO Gold, you must start at KST 2 AM and end at KST 6 AM in order to advance to the Platinum Division.

I completely missed the first contest because I fell asleep while lying down, and I simply got cooked on the second one (350/1000).

For some reason, though, the third USACO contest tends to be the easiest every year, so I decided to give it a shot as my last change this season.

I was a bit surprised that every problem was a Test Case problem. I wonder if they were Codeforces problems that got scrapped.

Solutions

Problem 1 : Good Cyclic Shifts

For a permutation \(p\), define \(f(p) = \sum_{i=1}^{N}{\frac{|p_{i} - i|}{2}}\).

Given a permutation of length \(N\), the task is to determine, for every cyclic right shift, whether the number of inversions is less than or equal to \(f(p^{\prime})\).

• It is guaranteed that \(\sum_{i=1}^{N}{|p_{i} - i|}\) is always even (Permutation Displacement).

The inversion count can be updated in \(\mathcal{O}(1)\) for each cyclic shift. (\(v \rightarrow v + 2X - N - 1\); \(X\) is the value moved from the far right to the far left.) Therefore, the main challenge is computing \(f(p)\) efficiently for each shift.

For convenience, define a function \(g\) such that \(g(p) = 2f(p) = \sum_{i=1}^{N}{|p_{i} - i|}\).

Each element moves one position to the left as the permutation shifts. If an element is currently to the left of its original position, its distance decreases, so \(g(p^{\prime})\) decreases by \(1\). If it is at or to the right of its original position, its distance increases, so \(g(p^{\prime})\) increases by \(1\). Therefore, we can maintain the number of increasing elements and update this count using a priority queue keyed by the remaining time until each element reaches its original position.

Since each element transitions from decreasing to increasing at most once, only about \(\mathcal{O}(2N)\) events are ever inserted into the priority queue.

Problem 2 : Picking Flowers

You are given a graph with \(N\) vertices and \(M\) undirected edges. There are flowerbeds on \(K\) vertices and \(L\) destination vertices. (A vertex can be both a flowerbed and a destination.)

For every vertex \(v\), suppose we add an additional flowerbed at that vertex. The task is to determine whether there exists a shortest path from vertex \(1\) to some destination that visits all flowerbeds. (\(2 \leq v \leq N\)) Each query vertex is considered independently.

• Subtask 1: \(K=0\), \(L=1\)
• Subtask 2: \(K=0\)
• Subtask 3: No additional constraints.

I misread the problem and thought it asked whether a shortest path could visit at least one flowerbed rather than all flowerbeds. By pure coincidence, that happened to be exactly the solution for the \(K=0\) case. Funny thing is that something similar happened in an AtCoder contest I did right before USACO.

Observations

First, since we only care about shortest paths from vertex \(1\) to destination vertices, we compute the shortest distance from vertex \(1\) to every vertex using BFS. For an arbitrary destination vertex \(t\), a vertex can lie on some shortest path from \(1\) to \(t\) only if it satisfies \(\mathrm{dist}(1, v) + \mathrm{dist}(v, t) = \mathrm{dist}(1, t)\).

Therefore, if we keep only the vertices satisfying this condition and remove all others, the remaining graph consists of vertices that can appear on some shortest path to a destination. Along any shortest path, the distance value increases by exactly \(1\) at every step. Hence every remaining edge points toward a larger distance value, making the graph a DAG.

Subtask 2 : \(K = 0\)

Starting from every destination vertex, perform a reverse BFS following only edges that decrease the distance value by \(1\). This finds all vertices that belong to some shortest path to a destination. If a vertex \(v\) survives this process, then it lies on some shortest path to a destination, meaning there exists a shortest path that visits the flowerbed added at \(v\). Since there are no other flowerbeds, this is sufficient.

Each vertex is processed at most once, so the time complexity is \(\mathcal{O}(N)\).

Full Solution

The full solution is only a slight modification of the \(K=0\) solution.

Perform DP on the DAG.

• \(F[v]\) : the maximum number of flowerbeds that can be visited on a shortest path from vertex \(1\) to \(v\)
• \(B[v]\) : the maximum number of flowerbeds that can be visited when moving backward from some destination to \(v\)

For a shortest path passing through vertex \(v\) to contain all flowerbeds, it must satisfy \(F[v] + B[v] - \mathrm{is\_flower}[v] = K\). (If \(v\) itself contains a flowerbed, it is counted twice, so we subtract it once.)

Therefore, adding a flowerbed at any vertex satisfying this condition guarantees the existence of a shortest path that visits all flowerbeds.

Problem 3. Random Tree Generation

A tree is generated as follows.

1. Create vertex \(1\).
2. For each vertex \(i(2 \leq i \leq N)\), choose a parent uniformly at random among vertices \(1\) through \(i-1\).
3. Repeat until all \(N-1\) additional vertices have been added.
4. Apply a random permutation to the vertex labels.

Given a tree with \(N\) vertices, compute the probability that this process generates exactly the same edge set.

• Subtask 1: \(N \leq 8\)
• Subtask 2: \(N \leq 2\,000\)
• Subtask 3: \(N \leq 200\,000\)

Observations

A vertex can only be generated after its parent has already been generated, so the number of valid generation orders depends on which vertex was originally vertex \(1\) (the root). Let the root be \(r\), and compute subtree sizes using DFS. Since every parent must appear before its children, the number of valid generation orders is \(\frac{\left(N - 1\right)!}{\prod_{u \neq r}{\mathrm{sz}_{r}[u]}}\).

Meanwhile, during the generation process, vertex \(i\) chooses its parent with probability \(\frac{1}{i-1}\), so the probability of any specific generation order is \(\prod_{i=2}^{N}{\frac{1}{i-1}} = \frac{1}{\left(N-1\right)!}\).

Therefore, when the root is \(r\), the probability of generating exactly this tree is \(\frac{\left(N - 1\right)!}{\prod_{u \neq r}{\mathrm{sz}_{r}[u]}} \times \frac{1}{\left(N-1\right)!} = \frac{1}{\prod_{u \neq r}{\mathrm{sz}_{r}[u]}}\).

Finally, after accounting for the random relabeling step, the final answer is obtained by summing over all possible roots and dividing by \(N!\).

Subtask 2: \(N \leq 2\,000\)

We can simply run a DFS for every possible root in \(\mathcal{O}(N^{2})\).

Full Solution

Suppose the current root is \(r\). If we reroot the tree at a child \(v\) of \(r\), then only the subtree sizes of \(r\) and \(v\) change. Root the tree once and run a DFS in \(\mathcal{O}(N)\) to compute all subtree sizes. Then perform another DFS, updating the affected subtree sizes in \(\mathcal{O}(1)\) per vertex while maintaining the answer.

Overall

The problems were fun, the difficulty felt relatively reasonable too, and at least this was much better than wasting four hours in the second contest.

Platinum is on an entirely different level, though, so I probably won't continue.

P.S. Apparently, now you have to participate in Gold every year to maintain Platinum status, I'm so cooked :skull: