Hi all,
The first contest of the 2022-2023 USACO season will be running from December 16th to December 19th this weekend. Good luck to everyone! Please wait until the contest is over for everyone before discussing anything contest-related (including but not limited to your scores or anything about the problems).
For those unfamiliar with the USACO contest format, please refer to the contest instructions and rules. We provide a short FAQ but folks should read all the rules carefully.
I have a question about the contest. Where do I ask it?
Email the contest director via the instructions above. Do not post anything publicly about the questions (including but not limited to your scores, how you felt about the problems, any content of the problems, etc) until after the contest is over for everyone. Do not DM me or anyone else affiliated with USACO, only the contest director can assist you. The contest director does not monitor Codeforces, this blog post is merely a courtesy to inform other people of the contest.
When can I enter the contest?
This contest runs until December 19th, 23:59 UTC-12 and is four hours long. The URL for the contest page can be found here.
If I submit multiple programs, which one gets evaluated?
Only the last submission will be evaluated for official scoring purposes.
Can I use prewritten code / templates?
No.
Am I allowed to use outside resources during the contest?
You may only refer to language documentation.
Why didn't I get an email from USACO when I registered my account?
Follow the directions on the USACO website regarding Gmail Delivery Issues to contact the contest director.
Can I solve problems in Rust?
No, the only languages supported are C, C++, Java, and Python. Consult the instructions for language-specific technical details.
Will Rust support be added?
Probably not. Petition IOI to add Rust support first.
hopefully before 2022 is over i will not be missing the shiny gold coloring on both cf and usaco :)
gl everyone!
You will miss it by getting platinum color in usaco
Congrats on scoring 866 in Gold (and AKing silver); this qualifies for Plat without any doubt.
Waiting for my turn next month now...
ty bestie
ur turn will come jan when u join me :DDD
Yeah you really cracked off this contest. And to anyone else hoping to qual for plat, don't forget that jan and feb are still there.
I want gold too
omeganot, more like omegaorz. If you don't get gold, I'm screwed in silver
hyper orz
My first USACO contest. I hope I can get to gold
Can we write some template at the beggining of the contest?
(Sorry, it will be my first USACO contest).
No, you are not allowed to use any prewritten code during the contest. All code you submit must be written within the time of the contest.
edit: i can't read, see below
how will u catch them? I used template in previous usaco contest but nothing happened.
man really admitted to breaking the rules :sob:
Can we all realize that this entire discussion really just started about writing a template during the contest
wait i actually can't read
JanBobi Yes you can write the template after the beginning of the contest. So you can write it out from memory and then copy and paste it for your other submissions.
Ok, thanks!
Can I copy a piece of text unrelated directly to competitive programming from the internet?
Not too sure, but USACO rules say that you can only search up stuff relating to the syntax of your language. So I guess (maybe?) you can copy-paste really basic stuff like take input, initialize vector, etc. but of course there's not much point of that.
What if I have prewritten not-code. Can I copy it to my source code in contest?
I assume not, otherwise you could just write whatever templates you have in pseudo-code and convert it to C++ during the contest :P
What if I have a prewritten piece of literature. Can I copy it to my source code in contest?
I'm sure the USACO grading servers will enjoy reading some Shakespeare but they'll also refuse to compile it.
Oh, please have mercy on me
Take it easy on my heart
Even though you don't mean to hurt me
You keep tearing me apart
Would you please have mercy on me?
I'm a puppet on your string
And even though you got good intentions
I need you to set me free
I'm begging you for mercy, mercy
I'm begging you, begging you, please, baby
I'm begging you for mercy, mercy
Ooh, I'm begging you, I'm begging you, yeah
Don't go breaking my heart
I couldn't if I tried
Honey if I get restless
Baby you're not that kind
Don't go breaking my heart
You take the weight off of me
Honey when you knock on my door
Ooh, I gave you my key
Woo hoo
Nobody knows it
When I was down
I was your clown
Woo hoo
Nobody knows it
(Nobody knows... it)
Right from the start
I gave you my heart
Oh-oh I give you my heart
glhf!
yall got this <33
Are the exact times when the contest window is open and closed published anywhere? Also, what is the duration?
I believe it runs from 5AM on the 16th to 5AM on the 20th (both times in Pacific Standard Time; it's 1PM UTC).
You can take the contest in any 4-hour window over those 4 days. Note that if you start too late, the 4-day contest period may end before your 4-hour window ends.
More information can be found here.
xiaowuc1, could you add this to the post?
I think you were off by 1h. Should be 4am pst unless my memory very bad since I always took in last 4 hours possible :clown:.
If you are right, time period is 3 days, not 4 days. The correct time period is 4 days.
Oh right, thanks.
The exact parameters are not published until the contest goes live, I have updated the blog post accordingly. This contest runs for four hours and closes on December 19th at 23:59, UTC-12.
Hope I get silver! Have been practicing hard recently! Good luck to everyone else!
Excited to get smashed by new problems! YaYYYYYYY
Can I participate in USACO contest. If yes, how?
By creating an account!
Hi, I also want to create a account, but not able to create at http://www.usaco.org/index.php?page=register,Is there any other page for creating?
You may have to contact Brian Dean to make your account then.
It's going to be super fun bricking silver. Edit: Bricked Silver. Jesus Christ, I don't even remember a time when I wasn't in silver smh.
[deleted]
Whom can I ask a question about P3 in Silver?...
I'm getting the strangest verdict in my entire life
My answer for the sample is correct, but I keep getting this:
I tried to print "W", and it still says that my answer is incorrect D:
At the bottom of the contest page: “Please email the contest director ([email protected]) if you come across any technical problems.”
Thanks! But I highly doubt that I will recieve an answer till the end of my virtual contest(
USACO grading is sometimes strict, you may have to put exactly one newline at the end of your output. But more likely they are having a grader bug which you will have to wait to get fixed D:
Thanks! It would be sad if there's a bug, because I also wanted to try Gold and Platinum :D
The checker is space sensitive.
Damn! Thank you so much, now it works!!!
deleted
You are not allowed to discuss anything about the problem during the contest window. Please delete this comment immediately. If you have any questions about a problem, email the contest director at [email protected].
Hi! I am facing an issue participating in USACO.
I submitted my code to problem A (Gold), and it kept telling me "Waiting for Available Grading Server" for minutes and then ended up with "Grading Failure due to Internal Error; Contact USACO Staff".
What should I do now, or am I going to end USACO2022DEC contest without any valid submission? :(
UPD: The grading server works now.
Reminder: this blog post is not actively monitored by the contest director. The contest site provides an email address to contact about technical problems; posting here is ineffectual at best and, in most cases (including all three clarification requests posted in this thread), doing so communicates information about the problems/your performance, which is prohibited by the rules of the competition.
.
.
I think the deadline has passed? Can we discuss the solution now?
I really liked the problems from gold division, especially "Mountains".
For the platinum division, I liked the problems, but "Breakdown" is much harder compared to the other two problems. I got AC on "Palindromes" and "Making Friends" in ~1h30min and spent the rest of the contest trying to solve k = 5 and optimize k = 4 (I solved it in n³ but was getting MLE).
Does anyone that solved "Breakdown" (or at least k >= 5) can give me some hints? Thanks in advance :).
How to solve "Mountains"? I can only manage to solve it with QN^2 , pass half of the testcases.
I also wondering how to solve the rest two. For "Bribing Friends" I can only solve it with dp[2][costa][costb] pass 15/20, and for "Strongest Friendship Group", although I passed all the test cases, what I do is just enumerate minimal degree and combine with SCC
for bribing friends notice that for some subset of cows, it's optimal to use ice creams on the smallest x cows. So this also means that using that greedy on some subset will never result in more than one cow being split between money/ice creams used on it. So sort by x value, run one knapsack dp on the ice creams in O(NB), then transition to using moneys through the one(or zero) split cow, and run another knapsack on money in O(NA).
Thanks~, I got it.
Just wondering how do you come up with the greedy? The left is just standard problem with a little trick
Can you elaborate on p3 (Strongest Friendship Group)?
By the way I too passed half of the testcases in Mountains and got 15/20 in Bribing Friends so I guess p3 kept me from reaching Plat :)
For P3.
just enumerate the minimal degree of the subgraph
for the given degree d, erase all the nodes that degree < d and also remove the edges.
go back to 2 and make the subgraph "converge".
And Also I use lots of constant optimization to pass all the testcases.
Wondering is this the intended solution?
Maintain the order of edge removal. Then, using DSU, add edges to the empty graph in reverse order, so that connected components are only merged and we can easily keep track of the maximum size in $$$O(n+m\alpha (n))$$$ instead of brute-forcing in $$$O((n+m)\sqrt{m})$$$.
I had a $$$O(m\log n + n\alpha(n))$$$ solution, where I first maintain a set of vertices that are not erased, and in each iteration, I erase the vertex with the lowest degree and update the adjacent vertices. I store the order of removal in an array, and reverse the array. Then, I maintain a DSU and then iterate over the array, adding edges in the DSU.
Solution of "Bribing Friends":
I don´t remember what was used to get the discounts, but I will assume it is cones.
Let's order the friends from greatest to smallest Xi, we can prove that if our optimal answer is the set of friends, $$$id_1,id_2...id_k$$$, such that id is increasing, we will take a suffix $$$(i+1,k)$$$ for free (apply the discount until it is free), paying a total of 0 mooneis and $$$C_{id_j}*X_{id_j}$$$ cones for every $$$i+1 <= j <= k$$$., and take a partial discount for $$$id_i$$$, paying a total of $$$C_{id_i} - \lfloor ConesRemaining/X_{id_i} \rfloor$$$.
In the optimal answer, we use only mooney from $$$1$$$ to $$$i-1$$$, mooney and cones in $$$i$$$, and only cones from $$$i+1$$$ to $$$n$$$. Now we can solve this problems with two DP:
$$$dpc_{i,j}$$$ = maximum popularity solving for $$$(1,i)$$$, spending j mooneis and 0 cones.
$$$dpx_{i,j}$$$ = maximum popularity solving for $$$(1,i)$$$, spending j cones and $$$at$$$ $$$ most$$$ A mooneis.
Transitions:
$$$dpc_{i,j} = max(dpc_{i-1,j}, dpc_{i-1,j-C_i}+P_i)$$$
$$$dpx_{i,j} = max(dpx_{i-1,j}, dpx_{i-1,j-C_i*X_i}+P_i, dpc_{i-1,A-\lfloor j/X_i\rfloor})$$$ -> You also need to check whether you can use all cones $$$j$$$ cones remaining on $$$i$$$.
The answer will be $$$max(dpx_{n,j})$$$ for every $$$1 <= j <= B$$$.
Hope that this can help you to understand the problem :)
Thank you very much!
It seems that I can get the intuition that why we need to sort by xi desc then use find the suffix of friends by exchange Cones (maybe it will be more possible to get the "P freely")
But I have two questions about it.
Although it's correct and meet my intuition, but can we prove it is correct?
When you are solving this problem, how do you come up with this idea? It's hard for me to come up with this.
To prove that the optimal answer is in this format: If we fix the set of friends that we want to choose, and now we are trying to discover the least amout of mooney spend to pay them, the best way to lower the total amout of mooney spend is applying the discount in the friend with the smallest Xi, since it will always decrease the total amout of mooney spend by 1. So the "greedy" ideia is to apply the discount to the friend (from the set of friends that we want do choose) with the smallest Xi until it's not free, and them get doing it until I cannot apply any new discount.
To come up with this ideia I think about how the optimal answer would look like and how I can apply some restrictions to the answer so I can optimize my DP. When the problem looks like a DP problem and I have to reduce the amout of states, it is very usual to try to restrict the answer.
your answer really helps!
If you go backwards you can easily update 2-edge distance (and 1-edge distances of course) between all pair of vertices. That's already enough for $$$k<=4$$$ — you just check all possible middle vertices on the path from 1 to $$$n$$$.
Now we also need to keep updated 3-edge distances from 1 to every vertex and from every vertex to $$$n$$$. Consider 3 cases where the new edge is the first, second or third in the new path, and use 2-edge distances which we already have.
And now also keep 4-edge distances from 1 to every vertex and from every vertex to $$$n$$$. When the new edge is second or third in the path, the middle vertex is one of the ends of the new edge and the update is $$$O(1)$$$ for each vertex considering we already have all 2-edge distances. When the new edge is the last we reuse 3-edges distances from 1 or to $$$n$$$. When it's the first we need to use $$$O(n)$$$ for each vertex, but it only happens when the added edge starts in 1 or ends in $$$n$$$.
I got AC in 1.4 second by just running Dijkstra every time I add a new vertex, starting from the tail of the added edge. I run Dijkstra on modified graph where vertices are (k, v) for v any original vertex and 0<=k<=K. I guess tests were weak.
I ran nsqrt(m) and then binary searched on TLE/WA with how far up the sqrt(m) I really search before breaking :) weak pretests op
How to solve "Reverse Engineering" problem from Bronze division?
Bump, also couldn't figure out.
You can incrementally build the program one if statement at a time until either your program can handle all the pairs or it's impossible to distinguish them.
I think the last window is still active as one can start their window at last second and will still get 4 hours. So, I think it would be better to wait for discussion till the last 4 hours end, which ends in about 2 hrs 35 mins from the time of this commentEdit : Wrong Info
The contest closes Dec 19 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!).
oh ok, my bad.
How do you guys find the difficulty of bronze problems ? I think that the first one is pretty easy , the second one is very nice and suitable for P2 and the third one is very hard :(
The first one is very easy
Platinum Solutions:
First reverse the process, adding rather than removing edges. Use meet in the middle: consider computing, for each vertex, the shortest path with $$$\left\lfloor \frac{K}{2} \right\rfloor$$$ or $$$\left\lceil \frac{K}{2} \right\rceil$$$ edges from vertex $$$1$$$ and to vertex $$$n$$$, respectively, so that each answer can be found in $$$O(n)$$$ time afterwards by enumerating the middle vertex. These two tasks are similar, so let's just consider the first one (finding shortest paths from vertex $$$1$$$). Note that we now only have to worry about paths of length up to $$$4$$$. There are several possible approaches from here. Here's the one I used:
We keep track of $$$f(i, j)$$$, the length of the shortest path from vertex 1 to vertex $$$i$$$ of length $$$j$$$ ($$$j \le 4$$$), and $$$g(i, j)$$$, the length of the shortest path from vertex $$$i$$$ to $$$j$$$ of length 2. When adding an edge $$$u \to v$$$, first update $$$g$$$ in $$$O(n)$$$ time by going over which edge precedes or follows the edge just added. Then:
Since there are $$$O(n^2)$$$ edges of the first kind and $$$O(n)$$$ edges of the second, and extracting the final answer from the two "halves" takes $$$O(n)$$$ time per query, the final complexity is $$$O(n^3)$$$.
Interpret the problem as a graph with cows as vertices and friendships as edges.
Main Lemma: Two vertices $$$u$$$ and $$$v$$$ will become friends at some point iff there exists a path from $$$u$$$ to $$$v$$$ such that the ID of all vertices on the path (except endpoints) is less than $$$\min(u, v)$$$.
Proof: Suppose such a path exists. Note that all the non-endpoint vertices on the path will be deleted before either $$$u$$$ or $$$v$$$ is. Consider the deletion of a single vertex $$$w$$$. If $$$w$$$ is not on the path, the path remains valid. If $$$w$$$ is on the path, after deleting it the two vertices adjacent to $$$w$$$ on the path are now adjacent, so $$$w$$$ can be deleted from the path while keeping the path valid, shrinking its length by 1. Eventually, after every internal vertex on the path is deleted, the path would reach a length of 1, i.e. become a direct edge between $$$u$$$ and $$$v$$$, as desired.
Conversely, suppose no such path exists. Then after deleting a vertex with ID less than $$$\min(u, v)$$$, no new path satisfying the condition could possibly be formed (since the deletion only lets us bypass a low-ID vertex, but we need to bypass high-ID vertices to form such a path). Ultimately, vertex $$$\min(u, v)$$$ will be deleted, with no path satisfying the condition (and therefore no direct edge between $$$u$$$ and $$$v$$$) ever existing. $$$\square$$$
Now, for each $$$u$$$, we will count the number, $$$f(u)$$$, of $$$v > u$$$ such that the edge $$$(u, v)$$$ will eventually be formed; subtracting $$$m$$$ from the sum of this quantity over all $$$u$$$ gives the final answer. To do that, insert the vertices into the graph one by one by increasing order of ID. For each connected component, maintain the set of vertices adjacent to the component that has not been inserted into the graph yet, using, say,
std::set
(note that after inserting the first $$$u$$$ vertices, $$$f(u)$$$ is just the number of elements in the set for the connected component $$$u$$$ belongs in). Using small-to-large merging on these sets, the problem can be solved in $$$O(n \log^2 n)$$$ time.Consider a single interval for which we want to compute the number of swaps needed.
Suppose that there are an even number of H's in it. Then the first H will be paired up with the last H, the second with the second-to-last, and so on. To align the first pair of H's, the number of swaps needed is twice the distance between the midpoint of the two H's and the midpoint of the whole interval (taking "half-positions" into account). The answer for the interval is just the sum over all pairs of H's. The case for an odd number of H's is similar, except that there is also a middle H to deal with and that it is possible that the task is impossible if the length of the interval is even.
Let's calculate the contribution of the intervals with an even number of H's. Enumerate the middle pair (of adjacent H's) and expand outward, one pair of H's at a time. Then, for a fixed set of pairs, the number of swaps is a function of the midpoint of the interval, and it is a piecewise linear function (sum of absolute value functions, one per pair), which can be maintained with Fenwick tree. Then for each interval corresponding to this set of pairs, we can evaluate this function at the midpoint in $$$O(\log n)$$$ time. The total complexity is $$$O(n^2 \log n)$$$ since each interval is processed once.
Handling the intervals with an odd number of H's is similar, but we enumerate the center H instead of the center pair, and we also have to check for each interval whether the task is possible.
Problem 2 can be solved in $$$O(nlogn)$$$ and Problem 3 can be solved in $$$O(n^2)$$$.
I suppose the $$$O(n^2logn)$$$ solution for Problem 3 shouldn't pass.
I used a $$$O(n²logn)$$$ solution with BIT and It worked in ~1300ms
Problem 2 can actually be solved in $$$O(n \alpha(n))$$$ time by counting contribution by the larger of $$$u$$$ and $$$v$$$. Consider the "union-find tree" of components that we encounter as we build the MST. Then, the contribution of $$$v$$$ is the total number of ancestors (without multiplicity) of the smaller vertices it has direct edges to. This requires only LCA queries to answer, which we can do with Tarjan's offline LCA algorithm.
We can speed this up further to $$$O(n)$$$ time using linear-time MST and linear-time LCA, but those both require using the WordRAM Model.
Use a pointer and a bucket instead of Fenwick tree. When you you want to query the sum of some prefix, move the pointer to this position and subtract/add the values on the positions passed. It can be shown that the distant sum is $$$O(n^2)$$$
Did anyone else feel that the silver and gold divisons were slightly easier than average this time?
I AKed silver after giving up on USACO last year and am motivated to try to reach Plat in the next 3 contests :)
thoughts on cutoff & 750?
um tbh i wouldn’t count it on too hard
I thought this contest was easier than last open quite a bit (in terms of getting over 800 points) and last open had a 800 cutoff..
It seems that some people's $$$n^2\log n$$$ solution can pass problem 3. My $$$n^2$$$ even runs slower than $$$n^2\log n$$$.
Can anyone provide solutions for the bronze problems?
you can also solve the problems yourself until someone posts the solutions
What is the silver cutoff going to be? Any estimates/guesses?
couldn't ak silver
Results are available in the website
The low plat promotion cutoff made for a nice Christmas gift :)
Same here, go to Platinum luckily
There are some solutions with wrong time complexity can pass all the tests of the Platinum problem Breakdown. For example, run Bellman-Ford after adding every edge can pass the problem in $$$O(kn^4)$$$ and it is much faster than my $$$O(n^3)$$$ solution. Besides, the wrong solutions is much easier than the right solution.
When I open my submission for Bribing Friends in Gold, it show a blank page: http://usaco.org/current/viewsource.php?sid=4318354 Is this intended? (my other submissions are all shown correctly)
If anyone who solved Bronze 3 could give it a difficulty in CF rating how would you gauge it? I usually AC bronze but that one bamboozled me.