Hi all,
The first contest of the 2023-2024 USACO season ran from December 15th to December 18th. 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).
There are some new rules regarding the platinum division of USACO, please refer to the website regarding the updates, especially if you are trying to be invited to the USACO training camp.
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?
The contest will open on December 15th.
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.
Can I use AI tools during the contest including but not limited to ChatGPT and Copilot?
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.
MIT Early Action results releasing during Plat :eyes:
good luck everyone
Rip my 20 line debug template... :/
These guys never forget dissing Rust
When will the contest start ?
it is eastern time i guess
time to attempt the contest for 30 minutes and play genshin impact for the rest, as usual.
Contest starting time?
12:00 pm ET
Sorry for this question as it is my first time, how do we actually enter the contest or does the contest window pop up only after it starts??
So, am I right that I can start solving the contest anytime within the weekend?
From here. Please ask questions after reading the rules.
I read the rules and then asked the question. The point is that before the contest clist.by showed that the duration of the contest is 4 hours, that is why I asked it.
This is what on CLIST:
Duration: 04:00
Time left: 4 days
It seems that it's your first time to participate in USACO. Wish you good luck!
I have said that it was written BEFORE contest, that is why I asked BEFORE the contest in order to know if I should start immedeately.
When start contest?
is it started?
no, why???
It is started
http://usaco.org/index.php?page=viewcontest
How i participate it. Is i need to register before it is started?
Yeah, you need to make an account first.
Ohhh get it Thanks
xiaowuc1 what time does the contest end on 12/18? 11:59 EST?
From https://usaco.org/index.php?page=viewcontest
thanks
Anyone know how to solve Plat p2 ?
Notice only the edges in the minimum spanning tree matter. Now do Kruskal and in the DSU maintain the answer for every node in a component. You can update the answers with merge small to large lazily. The small component could be updated naively and to update the large, I stored two lazy values for every component: $$$mul$$$ and $$$add$$$, so that all answers $$$A$$$ in the component are actually $$$mul \cdot A + add$$$.
when you need to get answer of some vertice in some component, how do you get it because i think if we can not just naively push down lazy ?
See my code for reference. The answer for a node will be $$$mul \cdot A+ add$$$. You "push down" naively for the smaller component (i.e. make $$$mul=1$$$ and $$$add=0$$$) and update the larger component's $$$mul$$$ and $$$add$$$ values.
thanks, nice solution.
Hopefully 791 (full on P1 and P3 and half of P2) is enough to promote to Platinum. Anyone knows the full solution to Gold P2?
You can maintain hash values for each vertex's path and whenever you get 2 different paths with same (maximal) length you can binary search on the hash values (based on length of path) to find the first point at where they differ and check which edge has lesser value and choose accordingly.
First calculate longest path starting at each vertex using dfs. Group vertices by their longest path length. Process vertices with equal path lengths together starting from vertices with 0 path length to longest. Rank all vertices with same path using pair comparison on {best edge to a neighbour,rank of neighbour}. Only consider neighbours whose longest path is 1 less than mine(optimal neighbour).
How to solve plat1
So notice that for subtask 2 where all cows are infected you can do a greedy where you iterate cows from order of greatest depth to smallest depth. If not all cows are infected you need to find cows which could start the process infected, which means that all cows within d distance have to be sick. Then to do the greedy for some node if its not covered by any cow yet you take the cow with highest depth that can start infected within d distance. To check if a cow is covered by someone else you just check if a cow you picked is within d distance. You can do these operations all with centroid decomposition.
Depth with respect to what?
The depth of the tree.Because this order is a perfect sequence of a chordal graph.
Can you explain what you mean? It’s difficult for me to understand how chordal graphs are related to this problem
A new graph is a chordal graph if we create a new graph that is concatenated with edges for two points u,v in the tree that satisfy dis(u,v)<=k. And the perfect elimination sequence of this graph is the sequence after each point is sorted by depth from largest to smallest.
Sir what does this even mean? We have a tree, what does chordal graph even mean?? And still, depth with respect to what :))??
A greedy worked very well when all the restriction were loose and so long as all nodes were covered it was ok :)); but now you have tight restrictions meaning some nodes are at distance exactly d. These dont even give some tight/implementable restriction, i.e. you only need (maybe exactly) one node with distance exactly d.
I'm not sure if this is related to chordal graph, but I think the greedy strategy is correct. I'll post a proof below.
Let $$$u$$$ is a lowest vertex needs to be infected. Let $$$v$$$ be the highest vertex can be chosen and $$$dis(u, v) \leq d$$$. The strategy claims that $$$v$$$ is one of the chosen vertex.
Assume $$$v$$$ is not chosen, then another vertex $$$w$$$ with $$$dis(u, w) \leq d$$$ is chosen, and $$$dep(w) \leq dep(v)$$$. It can be proved that $$$v$$$ can infect all uninfected cows infected by $$$w$$$.
Let $$$a$$$ be the LCA of $$$u$$$ and $$$v$$$.
So it is not worse to changing the chosen vertex $$$w$$$ to $$$v$$$.
I didn't come up with the greedy idea in the contest. I was inspired by the discussion here. I had a DP idea in contest with optimization to $$$O(N)$$$ but I didn't managed to implement it in contest.
How does any of this relate to the restrictions imposed by uninfected nodes :))? Like, of course this works for "all nodes are infected", this was never the issue.
The only vertice can be chosen are those whose distance to nearest uninfected vertex is $$$> d$$$. When we choose vertices we only consider those vertice.
And wby would this be optimal? What is to stop the greedy procastinating to consider a node as infected, but not to procastinate for long enough so it gets to consider a node that is "forbidden" by this principle? And even assuming we know the answer to this question, how can the greedy, knowing this, make an optimal local decision in a node when there are multiple other (non-local) similar scenarios (i.e. brother-ish nodes) in which choosing the alien node might eliminate the apparent need for choosing said node? (like, such issues break the necessarily local nature of greedy algorithms, and just this sort of band-aids dont seem to make for very compelling arguments, worse yet, I'd call them defective, else I am missing something :))
To the first question, I think it should be some data structure work to find the highest choose-able vertex within distance $$$d$$$.
To the second question, The proof just shows that if several vertices with same depth meet the condition, they are both optimal since they infects an identical subset of vertices need to be infected, so any one can be chosen as an optimal local choice.
Why is the last part true? If I have to choose between two (brothered) vertices, how do I know which one is better? Like, it seems as though if one has a more shallow afferent subtree, while the other has smth like height exactly d, it is more optimal to choose the latter, and it is still unclear to me what criteria can set these two apart :))-- like, it seems as though it cant be just height, because this characteristic can obviously not tell the minimum number of needed nodes to infect on its own
As we are assuming that the vertex $$$u$$$ we are going to infect is the lowest one, it does not matter which subtree is shallower or deeper. If a chosen vertex infects $$$u$$$, it infects all vertice need to be infected in a whole subtree, and no vertice lower than $$$u$$$ need to be considered.
My friend let me write on his account as a joke, but the algorithm is correct.
If all cows start infected, it means any cow can be a source node that starts sick. So then the idea of choosing nodes is this: We root the tree arbitrarily, and we will loop through all nodes from greatest depth to smallest depth and select nodes to start infected in this process.
Let the current node be $$$i$$$. If $$$i$$$ is within $$$d$$$ distance from a some node we have infected, we need not consider it. So now assume $$$i$$$ is not infected. Note that it is currently an uninfected node with largest possible depth, as all previous nodes are infected and all later nodes have shorter depth. That means that, if we have two nodes $$$x$$$ and $$$y$$$ that are both valid we can choose to infect the node with smaller depth. fdironia provided a proof above.
So now hopefully it makes sense how this greedy works if all nodes are infected. We return to the original problem. The issue now is that some nodes can't start infected. This is when there exists some node within $$$d$$$ distance that is not sick at the end of all days. Any node that satisfies the condition such that all nodes within $$$d$$$ distance are sick at the end of the process can start the disease. So we have turned this into the original problem; we only consider nodes that have to be sick, and out of the available nodes to make him sick we pick the one with smallest depth.
Please direct the downvotes to me rather than my friend, I apologize ;w;. We were next to each other after school and we both thought it was funny.
Participated for the first time in USACO contest. I solved P1, P2 completely and P3 for 2 subtasks. Is that enough for promotion?
If you did 2/14 subtask of P3 (I read subtask1 never count), you scored around 692 pts and promotion is about 700-750
I solved 5 test cases including the samples.
Btw, what is the scoring distribution of the problems?
Each problem is weighted equally (333 each) and each non-sample test case is worth the same for each question.
So if I solved the first 2 problems completely, tha's 666 points. And 3/11 from the third are another 90 points. So I have 756 in total, right?
How to solve pt p3?
$$$dp_i$$$ indicates the minimum answer of the first $$$i$$$ trains if the $$$i-th$$$ train is forced to satisfy $$$a_i=t_i$$$. Then consider $$$dp_i\rightarrow dp_j$$$ and find that the middle process must be left to go, right to go immediately and left to go immediately, so the start time of $$$(i,j]$$$ these trains can be determined, so the time complexity is $$$O(n^2)$$$.
How can you know the number of trains that have left from the other side?
Is it rated?
Fun fact: it seems that the tests of plat P3 is quite week.
Here is a dp solution: dp(x,y,0/1) represents: considering the first $$$x$$$ As and the first $$$y$$$ Bs, the last one is A or B. This is wrong because you can not find out the current time. But I keep the pair (cost,time), that is, keep the solution with the minimum cost, if there are more than one, keep one with the minimum time. It only failed on two test cases of the largest subtask (xd.
In bronze, I solved full A, 1-6 of B, full C. Is my point 333 + 138 + 333 = 804? Will I pass bronze to silver?
most likely.
Yeah, I made it.
What's the difficulty of the problems in silver/gold? What would their rating be in CF? Are the difficulties of the problems the same every month or do they get harder every month?
I think there is something wrong with system.
After solving the gold problems, I clicked the "Promote Me" button.
At the final minutes, I just shortened my code (for fun) and sent it again, but it seems I had a bug, but there wasn't any time left to fix that.
And now it seems that the judging system somehow considered my last submission even though I did this after pressing the "Promote Me" button?!
I know the rules (last submission rule) but when you press "Promote Me" it means you are done!?