Codeforces celebrates 10 years! We are pleased to announce the crowdfunding-campaign. Congratulate us by the link https://codeforces.com/10years. ×

### xiaowuc1's blog

By xiaowuc1, 5 weeks ago, ,

Hi all,

The second contest of the 2019-2020 USACO season will be running from January 17th to January 20th. Good luck to everyone! Please wait until the contest is over for everyone before discussing problems here.

Edit 1: The contest is now live! Please do not spoil anything about the contest publicly until the contest is over for everyone, and please report any issues with the contest directly to the contest administrator via the instructions instead of posting them here.

Edit 2: Due to a configuration error, the contest is running for 12 more hours than originally stated. The contest window is still open, please wait for the window to expire at 4:00 AM UTC on January 22nd before discussing.

Edit 3: Results can be found here.

• +128

 » 5 weeks ago, # |   +305 we should start preparing the contest lol
•  » » 5 weeks ago, # ^ |   +83 Technocup: Netflix adaptation
 » 5 weeks ago, # |   -43 For all others who cannot joke about the USACO contests ( yet:) ) SpoilerQuality mock contests for all levels of USACO: https://starleague.us/lms
•  » » 5 weeks ago, # ^ |   0 Quality These problems are way easier than the actual USACO. Last year I got full score on the mock Gold contest but I only got 300 in the actual contest.
•  » » » 5 weeks ago, # ^ |   0 I mean, that doesn't mean that the quality of problems is bad. Also in general I find it helpful to mock things that are one level higher than what I am currently in (e.g. Plat if I'm in Gold currently).
 » 4 weeks ago, # |   -6 I am not sure if the contest is over but how to solve second problem from platinum?
•  » » 4 weeks ago, # ^ |   +13 While the contest should technically be closed (it is past 4:00 am in UTC-12 time), the page for the contest is still open (this might be due to an issue on part of the contest organizers), so it is safer to not yet discuss.
•  » » » 4 weeks ago, # ^ |   +33 Yeah, please refrain from discussing until 11:00 pm eastern time (12 hours later than normal).
 » 4 weeks ago, # |   -44 is silver cutoff gonna be like 600? everyone says it was super hard lol
•  » » 4 weeks ago, # ^ |   +14 discussion is not allowed yet, just wait for until the time Benq mentioned above to discuss
•  » » » 4 weeks ago, # ^ |   +5 fishy15 cm :)
 » 4 weeks ago, # |   0 I believe the contest has ended, can anybody confirm?
•  » » 4 weeks ago, # ^ |   +20 It is now officially over.
 » 4 weeks ago, # |   0 Does anyone know how to solve the second gold problem, my solution was n^2 but got MLE.
 » 4 weeks ago, # |   +35 CaveNotice that you can create a tree structure from the cells. Iterate from the bottom layer to the top and merge subtrees into new subtrees. We can use a simple DP to find the answer. Nondec O(nk^3+qk^2)We can create a matrix for the DP transitions. We just need to precompute prefix products and prefix inverse products to answer range queries. Nondec O(nk^2+qk)300iq explained the solution to me so credits to him SpoilerorzBasically we use the matrix solution but notice that since the matrices are sparse, we can do multiplication in O(k^2). Then, we can precompute prefix sums of the matrices to answer queries in O(k).For P3 I have a bad solution which fortunately passes due to low constraints.Screencast
 » 4 weeks ago, # | ← Rev. 4 →   +43 Gold P3 is Balkan 2011 Trapezoid I think. Maybe that's why P1 is named "Time is Mooney"Anyway, very short spoilers: plat 1Basically, given some dependency between nodes, we have to count the subset of nodes that do not have depending nodes outside of the set. If we compress SCC, we can see that the DAG is a directed rooted tree. If we have that tree than counting is a simple DP. Constructing that directed rooted tree can be done by maintaining connected components for a suffix of rows, using disjoint sets. Idk if there is a simpler way to do this.code plat 2Divide and conquer gives $O((Q + N\log N) K^2)$. See code for details. imeimi told me that $O((Q+N)K^2)$ is possible too. It is same as what tmwilliamlin168 described.code plat 3We model the fall as a line $y = A_i - x \times i$.$O(n^2)$: Observe that the path is always like $i \rightarrow Q_i$ or $i \rightarrow j \rightarrow Q_i$. So just enumerate all $j$.$O(n\log n)$: Solve for all $i$ with $A_i < A_{Q_i}$. Possible $j$ satisfies $A_j < A_i$. So we have to find $j$ that has the smallest intersection with $Q_i$. Sweep in increasing order of $A_i$. Maintain a downward convex hull of lines. Then you can find it with a binary search (but linear search also works lmao). Case of $A_i > A_{Q_i}$ can be done similarly.code
•  » » 4 weeks ago, # ^ |   +16 My method for plat 1 was slightly different: alternate solutionFor each contiguous segment on a row, merge them to form 1 node, and draw directed edges to nodes in the row below if they are connected. We maintain a disjoint set data structure that keeps track of the groups of segments that, if the any of the segments in the highest row processed so far is flooded, will flood all of the segments. This disjoint set data structure also stores the number of ways to flood this group of segments. At first, all segments are a different group and the number of ways for each group is considered to be 1 (empty).We then process row by row from the bottom. When we process a segment, we merge that segment with the groups that are connected to it via the directed edges. When this segment is empty, those groups below that are disjoint do not affect each other, so we can simply multiply the number of ways for each group together when we merge.Once the merges are done for all segments in a row, each group now has the possibility of being entirely flooded by any of the segments in the top row. Thus, we add 1 to each of the groups that have a segment in this row.At the end, we still have a number of disjoint groups, so we multiply the number of ways to flood each one together to get the final answer code#include using namespace std; typedef long long ll; const ll mod = 1000000007; int N, M, cnt = 0; char grid[1005][1005]; ll par[1000005], sz[1000005], ways[1000005], tot = 1; int find_par(int x){ if (par[x] != x) par[x] = find_par(par[x]); return par[x]; } void merg(int x, int y){ int X = find_par(x), Y = find_par(y); if (X == Y) return; if (sz[X] < sz[Y]) swap(X,Y); sz[X] += sz[Y]; par[Y] = X; ways[X] *= ways[Y]; ways[X] %= mod; } struct node{ vector v; int l, r, num = 0; node(int _l, int _r): l(_l), r(_r){} }; vector segs[1005]; int main(){ ios_base::sync_with_stdio(false); cin.tie(0); freopen("cave.in","r",stdin); freopen("cave.out","w",stdout); cin >> N >> M; for (int i = 1; i <= N; ++i){ for (int j = 1; j <= M; ++j){ cin >> grid[i][j]; } } for (int i = 1; i <= 1000000; ++i){ par[i] = i; ways[i] = sz[i] = 1; } for (int i = N; i >= 1; --i){ int prev = 0, curl = 0, curr = 0, pt = 0; for (int j = 1; j <= M; ++j){ if (grid[i][j] == '.'){ if (prev == 0){ prev = 1; curl = j; } curr = j; } else if (prev == 1){ cnt++; auto x = new node(curl,curr); while (pt < 0) pt++; while (pt < segs[i+1].size() && segs[i+1][pt]->r < curl) pt++; while (pt < segs[i+1].size() && segs[i+1][pt]->l <= curr){ x->v.push_back(segs[i+1][pt]); pt++; } pt--; x->num = cnt; segs[i].push_back(x); prev = 0; } } } for (int i = N; i >= 1; --i){ set active; for (auto it : segs[i]){ for (auto x : it->v){ merg(x->num,it->num); active.insert(find_par(it->num)); } active.insert(find_par(it->num)); } for (auto it : active) ways[it] = (ways[it] + 1)%mod; } for (int i = 1; i <= 1000000; ++i){ if (par[i] == i) tot = (tot * ways[i]) % mod; } cout << tot << '\n'; } 
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   +16 Did not realize the equivalence of Gold P3 and Trapezoids. :| Admittedly, it didn't seem particularly original.For Plat 2 my $O(nk^2+qk^2\log n)$ solution with segment tree passes $q=10^5$, not sure whether you can pass $q=2\cdot 10^5$ with this?For Plat 3 we added some cases with large hulls which made one of our $O(n^2)$ solutions TLE, but apparently this didn't suffice.Solutions
•  » » 4 weeks ago, # ^ | ← Rev. 6 →   +8 Thank you for the solutions!
 » 4 weeks ago, # |   +22 Where can I see the all questions before the results come out (when would that be, though?), given the contest has now ended ?
•  » » 4 weeks ago, # ^ |   +23 all the problems can be found on the USACO discord server invite link
 » 4 weeks ago, # |   +17 http://usaco.org/index.php?page=jan20resultsSolutions and results are available.
 » 4 weeks ago, # |   0 For Silver Wormholes, I thought of using DSU ( Union Find ). Sort all edges in decreasing order of weights, and then after connecting each edge in this order, check if now all cows can sort themselves. So, I thought, let's view given array as permutation. Then we consider the index $i$ as value $i+n$. And then check whether each $i$ can reach $i+n$, but this is obviously TLE. How to do it faster? I have this feeling that there is a much easier approach.
•  » » 4 weeks ago, # ^ |   0
•  » » » 4 weeks ago, # ^ |   0 So, please correct me if I'm wrong. Instead of checking everything, in my code, if I checked each node in the smaller of the components while uniting, then similiar to the argument of merging sets in $O(nlogn)$ time, we have each element being checked only $logn$ times. Is that what I should have done?
•  » » » » 4 weeks ago, # ^ |   0 yes
•  » » » » » 4 weeks ago, # ^ |   0 Okay, thanks a lot!
 » 3 weeks ago, # |   0 For Silver problem "loan", does anyone have a proof for the correctness of binary search solution?I had to do a lot of math to prove it. Did I miss anything?
•  » » 2 weeks ago, # ^ |   0 What's wrong with the analysis? (aside from the "mlik" typo, I don't think anyone proofread this >:( )
•  » » » 2 weeks ago, # ^ |   0 I think it can be rather difficult to prove the correctness of binary search. It's easy to guess but hard to prove.
•  » » » » 2 weeks ago, # ^ | ← Rev. 2 →   0 Oops, I misunderstood. Suppose that $X_1 •  » » » » » 2 weeks ago, # ^ | 0 Oh, I didn't notice that monotonicity. I tried to prove$LHS - RHS \leq 0$and break it into several cases because of$\max$and$ \operatorname{floor}$function. That needs lots of work. Thanks!  » 2 weeks ago, # | 0 Can someone explain the maxmatch concept in the official USACO solution for the Silver loans problem? (line 11 onward in Nick's code) •  » » 2 weeks ago, # ^ | 0 You can verify (with a bit of math) that$\lfloor \frac{N-G}{X}\rfloor=Y$remains the same after$t=\lfloor\frac{N-G-XY}{Y}\rfloor$days (meaning that we subtract$Y$from$N$exactly$t+1$times). After subtracting$t+1$times, then$N-G