### xiaowuc1's blog

By xiaowuc1, 10 months ago, , Hi all,

The final contest of the 2018-2019 USACO season, the US Open, will be running from March 29th to April 1st! Good luck to everyone! As a courtesy to your fellow contestants, please wait until the contest is over for everyone before discussing problems here.

Edit 1: The contest is live! Please do not post any spoilers about the problems publicly — if you have any issues with the problem statements, please follow the instructions to voice your concerns. Comments (41)
 » When does the contest usually starts? Thanks in advance :)
 » where is the contest window?
 » Guys, all the problems are by Ethan Guo
 » is anyone else not getting an email for the forgot password thing on USACO? Im pretty much locked out of my account
 » does anybody know WILLIAM LINs score?
 » How does one implement Gold Balance non-cancerously?
•  » » If we don't perfom swap on ceils $n$ and $n + 1$, then the answer is difference between number of inversions in a first half and a second half. If we perfom swap on ceils $n$ and $n + 1$ we can notice, that in an optimal solution we either will move some number of 1's from a second half to a first half either we will move some number of 1's from a first half to a second half and after we finish 1s movement, we also need to add difference between inversions in a first half and a second half.So, the solution is as follows:Fix the direction in which we will move 1's. Move each 1 one by one, maintain number of inversions in a first and a second half. Relax answer with difference between inversions + actions that we spent on 1's movement.
•  » » » Thanks!
•  » » » Wow, I can't believe I didn't realise that all that the swaps across the middle amounted to was moving a certain number of ones across :/
•  » » » Goat. Couldn't do the math right. Unfortunately, I got it wrong.
 » What was the DP solution for Gold 1?
•  » » I'm not sure my solution counts as DP but I used memoization to recursively fill the DP.
•  » » 10 months ago, # ^ | ← Rev. 2 →   My state was $dp[rightmost element][number of groups]$. I precomputed the cost for all subarrays in $O(N^3)$, then each transition is $O(N)$.
 » Can anyone explain their solution for platinum 3
•  » » A valley is uniquely defined by the maximum height in the area. So you can enumerate possible valleys by fixing maximum height and finding the connected component that has heights all less or equal to it. Now you have $O(n^2)$ candidate, but you want to see whether the component has a hole. However, you can count a number of "global" holes, because it's a number of connected components in 8 direction. Preprocess the number of "global" holes, and let's try step 1 again. Maintain a disjoint set that contains each connected component, and the num of holes that each component has. If a component is merged, then basically all holes in each components are preserved. But, there is a "small" difference in the number of holes — that difference, could be traced because all the difference in "global" holes is attributed to that merges, thus the number is identical.
•  » » » I have a couple of questions. What is a "global" hole and how do you preprocess them? Also, when two components are merged, how do we know if the merge creates a new hole or not? Thanks in advanced!
•  » » » » 10 months ago, # ^ | ← Rev. 2 →   OK. I will clarify the definitions. A "Hole" is 8-directionally connected component consisted of cells that have a higher height than the specified maximum. (Note that we consider border cells as height $\infty$.) When I said "component $X$ has a hole", then it means there is a hole component, completely inside a connected component $X$. When I said "global hole", it is simply the number of connected components of such.We can't know whether the merger creates a hole or not, but we just deduce it from the difference of precalculated number of "global holes" for each phase, because the number would be the same.
•  » » » » 10 months ago, # ^ | ← Rev. 2 →   Precompute for each height, the number of holes over all “valleys.” You can do this with a DSU. Then do a second DSU pass keeping track of the number of holes per valley (change in number of holes is number of holes total after considering this height minus the number before)
•  » » I solved it with Euler's formula, which stated that number of faces in a connected planar graph is equal to (# of edges) - (# of vertices) + 2. I add cells into the graph one by one from the lowest to the hightest. For each connected component, it can be considered as a planner graph, with neighboring cells forming an edge, and each cell as a vertex. I maintained # of edges and # of vertices in each connected component. These are easy to maintain.I also maintained # of 2 by 2 squares in each component, because each of them forms a face when turning into graph, but that's not what we considered a "hole". When adding new cells, this could be updated by directly checking whether this cells forms a 2 by 2 square.After updating each counter, I checked whether (# of edges) - (# of vertices) + 2 - (# of 2 by 2 squares) is equal to one (region outside the component is also considered a face). If not, then there must be a hole in it.
 » Does anyone have solution for Gold 3?
 » Could someone please explain their thought process to attack Platinum 2 (Compound Escape)? I got to "count the number of MSTs," but didn't make much progress afterward.
•  » » I did a weird dp: dp[r][b][s] = {min cost, #ways} , where r = row processed, b = whether hor edges in that row have been processed, and s = connectivity state, which represents how the nodes in the last row are related (ie 112211 means node in pos 0,1,4,5 are in one component and pos 2,3 are another). For k=6, there are only around 130 total connectivity states, and if you precompute the state transitions it runs pretty quickly.
•  » » » My bruteforce code below tells me that there are 203 connectivity states. Did you optimize more? Code#include using namespace std; int main(int argc, char const *argv[]) { set> st; int a; for(a = 0; a < 6; a++) { for(a = 0; a < 6; a++) { for(a = 0; a < 6; a++) { for(a = 0; a < 6; a++) { for(a = 0; a < 6; a++) { for(a = 0; a < 6; a++) { vector tmp(6), v(6); map F, mp; for(int i = 5; i >= 0; i--) F[a[i]] = i; for(int i = 0; i < 6; i++) tmp[i] = a[i]; sort(tmp.begin(), tmp.end()); tmp.erase(unique(tmp.begin(), tmp.end()), tmp.end()); sort(tmp.begin(), tmp.end(), [&](int x, int y) { return F[x] < F[y]; }); for(int i = 0; i < tmp.size(); i++) mp[tmp[i]] = i; for(int i = 0; i < 6; i++) v[i] = mp[a[i]]; st.insert(v); } } } } } } cout << st.size() << endl; } 
•  » » » » I found 203 connectivity states as well, and after some quick research it appears that the number of connectivity states is known as a bell number and that 203 is the amount when k = 6.
•  » » » » Bell numbers count the possible partitions of a set. But in this problem, not every partition method is valid.For example, when $k=4$, it won't happen that the first and the third cell are in one component, and the other two cells are in another component. (You can try drawing it on a paper.)So when $k=6$, only around 130 connectivity states are valid, as stated by jasony123123.
•  » » » » » Partitions that are valid connectivity states are called crossing-free partitions. The number of those is exactly the nth Catalan number.
 » 10 months ago, # | ← Rev. 2 →   For Gold 2, I can only think of a greedy approach (9/15 test cases, rest is TLE). Sort all pair (i, j) by their distance, then use DSU to form groups.
•  » » Answer is MOD-48n-84(k-1).
•  » » » Can you explain why?
•  » » » » You always get the sets {1},{2}, ..., {K-1}, {K,K+1,...N}
•  » » » » » I don't understand how this observation is connected to @dorijanlendvaj's solution. Can you explain its relevance?
•  » » » » » » The smallest pair is always going to be achieved by taking K-1 and N, which you can see in the construction jebaited posted.
•  » » » » » » » 10 months ago, # ^ | ← Rev. 2 →   How do you know that k-1 and n will always produce the smallest number, though?
•  » » I forget the problem. I can't access 2019US OPEN's problem on USACO now? Can you tell me what the problem is? Please.
 » Can anyone predict promotion cutoffs for Gold to Plat?
•  » » I think we are seeing either a 700 or 750 here. It depends on how many people solved the last problem. From my correspondance with other people who took the contest, they agreed that number three was the hardest.
•  » » 10 months ago, # ^ | ← Rev. 2 →   I feel like it's going to be 750, as there was significant partials available and the difficulty wasn't too bad.
•  » » » How would you get partial on gold 3?
 » Why are results still not out?
•  » » Wait so long. I forget the problem Gold 2. I can't access 2019US OPEN's problem on USACO now? Can you tell me what the problem is?
•  » » Results are finally out at http://usaco.org/index.php?page=open19results!