### xiaowuc1's blog

By xiaowuc1, 6 weeks ago, Hi all,

The final contest of the 2020-2021 USACO season will be running this weekend. Good luck to everyone! Please wait until the contest is over for everyone before discussing problems here.  Comments (24)
 » Good luck to all!
 » I think the contest is over right? How did you all do?
•  » » I don't think we can discuss that right now, we can discuss scores and problem questions when the USACO website tells us that the contest and over and it shows the solutions for the problems.
•  » » » When I posted the comment, the USACO website already said that "the contest is over and they are compiling the results".
 » How to solve the geometry problem from Gold?
•  » » I think it’s dp right? I didn’t manage to get it during the test tho.
•  » » » yes, it's dp.
•  » » » » Could you pls share code or somethn?
•  » » » » »
•  » » » » » » If I haven't misinterpreted, the above solution is O(n^5), here is an O(n^4) solution: CodeThe solution does some math to speed up the transitions by a dimension, though it actually doesn't run that much faster than O(n^5) solutions. This is probably because the transitions are more complicated. If I knew O(n^5) would've passed I would've coded that instead :/ Shoutout to Benq for setting easier problems :)
 » Do you think 730 would be able to qualify for plat?
 » Can anyone provide link to the problems for practice, since I am not able to find the link to the problems of US open on the USACO website.
•  » » I think it’s temporarily unavailable because they are still calculating the result. It probably will be open again after a few days and you can find it under “contest”.
•  » » » I see, thanks for letting me know.
 » 6 weeks ago, # | ← Rev. 2 →   My solutions for platinum: unitedWe want to count triples $(L, M, R)$ s.t. $L < M < R$ and $A_L$, $A_M$, and $A_R$ is unique in the subarray $[L, R]$.Fix $R$. We keep a segment tree, where the $i$-th leaf in the segment tree has the number of pairs $(i, b)$ ($i \leq b$) s.t. $A_i$ and $A_b$ is unique in the subarray $[i, R]$. Note that if $A_i$ is unique in the subarray $[i, R]$, then $\text{segtree}_i \geq 1$ ($(i, i)$ is a valid pair).Let $\text{prv}(i)$ denote the greatest index $j < i$ s.t. $A_j = A_i$. Then the number of triples $(L, M, R)$ for a fixed $R$ is $\Big( \sum_{i = \text{prv}(R) + 1}^{R - 1}{\text{segtree}_i} \Big) - \Big( \sum_{i = \text{prv}(R) + 1}^{R - 1}{[\text{segtree}_i \neq 0]} \Big)$We subtract $[\text{segtree}_i \neq 0]$ since $L < M$ must hold, thus we need to subtract the pairs $(i,i)$ if it is a valid pair ($A_i$ is unique in $[i, R]$).Let's move from $R - 1$ to $R$. $A_R$ becomes unique in $[R, R]$. $A_{\text{prv}(R)}$ is no longer unique in $[\text{prv}(R), R]$. For $\text{prv}(\text{prv}(R)) + 1 \leq i \leq \text{prv}(R) - 1$, the pair $(i, \text{prv}(R))$ becomes invalid. Subtract $1$ from $\text{segtree}_i$ if $A_i$ is unique in $[i, R]$. For $\text{prv}(R) + 1 \leq i \leq R$, the pair $(i, R)$ becomes valid. Add $1$ to $\text{segtree}_i$ if $A_i$ is unique in $[i, R]$. We can do all operations above with a segment tree that supports: For all $L \leq i \leq R$, add $x$ to $\text{segtree}_i$ if position $i$ is active. Find $\sum_{i = L}^{R}{[\text{position } i \text{ is active}] \, \text{segtree}_i}$. Toggle position $i$ to active or inactive. Time complexity: $O(N \log{N})$. routingCreate an extra node labeled $0$ in the given graph. If the $i$-th node is a sender, add edge $(0, i)$. If the $i$-th node is a reciever, add edge $(i, 0)$. Now we only need to count the number of eulerian circuits in a digraph, which we can do with the BEST theorem. The heaviest part of the computation is finding the determinant of an $N \times N$ matrix.Time complexity: $O(T N^3)$. balancedWe can decompose a subset into separate rows, where each row is a segment $[L_i, R_i]$. Then, the subset is valid if $[L_i, L_{i+1}, \dots, L_j]$ and $[R_i, R_{i+1}, \dots, R_j]$ is bitonic and the rows are contiguous.Let $\text{dp}(r, c_1, c_2, b_1, b_2)$ be the number of configurations if the last segment is on the $r$-th row and spans from column $c_1$ to $c_2$. $b_1$ and $b_2$ denotes whether we have encountered the minimum (maximum) element in $[L_i, \dots, L_r = c_1]$ ($[R_i, \dots, R_r = c_2]$). Then, if there is no empty cell between $(r, c_1)$ and $(r, c_2)$: $\text{dp}(r, c_1, c_2, b_1, b_2) = 1 + \sum\limits_{\substack{1 \leq i \leq c_2 \\ b_1 = 0 \vee c_1 \leq i}}{\sum\limits_{\substack{c_1 \leq j \leq N \\ b_2 = 0 \vee j \leq c_2}}{\text{dp}(r + 1, i, j, b_1 \vee (c_1 < i), b_2 \vee (j < c_2))}}$We can speed up the transition to $O(1)$ with prefix sums.Time complexity: $O(N^3)$.
•  » » It's actually possible to solve routing in $O(KN^2)$ time, because the matrix you take the determinant of is almost upper-triangular. In particular, it's upper triangular for all but at most 2 rows, so if you do Gaussian elimination in the right order, you'll only have to do $O(KN)$ row-operations.Just for the record: I believe the intended solution does not involve the BEST theorem or determinants, and takes $O(N^{K+1})$ runtime. Essentially, we will just try to match all inedges and outedges at each vertex; there are $\prod deg(i)!$ ways to do this. Some of these matchings may form unwanted eddy cycles, which must involve one of the $K$ backedges. Then, we can count ways to form the cycles using these $K$ edges, and we'll end up with a DP with $O(N^K)$ states and $O(N^{K+1})$ runtime. In fact, you can use some determinant-like arguments (or inclusion/exclusion if you'd prefer) to transform this into computing some path counts in $O(N^2)$, followed by taking a determinant of a $K \times K$ matrix, which is essentially equivalent to the BEST theorem/Gaussian elimination solution.
•  » » I just have a slightly different solution to united I'd like to share (the complexity is the same, but we don't need lazy propagation in segment tree for example).If we fix our $L = l$, let $f(i)$ denote the index of first occurrence of number $i$ to the right of $l$, and $s(i)$ denote the second occurrence. We can handle some of them being non-existing by just setting them to $n$.Then, we need to consider the interval $(l + 1, f(A_l) - 1)$ to search for two indices for $M$ and $R$. Obviously, as $A_M$ and $A_R$ have to be unique in the chosen subarray, they are going to be $f(x)$ for some $x$. The condition for some values $x$ and $y$ being a suitable pair of values is $f(x) < s(y)$, and $f(y) < s(x)$. We can calculate the number of such pairs using a regular segment tree. In every node we store: the number of $f$ values the number of $s$ values number of $(i, j)$ such that $f(i) < s(j)$ number of $(i, j)$ such that $s(i) < f(j)$, which we can easily merge in $O(1)$. From these four values, we can get the number of pairs we need. Note that when we're moving our $L$, we only have $O(1)$ updates in the segment tree, so we end up with $O(N\log N)$ complexity in the end.
•  » » For united, how do you construct that segment tree? In competition, I got to the point of figuring out that kind of a structure was necessary, but couldn't figure out how to actually build such a tree. How can you toggle an element's activity and target those elements specifically?
•  » » » In each segment $[L, R]$ (of a node in the segment tree), we keep: $cnt$, number of active positions. $sum$, sum of elements in active positions. $lazy$, lazy propagation. Then, if a we add $x$ to the segment $[L, R]$: Increase $sum$ by $cnt \cdot x$. Increase $lazy$ by $x$. Everything else is almost the same as a standard lazy segment tree.
 » 6 weeks ago, # | ← Rev. 2 →   What was the approach for #1 in the silver division?The tricky thing was that you can go back the way you came and retrace your steps, so what I did was have a sort of vis set that stores the grids we visited at each point in the maze. But that TLE'ed on test case #10, so I'm curious to know what other people did.
•  » » A set is too slow for test case #10. You could use a 3-D array to store the states you have already visited.
•  » » » Yeah that's what it says in the official solution.It's still a bit sketchy though, because my solution takes about 0.33 seconds (and the official solution took 0.2), which is quite long. Maybe we could have had a limit of a 20 x 20 grid instead, but it's already over now.
 » 6 weeks ago, # | ← Rev. 2 →   USACO Gold Solutions: United#include #include #include #include #include #include #define ll long long using namespace std; int n; bool cstm(pair p1, pair p2){ return p1.second < p2.second; } struct segTree{ vector v; vector arr; vector> vec; int cl(int x){ int pwr = 1; while(pwr < x){ pwr *= 2; } return pwr; } pair merge(pair p1, pair p2){ return make_pair(p1.first,p2.second); } long long build(int ind){ if(ind >= v.size() - 1){ arr[ind] = v[ind - (v.size() - 1)]; return arr[ind]; } arr[ind] = build(2 * ind + 1) + build(2 * ind + 2); return arr[ind]; } pair build2(int ind){ if(ind >= v.size() - 1){ int x = ind - (v.size() - 1); vec[ind] = make_pair(x,x); return vec[ind]; } vec[ind] = merge(build2(2 * ind + 1),build2(2 * ind + 2)); return vec[ind]; } long long interval(int i, int L, int R){ if(vec[i].first > R || vec[i].second < L){ return 0; } if(vec[i].first >= L && vec[i].second <= R){ return arr[i]; } long long a = interval(2 * i + 1,L,R); long long b = interval(2 * i + 2,L,R); return a + b; } void update(int k, int u){ int ind = (v.size() - 1) + k; arr[ind] = u; while(ind != 0){ int parent = (ind - 1)/2; arr[parent] = (arr[2 * parent + 1] + arr[2 * parent + 2]); ind = parent; } } }; class Problem1UnitedCowsOfFarmerJohn { public: vector arr; vector> myMap; vector nxt; vector prev; vector end; vector start; ll comp(int x){ if(prev[x] == -1){ return x; } return x - prev[x] - 1; } void fill(){ end.resize(n), start.resize(n); for(int i = 0; i < n; i++) { if (nxt[i] == -1) { if (i != 0) start[i] = start[i - 1]; else start[i] = 0; } else { start[i] = start[i - 1] + 1; } if (prev[i] == -1) { if(i != 0) end[i] = end[i - 1]; else end[i] = 0; } else { end[i] = end[i - 1] + 1; } } } vector> transform(){ vector> v; for(int i = 0; i < n; i++){ if(nxt[i] == -1) continue; v.push_back({i, nxt[i]}); } return v; } ll interval(int n){ vector> vec = transform(); segTree st; int x = st.cl(n); st.v.resize(x); st.arr.resize(2 * x); for(int i = 0; i < st.v.size(); i++) st.v[i] = 0; st.vec.resize(2 * x); st.build(0); st.build2(0); sort(vec.begin(), vec.end(),cstm); ll ans = 0; for(int i = 0; i < vec.size(); i++){ vec[i] = {vec[i].first + 1, vec[i].second}; ans += st.interval(0, vec[i].first, vec[i].second); st.update(vec[i].first, 1); } for(int i = 0; i < n; i++){ if(prev[i] == -1){ ans += end[i]; } } return ans; } void solve(std::istream& in, std::ostream& out) { in >> n; arr.resize(n); myMap.resize(n); nxt.resize(n); prev.resize(n); for(int i = 0; i < n; i++){ in >> arr[i]; arr[i]--; myMap[arr[i]].push_back(i); } //return; for(int i = 0; i < n; i++){ if(myMap[i].size() == 0) continue; for(int j = 0; j < myMap[i].size() - 1; j++){ nxt[myMap[i][j]] = myMap[i][j + 1]; } for(int j = 1; j < myMap[i].size(); j++){ prev[myMap[i][j]] = myMap[i][j - 1]; } nxt[myMap[i][myMap[i].size() - 1]] = -1; prev[myMap[i]] = -1; } ll sm = 0; for(int i = 0; i < n; i++){ sm += comp(i); //out << comp(i) << ' '; } fill(); out << sm - interval(n) << endl; } }; That's all I solved fully (400 on this contest)
 » When do US Open/Finalist results come out? (This won't affect me, but I'm curious)