Hi all,
The first contest of the 2020-2021 USACO season will be running from December 18th to December 21st 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! There are new changes to how USACO contests are run — the most notable change is that I/O is no longer done via files. Please consult the official rules for all the changes.
Edit 2: Although the contest window is almost over, please do not discuss the contest until everyone has finished it. The contest window should close four hours after it officially ends since folks who join at the last minute purportedly still get a full window, in which case the contest ends at this time.
Edit 3: The contest is officially over — hope everyone enjoyed the contest! Results should hopefully be ready by the end of the week.
Edit 4: Results are out!
What time zone are the dates on the website referring to? I saw EST mentioned somewhere on the website, but that wasn't specifically talking about the contest.
The contest page will have the exact rules, but I think that it's typically the most permissive possible bounds; the start time will be December 18th 00:00 UTC+13, and the end time will be December 21st 23:59 UTC-12, or something like that.
Looking forward to some more COWVID puns!
Thank you xiaowuc1
The contest window should close four hours after it officially ends since folks who join at the last minute purportedly still get a full window, in which case the contest ends at this time.
The contest closes Dec 21 at 23:59 UTC-12 time (even if your personal clock is still running at that time, so do not wait until the very last minute to start!).
Explicitly not according to new usaco rules. I'm curious if anyone has ever done this (previous year or this year) and can confirm it was ever the case. I wouldn't be surprised if they never impl to actually cut it off tho :clown:
I'm now doing it!
The contest window was just closed. Don't ask me why I know that, I was kicked out.
Hope you are well :(
Can someone explain the solutions to the platinum problems?
so is the contest over or not yet?
Yes it is
ok i was curious about the solution to the second silver problem the one about subsets
I also was not able to solve it. I solved the other 2 the graph one and the transitivity one but wasn't able to solve this question.
me too but i didnt proof the graph one tho
Here's the solution to Silver 2:
Sort the points by x-coordinate.
The first observation to note is that a rectangle is a contiguous range of x and y coordinates, so it will be a contiguous segment in our array (now that it's sorted).
Brute force the leftmost and rightmost points in the subset. It is easy to see that none of these groups overlap, and they cover all possible subsets. Now you can disregard any points with an x coordinate out of the range that they cover. Because you are putting the endpoints of the current range in the current subset for sure, all of those points that are within them must be taken with the current subset. However, you have a choice to take all of the points above them and below them (but within their x-coordinate range). You can choose anyone of the points above their range, and any one of the points below their range and extend the y-coordinates of the rectangle so that they are covered. Therefore, the answer for some fixed x-coordinate bounds is:
$$$(1+numberofpointshigher)*(1+numberofpointslower)$$$.
Here is my accepted code.
Let me know if you have any questions.
The contest is officially over as just now the contest window got over.
Can we discuss now?
Anyone have a java solution for Bronze #3 that works for all cases?
hint:sort the cows looking to the north by their x value , and the others by their y value
It was my first time in USACO so I entered bronze division. I just did normal brute force no sorting needed lol. I think your solution has a better time complexity as mine is around $$$O(N^3)$$$. But anyways, constraints were very small.
It was a greedy solution. We sort the North ones on basis of x co-ordinates and East ones on basis of their y coordinate.
Now we can see that iterate in North ones and for every North direction, I iterate in East ones.
I find the expected point of meeting and checked whether it was possible for me to block a cow or not. If yes I updated the value and continued traversing further
can u give me your code for this problem?
Does anyone know the solutions to the Gold problems?
https://github.com/bqi343/USACO/tree/master/Contests/USACO%20Solutions/2020-21/Dec
This contains solutions to all the problems.
When will we be able to upsolve the problems?
Usually the results come out Thursday-Friday (ish). After that, the problems will be open to upsolve.
UPD: Results are out early!
Thanks a lot
some experienced person please predict the ratings of the silver problems...
My very rough guess would be 1400, 1800, 1700.
Can someone please explain the solution to cowmistry platinum? Thanks.
So the xor problem right? Basically just simulate the process of going down a trie of the binary representation with 3 paths at the same time, keeping which pairs have xor smaller than K for sure (I did this with a submask of 3 bits).
Then realize this is sort of small-to-large in the splitting points and when you split for the second time you'll have a path that's already smaller than K in pairwise xor in both pairs, in this case you can take any value below this node and solve for only 2 paths (actually whenever a path is smaller than K for sure with the others, just do this to reduce the number of paths).
Also treat nodes that have all possibilites under it as some special node that you're able to use 0 or 1 in any way (but still keep the xor pair information).
This with memoization using a map was enough for the complete problem and it's probably barely hackable but if I use some unordered map it should be way faster. Also this can be coded without the memoization at all but implementation seemed too hard for me. Probably the intended solution is easier to code though.
It's problem 3
How do you solve gold problem 3? I have a hashing solution that was too slow (and had some collisions).
You can use XOR-hash, note that order doesn't matter and points can't be repeated, so assigning a random integer to each point and for hashing elements, just use xor of their random values, with 64-bits integers the probablility of colision is really low, and you can use a vector instead of a set to count the number of differents and improve the algorithm, however the constraints allow to do it without optimizations.
You need to fix $$$L$$$ and $$$R$$$, and then insert to the set the hashes of every square of size $$$R - L + 1$$$ with its left edge equal to $$$L$$$ and its right edge equal to $$$R$$$, to do this you can do a sweep line/sliding window over the y-axis, in total you will only consider $$$O(N^3)$$$ squares if you fix each pair of $$$L$$$'s and $$$R$$$'s.
I've noticed that
mt19937
doesn't work on USACO. It compiles, but gives the verdictRuntime Error or Memory Limit Exceeded
. Is there any good alternative for random number generation? (rand
isn't a good enough generator)I just use
srand(time(null))
and normalrand()
, and for 64 bit integers( (long long) rand() & (INT_MAX) ) * INT_MAX + rand()
If anyone is interested, here's my implementation using this approach: link
Results are out at http://usaco.org/index.php?page=dec20results. Very fast!
For some reason, I can't see top scorers for both the Bronze and Silver Divisions. Does anyone know why that's the case?
Why there's only results for top scorers?
Presumably so people don't get angry about camp selection, ie other factors, most importantly grade level, come into play when selecting the finalist camp. However you should be able to see your exact place number among all pre-college students (which I'm assuming you are, but probably same is similar for college+) in the paragraph above where it shows the contest problems.
Why aren't there any results for the Bronze and Silver Divisions? I can see them for the Gold and Platinum divisions though...
does anyone have a working code for gold 2's subtask 2?even though the editorial explained the dp,I still find it difficult to implement the main dp
I added it here.
thanks