The main point of this repo is to track my learning process during USACO 2020-2021 season. All the solutions have been verified at USACO contest website. I learn for fun, for a change, a change in problem, a change in solution, a change which leads to the discovery of new algorithm.
At Platinum level, I have to define new concepts sometimes. In Circus (USACO 2020 Open) problem, new definitions are given for virtual connected component and chain in order to describe my algorithm. The connected component (CC) is somewhat similar to but also different from connected component in graph. It defines one domain where two cows could swap their positions. The chain is like one weighted edge in tree or graph, which connects but also segments CCs. Similar to Boruvka’s algorithm, the algorithm is to merge CCs by removing or hiding chains when there are enough unoccupied vertices. Here is the detailed description.
Solutions to other two problems:
The Sum of Distances is a very interesting question. During the contest, I realized that it is actually Dijkstra shortest path (SPF) problem. But the vertex is a K-dimensional vector. Every field in a vector vertex has its own rule to change in graph G[i]. There will be a lot of vertices in the connected graph starting from (0,0, ...0). The key point is to find which vector vertex in G is visited.
The 1sumbfs.cpp is doing Dijkstra BFS traversal from this starting vertex. The hash table is used to check which vector vertex is visited.
As the problem asks for the sum of all shortest distance, I defined one rule to visit all the vector vertices: never go back. The detail of 1sum.cpp can be found here.
The generating function is helpful to find the DP transition formula, or make DP unnecessary. But not any DP transition can be deducted from generating function. For Tree Depth, USACO 2019 December Contest, Platinum, the solution is usually based on generating function of permutation statistics. Here I provide one DP solution.
First the DP state is defined as follows:
dp[n][k]: the total number of k inversions for all permutation with n objects.
Now we add the number n to the permutation of n-1 objects. There are n position which we can insert the nth object. If it is appended at the end, it adds 0 more inversion. WLOG assumes that there are n-1-i more inversions if nth object is added at position i. Thus we get the DP transition formula as follows:
dp[n][k] = sigma(dp[n-1][k-i]) for i=[0, min(n-1, k)]
The k could be very big, but it is not over n(n-1)/2. If k is big than this number, dp[n][k] = 0. So we can have the following values for DP table.
dp[0][0] = 1, but dp[0][1]=0
dp[1][0] = 1, but dp[1][1]=0
dp[2][0] = 1, dp[2][1] =1, but dp[2][2] = 0.
For K inversions, we only care about (K-i) number of inversion at dp[n-1] level, which is a part of prefix sum. So the time complexity is still O(NK) or O(N3).
Sometimes we have to convert vague definition to clear definition.
For example, in Sprinklers 2, the transition line is above the read block or on the left side of blue block. It is not exactly at one point (i, j). Another example is Out of Sorts. The partition point is between i and i+1, not at i or i+1. For these cases, the clear definition must be provided to complete the computation.
I used PLUG DP to solve van (USACO 6.1) and betsy (USACO 6.5). Here I modify the plug properties to solve the "Compound Escape" problem again.
The code is pretty much similar to other two problems. The plug DP is used to solve the row-based, such as grid, problems when the size of one row is relatively small. It greatly improves the performance of the Bellman-Held-Karp Algorithm for these special cases. As the state space is small but scattered, we should have a way to store the state. I used hash table in these cases.
Here are some DP optimization techniques used for some USACO problems.
Similar to the problem "Maximum value in sliding window", priority queue can be used to improve efficiency. But montonic queue is more efficient.
- Photo in 2013 Open : convert O(N2) to O(N) by using monotonic queue.
- Trapped in the Haybales : We can not use monotonic queue as the monotonicity is subject to change. Instead we use priority queue in solution. Maybe red-black tree is better than priority queue.
dp[j] = min(dp[k] + b[k] * a[j]) for k < j
dp[i][j] = min(dp[i-1][k] + b[k] * a[j]} for k < j
USACO problems:
dp[i][j] = min(dp[i-1][k] + C[k][j]) for k < j
dp[i][j] = min(dp[i][k] + dp[k][j]) + C[i][j] for i < k < j
The USACO problems is very intriguing. They lead me to think deeper and deeper into the possible change in problems and solutions:
- No Time to Dry: If we change Q to be 2*106, my online algorithm should still pass all the test cases.
- Landscaping: My online solution does not depends on the maximum value of (Bi or Ai), which is 10 in problem.
- Minimizing Edges: We could possibly have different changes in solutions and problem.