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.
When will the competition start exactly?
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.
Well, I mean which hour exactly will we be able to participate? Since December 13th seems vague for me.
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.
If I recall correctly, it is UTC-12 as opposed to UTC.
Looking forward to not being able to solve any problems!
Can somebody please say when will the contest exactly start.
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.
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?
You can't until the contest officially starts.
Oh, alright, I thought it was starting at 0:00 UTC, not UTC-12
The contest starts at 13 December 2019, 0:00, UTC-12
https://www.timeanddate.com/worldclock/timezone/utc-12
Contest has begun, you can sign up for any 4 hour period to take the contest until 23:59 UTC Dec 16th.
GLHF everyone!
Dang, a lot of partials...
Wait, are you allowed to say that?
...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.
I would still refrain from discussing anything even minimally related to the contest.
Will there be an editorial after the contest?
Generally they post tutorials for the problems, yes.
Nice, enjoyed it.
I did screencast for Platinum contest and will post it here after the end of the contest.
Maybe a stupid question, but I couldn't find the memory limits anywhere?
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.
Thanks
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.
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.
Let 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
First 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
It 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 dp
The 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<i first, the other case is similar.
Let dp1[n][k] be the number of permutations and dp2[n][k] be the sum of number of j<i satisfying the condition above over all permutations.
We start with the permutation only containing i. We build the permutation by adding i-1, i-2, ..., 0. Then we add i+1, i+2, ..., n-1.
When we add an index j < i,
dp1[n][k] -> 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 "j<i transitions" and n-1-i "j>i transitions".
We can compute the prefix DP of all "j<i transitions" and "j>i" 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 "j<i transitions" with x inversions and the answer of the prefix of "j>i transitions" with k-x inversions.
https://github.com/tmwilliamlin168/CompetitiveProgramming/blob/master/USACO/Contests/1920_1P/Treedepth.cpp
https://youtu.be/oxcAyQmUof0
My $$$\mathcal{O}(n^5)?$$$ pieaters solution passed...
Well, the test data is essentially random.
Are y'all going to add more test data like how you did for Cowland?
I hate to necropost but...
In the third task when you say
dp[n][k]->dp[n + 1][k],dp[n + 1][k + 1],...,dp[n + 1][k + 1], what goes in the...section?Maybe the k+1 is wrong, it may be like k+n or k+n+1.
How to solve gold milkvisits ( the one about trees ).
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.
"Finding node u, v could be done with dfs and stack for each milk_type." Could you elaborate ?
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)$$$.
thanks.
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)
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)$$$.
How do you check whether a node exists in a path or not? can you please elaborate?
Using DFS times.
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,$$$
Alternatively, use sparse segment trees as mentioned below.
Could you please share a pseudocode so I could visualize it better? I am having troubles with the time limit.
Solution
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.
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})$$$
(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.
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.
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)$$$.
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.
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.
The platinum problems were really good! Thanks for setting them.
Does this mean you will be working closely with USACO staff from now on?
How to solve silver P2 ?
I was trying to do binary search on the time spent but I wasn't quite getting it.
I used sliding windows and few observations to solve the problem
...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
I noticed this too
My problem was calculating the time T
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 a
now 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
Thanks alot!
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]$$$.
https://atcoder.jp/contests/agc013/tasks/agc013_c
we need to go deeper
https://codeforces.com/contest/652/problem/F
Yep, I've done both of these (but I thought the weights idea was interesting enough to make another ants problem).
Does anyone think 795/1000 enough to pass silver? I was hoping to qualify in-contest but couldn't fully solve P2
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
Congrats, you made gold!!!
For gold P3, was NMlogN not meant to pass? Thanks
I'm not aware of such a solution.
It's just the NMK solution but with segment tree instead.
Just be aware of memory, I guess it can get TLE because of memory access.
Ooof O(MN) memory
how to solve p3 on plat with G.F?
When the results will be posted ?
The results are posted now!!!
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?
As $$$n$$$ is very small ,your algorithm must get AC. You can also build a graph according to the relatives.
When will the standings be posted ?
Results and editorials are out at http://usaco.org/index.php?page=dec19results!
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.
They judge by last submission so did your last submissions fail?
No, all my last submissions were like I said above :/
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
https://codeforces.com/blog/entry/21472?#comment-261237