### xiaowuc1's blog

By xiaowuc1, 7 weeks ago, ,

Hi all,

The first contest of the 2019-2020 USACO season will be running from December 13th to December 16th this weekend. 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: Even though it is impossible to start the contest after 23:59 UTC-12, contestants who start right at that point in time still get a full four hours to do the contest. Therefore, please do not discuss the contest until 4:00 UTC-12 on December 17.

Edit 3: Results can be found here.

• +151

 » 7 weeks ago, # |   +11 When will the competition start exactly?
•  » » 7 weeks ago, # ^ |   0 You can choose to start any time in the interval provided, but once you start you have 4 hours and you cannot pause midway through.
•  » » » 7 weeks ago, # ^ |   +11 Well, I mean which hour exactly will we be able to participate? Since December 13th seems vague for me.
•  » » » » 7 weeks ago, # ^ |   +1 I believe you can start right at 0:00 UTC of Dec 13th and ends at 23:59 UTC Dec 16th, so begins and ends right at start and end of dates given in universal time.
•  » » » » » 7 weeks ago, # ^ |   +5 If I recall correctly, it is UTC-12 as opposed to UTC.
 » 7 weeks ago, # | ← Rev. 2 →   +35 Looking forward to not being able to solve any problems!
 » 7 weeks ago, # |   +4 Can somebody please say when will the contest exactly start.
•  » » 7 weeks ago, # ^ |   0 Read the comments above. Beginning at 0:00 UTC of Dec 13th and ending at 23:59 UTC Dec 16th, you can choose when to start the contest.
•  » » » 7 weeks ago, # ^ |   0 How many hours left?
 » 7 weeks ago, # |   0 Uhm, how do you participate in the contest? I have an account, and I see the contest dates on the right sidebar, but where can you start the contest for yourself?
•  » » 7 weeks ago, # ^ |   0 You can't until the contest officially starts.
•  » » » 7 weeks ago, # ^ |   0 Oh, alright, I thought it was starting at 0:00 UTC, not UTC-12
 » 7 weeks ago, # |   +19 The contest starts at 13 December 2019, 0:00, UTC-12https://www.timeanddate.com/worldclock/timezone/utc-12
 » 7 weeks ago, # |   +24 Contest has begun, you can sign up for any 4 hour period to take the contest until 23:59 UTC Dec 16th.GLHF everyone!
 » 7 weeks ago, # |   -136 Dang, a lot of partials...
•  » » 7 weeks ago, # ^ | ← Rev. 3 →   +24 Wait, are you allowed to say that?
•  » » » 7 weeks ago, # ^ |   -98 ...what I mean is that the problems just give a lot of partials ie. 1-3 test correct for some time complexity or 1-5 test cases correct for some time complexity, I'm not giving anything away.
•  » » » » 7 weeks ago, # ^ |   0 I would still refrain from discussing anything even minimally related to the contest.
•  » » » » 6 weeks ago, # ^ | ← Rev. 4 →   -26 Guys, good luck!! :)
•  » » » 7 weeks ago, # ^ |   -8 btw nice spelling
 » 7 weeks ago, # |   0 Will there be an editorial after the contest?
•  » » 7 weeks ago, # ^ |   +3 Generally they post tutorials for the problems, yes.
 » 6 weeks ago, # |   +65 Nice, enjoyed it.
 » 6 weeks ago, # |   +93 I did screencast for Platinum contest and will post it here after the end of the contest.
 » 6 weeks ago, # |   +25 Maybe a stupid question, but I couldn't find the memory limits anywhere?
•  » » 6 weeks ago, # ^ |   +15 From the instructions page under General Technical Details: Your program must be less than 100,000 bytes in size and must compile in 30 seconds or less. Unless otherwise stated, your programs will be limited to about 256MB of total memory use.
•  » » » 6 weeks ago, # ^ |   +5 Thanks
 » 6 weeks ago, # |   0 The contest has ended more than four hours ago. Pinging this to discuss solutions.Hints for platinum three? I have no idea how to deal with the condition on the number of inversions.
 » 6 weeks ago, # |   0 Did the contest end earlier than expected?I was still in my window but I was kicked out when submitting problems. I think the contest should not end so early.
 » 6 weeks ago, # | ← Rev. 2 →   +79 PieatersLet dp[l][r] be the max sum of weights if only pies from l to r can be eaten.Consider the last cow, it must have some pie k to itself.So we can transition dp[l][r] from dp[l][k-1]+dp[k+1][r]+(max weight of all cows having a starting index in [l, k] and an ending index in [k, r]).We simply iterate through all k, and for each k, we can use 2d rmq to transition in constant time (alternatively, we can do some simple precomputations in n^3).Total time is O(n^3).https://github.com/tmwilliamlin168/CompetitiveProgramming/blob/master/USACO/Contests/1920_1P/Pieaters.cpp SnowcowFirst compute the preorder dfs so all subtrees become ranges.Let's maintain the answer for each node in a segtree so in order to answer queries for the sum in a subtree, we can just perform a range query.For each color, maintain a set of the ranges that already contain that color.Note that if 2 subtree ranges intersect, then one must contain the other.When we add a new range r to a color, if the r is already contained, nothing happens. Otherwise, we remove all ranges which are contained by r and update those ranges with -1 in the segtree. Then we add 1 to range r in the segtree.Note that we can only remove a range once, so in total this works in O(nlogn).https://github.com/tmwilliamlin168/CompetitiveProgramming/blob/master/USACO/Contests/1920_1P/Snowcow.cpp TreedepthIt is useful to know how to compute the number of permutations of length n with k inversions in O(n^3) time.O(n^4): dp[n][k] -> dp[n+1][k], dp[n+1][k+1], ..., dp[n+1][k+1]O(n^3): use prefix sums to speed up the dpThe depth of i is the number of j such that the minimum of the range [i, j] (or [j, i]) is aj. Each such j is an ancestor of i. Note that it can be proven with induction.Let's count the case with j dp1[n+1][k], dp1[n+1][k+1], ..., dp1[n+1][k+1]dp2[n][k] -> dp2[n+1][k], dp2[n+1][k+1], ..., dp2[n+1][k+1]Additionally, add dp1[n][k] to dp2[n+1][k], since when index j is a min of all elements added so far, the depth is increased by 1.When we add indexes > i, we exclude the last step of adding dp1[n][k] to dp2[n+1][k].The DP takes O(n^3) time with prefix sums optimization, so this solution is O(n^4) total which is too slow.Notice that the DP for i consists i "ji transitions".We can compute the prefix DP of all "ji" transitions in O(n^3).To find the answer for i, we iterate over 0<=x<=k, and add the product of the answer of the prefix of "ji transitions" with k-x inversions.https://github.com/tmwilliamlin168/CompetitiveProgramming/blob/master/USACO/Contests/1920_1P/Treedepth.cpp Video of me typing and staring at a screen for hourshttps://youtu.be/oxcAyQmUof0
•  » » 6 weeks ago, # ^ | ← Rev. 2 →   0 My $\mathcal{O}(n^5)?$ pieaters solution passed... precomputing
•  » » » 6 weeks ago, # ^ |   +5 Well, the test data is essentially random.
•  » » » » 6 weeks ago, # ^ |   0 Are y'all going to add more test data like how you did for Cowland?
 » 6 weeks ago, # | ← Rev. 2 →   0 How to solve gold milkvisits ( the one about trees ).
•  » » 6 weeks ago, # ^ |   0 First, break the query into 2 queries (a, lca(a, b)), (b, lca(a, b)). So for every query (a, lca(a, b), MILK_TYPE), what is the lowest node u which is parent of node a such that milk type of cow in that node is equal to MILK_TYPE. For (b, lca(a, b), MILK_TYPE), let say that node is v. If the heights of u and v are smaller than lca(a, b), then the answer for (a, b, MILK_TYPE) is 0, otherwise is 1.Finding node u, v could be done with dfs and stack for each milk_type.
•  » » » 6 weeks ago, # ^ |   +3 "Finding node u, v could be done with dfs and stack for each milk_type." Could you elaborate ?
•  » » » » 6 weeks ago, # ^ |   0 You will store a list of queries to process offline for each node. For each milk type, maintain a stack of nodes that have it when you do DFS. When you visit $a$ or $b$, you just need to check if the last element you pushed to the required milk type stack is lower than $lca(a, b)$.
•  » » » » » 6 weeks ago, # ^ |   0 thanks.
•  » » » 6 weeks ago, # ^ |   0 how to solve the online version of Milk Visits(gold)in editorial it is written at the end to try and solve it in (M+N)log(N)
•  » » » » 6 weeks ago, # ^ |   +1 I have an online $O(N*\sqrt{N})$ solution. For colors with less than $\sqrt{N}$ occurrences, just check all nodes of that color in $O(1)$. For colors with frequency $\geq \sqrt{N}$ , we do $O(N)$ preprocessing per color to find the closest ancestor of that color. Using this we can find the answer for these colors in $O(1)$.
•  » » » » 6 weeks ago, # ^ | ← Rev. 3 →   +3 For each color, you can store a set of the vertices of that color, sorted by their index in the preorder traversal (like in snowcow). Then given a path $u-v$ and a color $c,$ Find the lowest node $x$ above $u$ of color $c$ in $O(\log N)$ using the set of color $c$. Test whether $x$ lies on the $u-v$ path using LCA in $O(1)$ or $O(\log N)$. Do the same for the lowest node above $v.$ Alternatively, use sparse segment trees as mentioned below.
•  » » » » » 4 weeks ago, # ^ |   0 Could you please share a pseudocode so I could visualize it better? I am having troubles with the time limit.
•  » » » » » » 4 weeks ago, # ^ | ← Rev. 2 →   0
•  » » » » » » » 4 weeks ago, # ^ |   0 Thanks.
•  » » 6 weeks ago, # ^ |   0 This might be really unnecessary but explicitly finding out the answer seemed easier to me.Let $f(u, c)$ be the number of nodes of color $c$ from root to node $u$, and $l = lca(u, v)$ Then our answer would be $f(u, c) + f(v, c) - 2f(l, c) + (color[l] == c)$Doing an euler tour will reduce adding information of node $x$ to a range update, and calculating $f(x, y)$ to a point query. These can be done easily by maintaining a sparse segment tree for each color.Requesting the solution of other two problems.
•  » » » 6 weeks ago, # ^ | ← Rev. 2 →   +3 Pump: just iterate through every possible minimum flow value and find the path with minimum cost.Cowmbat: Let $f_i$ be answer for $[1, i]$ and $cost_{c, i}$ be the cost to change prefix $[1, i]$ into $c$. We have: $f_i = min_{j \leq i - k} (f_j + min_{\forall c} (cost_{i, c} - cost_{j, c}))$ = $min_{\forall c} (min_{j \leq i - k} (f_j - cost_{j, c}) + cost_{i, c})$. Let $g_{i, c} = min_{j \leq i} (f_j - cost_{j, c})$, we can calculate $g_{i, c}$ from $g_{i - 1, c}$ in $O(1)$. Substitute it in: $f_i = min_{\forall c} (g_{i - k, c} + cost_{i, c})$
•  » » 6 weeks ago, # ^ | ← Rev. 3 →   0 (MilksVisits Silver). Here is how I solved it. First I make the tree weighted.#1 — Weight of edge == 0 if both nodes are the same ('H') or ('G') (depends on you) #2 — Weight of edge == 1 same as zeros .#3 — Weight of edge == 2 if types of nodes (U,V) are different.now we preprocess the date using binary lifting keeping track of the Max.Finally, to answer the queries I get the max (U,LCA(u,v)) (LCA(u,v),v).of course, there are 3 cases if max is (0 or 1) the answers depend on how you make the graph.if the max is 2 the answer always is 1.
•  » » » 6 weeks ago, # ^ |   0 You can store the highest ancestor with the same type. The answer is no if types of u and v are bad and the highest ancestor is the same.
•  » » 6 weeks ago, # ^ | ← Rev. 2 →   0 I had a different approach, using divide and conquer (kinda overkill though). First, notice that the answer for a query $(u, v, w)$ is $1$ iff when every vertex with type equal to $w$ is removed from the graph, $u$ and $v$ are in different components. Suppose we've already processed all the queries, i.e the solution is offline.Let $solve(l, r)$ be a function that finds the answer for every query $(u, v, mid)$ where $mid = (l+r)/2$. Now, iterate through every value $t$ from $l$ until $r$ and insert every edge $(a, b)$ from the tree in a DSU if either $T(a)$ or $T(b)$ are equal to $t$ and both $T(a)$ and $T(b)$ are different from $mid$. After this, to answer all queries $(u, v, mid)$, just check if $u$ and $v$ are in different components. If so, the answer is $1$.After this, remove all edges added in the DSU in the step above using a stack. To recursively call $solve(l, mid-1)$, we now have to add every edge $(a, b)$ from the tree where both $T(a)$ and $T(b)$ are not in the range $[l, mid-1]$ and either $T(a)$ or $T(b)$ are in the range $[mid, r]$.Then, to recursively call $solve(mid+1, r)$, erase all edges added in the step above again, and insert in the DSU only edges $(a, b)$ where both $T(a)$ and $T(b)$ are not in the range $[mid+1, r]$ and either $T(a)$ or $T(b)$ are in the range $[l, mid]$.Finally, remove all edges added previously in the DSU once again. Since we use DSU with rollback, the complexity of this solution is $O(n \cdot log^2 n)$.
•  » » 4 weeks ago, # ^ |   0 Hi, during the competition, I found another solution to this exercise. My solution is more complex than the one presented in the correction, however, and is slower. x)My solution is to maintain for each node of the tree all "open" requests (that is to say, passing through this node). All the "open" requests constitute in the merger: - sets of "open" requests from children - requests whose node is one of the ends of the path.We can maintain this effectively and simply with a set. To merge two sets of queries, simply make a DSU with the optimization of the smallest in the largest.If we try to add an identical request to the set, it means that we have reached the LCA of the nodes, and consequently that the request is "finished" (the ancestors of the current node will not be affected by the request). As a result, we can fire the whole request.Once this process is completed, we search in the set all the requests whose MILK_VISIT is the color of the current node. We put that they are possible, and we fire them from the set of requests so as not to have to consider them several times (which would lead to a considerable increase in complexity!).Sorry in advance for my English mistakes.
 » 6 weeks ago, # | ← Rev. 2 →   +52 I selected the problems for platinum. Hope it was interesting (but not too interesting for those of you at the top, that would mean that it's too hard :P).EDIT: Solutions are here.
•  » » 6 weeks ago, # ^ |   0 The platinum problems were really good! Thanks for setting them.
•  » » 6 weeks ago, # ^ |   0 Does this mean you will be working closely with USACO staff from now on?
 » 6 weeks ago, # | ← Rev. 3 →   0 How to solve silver P2 ?I was trying to do binary search on the time spent but I wasn't quite getting it.
•  » » 6 weeks ago, # ^ |   +18 I used sliding windows and few observations to solve the problem hint...instead of exchanging velocity we can exchange weights. first we calculate the variable t-the time to stop and then maintain a sliding window to find the number of meetings.best silver problem I have ever solved. Thanks Benq
•  » » » 6 weeks ago, # ^ |   0 I noticed this tooMy problem was calculating the time T
•  » » » » 6 weeks ago, # ^ |   0 if a particle is going leftwards add location and its weight to a array a. else add l-location and its weight to the array anow sort the array by distance(first value) and then keep iterating until the weight is atleast half of total weight.the time is the distance of the last index iterated
•  » » » » » 6 weeks ago, # ^ |   0 Thanks alot!
•  » » 6 weeks ago, # ^ |   0 Ignore weight's and collisions first. Calculate times then cows are at locations 0 and L. Notice that the order of increasing x is the same as increasing time in location 0 (contrary at position L). From this, we can find out T. To calculate collisions we can once again ignore weights and collisions. For every cow going to the right calculate the number of cows moving to the left in an interval $[x, x + 2T]$.
•  » » 6 weeks ago, # ^ |   0
•  » » » 6 weeks ago, # ^ |   0 we need to go deeperhttps://codeforces.com/contest/652/problem/F
•  » » » » 6 weeks ago, # ^ |   +16 Yep, I've done both of these (but I thought the weights idea was interesting enough to make another ants problem).
 » 6 weeks ago, # | ← Rev. 2 →   0 Does anyone think 795/1000 enough to pass silver? I was hoping to qualify in-contest but couldn't fully solve P2
•  » » 6 weeks ago, # ^ |   +1 There's no guarantee about the cutoff, but seeing how it's generally around 750 and this silver contest was harder than usual, it should be enough
•  » » 6 weeks ago, # ^ |   0 Congrats, you made gold!!!
 » 6 weeks ago, # |   +3 For gold P3, was NMlogN not meant to pass? Thanks
•  » » 6 weeks ago, # ^ |   +3 I'm not aware of such a solution.
•  » » » 6 weeks ago, # ^ |   0 It's just the NMK solution but with segment tree instead.
•  » » » » 6 weeks ago, # ^ |   0 Just be aware of memory, I guess it can get TLE because of memory access.
•  » » » » » 6 weeks ago, # ^ |   0 Ooof O(MN) memory
 » 6 weeks ago, # |   0 how to solve p3 on plat with G.F?
 » 6 weeks ago, # |   +16 When the results will be posted ?
•  » » 6 weeks ago, # ^ |   0 The results are posted now!!!
 » 6 weeks ago, # |   +2 In Bronze P3:Generating all permutations + sorting got AC, but I was wondering if there is a more efficient solution, for example is it possible to construct the result directly from the conditions?
•  » » 6 weeks ago, # ^ |   0 As $n$ is very small ,your algorithm must get AC. You can also build a graph according to the relatives.
 » 6 weeks ago, # |   +1 When will the standings be posted ?
 » 6 weeks ago, # |   +10 Results and editorials are out at http://usaco.org/index.php?page=dec19results!
 » 6 weeks ago, # |   +1 Anyone else that cant see how many points they had on the contest? I got full AC on P1 and P2, and on P3 I had first 8 test cases correct (first 2 subtasks) and rest was WA, that should put me at 833 points right? Enough to be promoted to Platinum division but I checked on my account profile and I'm still Gold and nowhere I can see how many points I had.
•  » » 5 weeks ago, # ^ |   0 They judge by last submission so did your last submissions fail?
•  » » » 5 weeks ago, # ^ |   0 No, all my last submissions were like I said above :/
 » 6 weeks ago, # |   0 Could someone help me find a bug in my solution to Snowcow (Plat 2)?I am getting WA on test cases 9 and 10 (I can't test it in my IDE because there is StackOverflowError).https://github.com/tommattgeorge/CompetitiveProgramming/blob/master/snowcow.java
•  » » 4 weeks ago, # ^ |   0