Hi all,
The first contest of the 2021-2022 USACO season will be running from December 17th to December 20th this weekend. Good luck to everyone! Please wait until the contest is over for everyone before discussing problems here.
Edit 1: The contest is live now! Please read the contest rules carefully, especially regarding how to ask clarifications or contact the contest organizers. Do not spoil anything (including but not limited to your scores or anything about the problems) about the contest until the end of the contest (four hours after the stated deadline of the contest).
Edit 2: Results have been released.
What are one's chances at plat with 1780 rating (peak 1930)? I've solved virtually all past gold problems since 2015.
I think they're quite high, if this year's contests are like last year's. You got this :D
I hope to plat as well xD
EDIT: omg I did it!!!
Thank you for your contests. Would you please also clarify the exact time of each contest?
It's not xiawuc's contest, as far as I know. It's run by Brian Dean.
The contests are open for several days, Dec 17-20, so you can pick the time window that suits you best. The time starts when you log into the contest, and you only have 1 attempt
Can a specialist with rating 1413 (peak 1553) reach gold in 2 contest?
I guess we will find out soon :p all the best.
ok I failed, ended silver with 433 pts. 666 was doable. Silver 1 : sad noises :
I made Gold when I was ~1400 and had peak 1512 iirc. I got a 400 in December and a 1000 in January.
I made gold then struggled in pupil for a year lol.
can one give the contest unofficially ?
Where can i register for the contest ?
You dont have to register for the contest — just login and click on start contest on the contest page when you are ready for your window.
Hope I reach Gold this contest — I am stuck on Silver for the last 2 years although I think my CF rating is high enough to clear Silver.
Hope I can reach Gold as well.
oh
what's the duration for a contest in USACO? Does it vary in leagues(bronze, silver, gold, platinum)?
The contest is 4 hours for each division. You can take this for any 4-hour window from Dec 17th-20th. Also if you promote in-contest, your timer resets (so for example if you ace Bronze, then you promote to Silver and have another 4 hours for that contest)
I could not find any info on this but could you get promoted twice, if you full score two times?
Yep, technically it's possible to promote to platinum in your first contest by acing everything.
Anyone ready to increase rank after practicing over summer?
No.
What is the exact start & end time? I can't find it anywhere.
I'm excited to get destroyed by plat problems!
If you ace a division, does your timer restarts? If yes, does it start automatically or I will have the right to start whenever I want before 20th dec?
Since the rules about the usage of the prewritten code are explicitly strict I want to clarify a couple of things. I'm not necessarily having anything against it, just want it to be more clear :)
I suppose the rule literally concerns everything in the code so, for example, you have to type every include manually.
Can you do all the includes and convenience stuff just once during one particular contest and reuse it between problems? Maybe one could even reuse something like a segment tree between 2 tasks, is this allowed? Or is it supposed to be from scratch in every single problem?
If yes to the previous question — can you start doing this 10 minutes before the contest?
In the future, you should email the contest organizer these sorts of questions, as the contest organizer does not monitor this forum.
The answer to question 3 is very clearly no, independent of the answer to question 2, as that would be considered pre-written code, even if you do it right before you start the contest. The rules very clearly state that using pre-written code is forbidden.
The answer to question 2 is probably (again, confirm with the contest organizer) yes. The intent of the rule is to emulate starting from scratch in a "clean" environment, so once you typed out the code, you should be able to copy/paste it freely within a problem or across problems.
If I promote from x to y
Can I participate the next day and whenever? for y
Yes you can if you promote in-contest and it's before the deadline, your timer also resets.
I did not do well on gold. I wonder can I submit the solution out of contest to check whether my fixed version is right or should I wait until after 20th Dec ?
You will have to wait until after the problems are available for practice. You can also check whether your solution is right with someone who may have solved that problem you resolved after the official conclusion of the contest. Also, note that the contest ends at around 7 AM on December 21st ET.
sry
sry
In the future, it'd be best to read the announcement and rules more carefully:
i got it, im sorry, i lost all my contribution already in literally a month i will be like 'i was so stupid back then'
Thank youmy frmied!!!!!! With this information, I now know the problems givennin the contest and i can easily AK after i solve each one outside contest!!!!
If we get AC on most of testcases of a problem will we get some points from that problem or not?
You can get partial score i.e getting 5/10 testcases in 1 problem will give around 333/2 points
How can we see score?
You have to calculate your score manually, I think.
Does samples count towards scores?
Yes, they’re basically free points.
except, by law, you aren't allowed to just read the examples and print the example directly, as your program isn't computing anything per se (thus, a program that is just reading the input and checking if it correspond with some example to print some output would not be accepted). Hope, though, this will be the case, because spoiler
Aren't you allowed to do so in case you have something else in your solution though? Meaning that if you are trying to solve a certain subtask which does not include every samples, you are allowed to print out sample answers. I think you are referring to the sixth note in the General Technical Details, which counters only solely printf solutions. (Furthermore, not allowing stuffs like that would be unreasonable, as USACO refuses to judge solutions which does not completely pass samples, and since some problems are essentially two independent problems, it would be impossible to solve one without at least solving a subtask for the other.)
In fact, I don't really understand this rule. Does it mean that programs that do not contain any computational procedures, but only print statements, are forbidden?
For example, suppose my program contains a corner case, am I violating this rule by directly outputting the answer to such case?
Or, if I just guessed a random formula for a problem to pass all the examples. Is this a violation of the rule?
nah corner cases r fine
Programs that consist of essentially nothing more than print statements may be disqualified. If feedback for certain test cases is provided during a contest, you are NOT to submit repeated programs consisting of essentially print statments in order to reverse-engineer the inputs. Programs must actually compute the requested answers, not just print results from a pre-computed lookup table.
.
Please reread this page carefully as it states all the contest rules.
Note that this includes sharing your score and giving insight about the problem.
now i know a reason to improve in jitterclicking
Can I participant in this contest?
Anyone can still participate in the contest. Make sure to register for an account, and start the contest when you're ready. Good luck!
when will the editorial be published?
The contest is still running. It should be available after the contest.
The contest is over now? How do you all perform?
Any idea for silver's problem 1? (The contest has already end acording to the usaco site)
Consider the farms between two cows of Farmer Nhoj, using two cows of farmer john you can get all the farms between any two cows Farmer Nhoj. So for each such segment find maximum value of tastiness you can get using only 1 cow Lets call it $$$P_i$$$. and tastiness if you use two cows be $$$Q_i$$$. For a moment use 2 cows on each segment. Now number of cows used might be greater than $$$N$$$. So greedily Decrease the value by finding the minimum delta (that is either convert 2 cows to 1 cow for some segment, or 1 cow to 0).
Thanks
For each segment, if using 1 cow you gain $$$P_i$$$ while using 2 cows you gain $$$Q_i-P_i$$$, We also can easily prove that $$$P_i\geq \frac{Q_i}{2}$$$. Hence if we use 2 cows, then the event of 1 cow would be considered already. Then we have a sorted list of values, for each cow we used.
Greedily select the intervals from starting. Start from the leftmost position and continue till you can select the patches. Also start as far as you can from the first patch you are selecting.
I didn't participate in silver so I can't submit but here's my idea.
Consider the $$$M$$$ cows, they divide the grass into $$$M+1$$$ intervals(if a grass is on one of these cows, just delete them).
It's obvious that the placement of the $$$N$$$ cows in different intervals are independent.
If we put two cows in one interval, we will put them in position $$$L+1$$$ and $$$R-1$$$ (the interval is $$$[L,R]$$$), so every grass in the interval will be choose (we just need one cow if the interval is the leftmost one or the rightmost).
If we put one cow in one interval, one consecutive segment of the grasses will be chosen and we will find the maximum one.
Define the total value of one interval $$$V2$$$, we consider the two ways of placing the one cow.
Put it in $$$L+1$$$
Put it in $$$R-1$$$
It shows that these two segments of grasses will cover all the grasses in the interval, so if we define $$$V1$$$ as the maximum value of placing one cow, we know that $$$2*V1\ge V2$$$, which means $$$V1\ge V2-V1$$$.
Now will put the $$$N$$$ cows one by one into the intervals.
Put one cow in the interval with $$$0$$$ cows has the value $$$V1$$$.
Put one cow in the interval with $$$1$$$ cow has the value $$$V2-V1$$$.
Just sort all the values ($$$V1$$$,$$$V2-V1$$$) and take the maximum $$$N$$$ ones and it will be valid.
(Because due to the observation $$$V1\ge V2-V1$$$, value $$$V1$$$ will always be taken before value $$$V2-V1$$$, so this method must be valid.)
Complexity: $$$O(nlogn)$$$
How to solve silver problem 3?
You can subtract the number of invalid pairs from $$$N^2$$$.
Notice that invalid pairs are of the form:
$$$a_1 + a_2 \gt k$$$
$$$b_1 + b_2 \lt k$$$
these are $$$2$$$ dsjoint sets.
If you go from 0 to 2M, you see the event $$$a_i+a_j$$$ your results increase by 1, while you see $$$b_i+b_j$$$ your results decrease by 1. Complexity $$$O(M^2)$$$.
Isn't O(N^2) too slow?
It is $$$O(M^2)$$$, sorry for the typo, since $$$a_i$$$ and $$$b_i$$$ are bounded by $$$M$$$.
Observe that M was quite less. So store the count of all possibilities of ai + aj and bi + bj. Now you can create a difference array, and iterate for all possible sums from 0 to 2*m, add cnt[] to the difference array for sum values of a (because range starts here) and -cnt[] to the difference array for sum values of b (because range ends here). Finally, calculate the prefix sum to get the answers for all k.
Overall time complexity : O(max(n,m2))
Okay... How to solve Gold 1 ?
For t=1 i solve it with dp[i-th element][choose or not], but t=2 I try to use dp[i-th element][previous one statue][current state]
status
0 = not choose
1 = choosed and will make pair with later one
2 = choosed and paired with previous one
i wrote the dp for a long time and finally find the bug at the last minute but can not submit.
Can anyone tell me is it correct?
For t=2, how will you check that any pair of not chosen elements are not within a range of k with this dp state? Also, there is an easy greedy approach for t=1 as well.
First observe that if you know which elements you have to keep single, then greedily you should select the remaining consecutive elements to pair up.
For t=1, there will be some disjoint ranges. You can separate ranges when abs(a[i+1]-a[i])>k. Now a particular range will always contain an odd number of elements, there will be several cases to remove at max one element, start pairing from the end and calculate the min value until you can pair from the end.
I used DP, but my state is whether the last 3 guys are used. It's getting wrong answer, and I cannot fix it.
Help?
I think it's not very healthy how almost every Platinum problem is being set by the same person for quite a while now.
Why?
Every author comes up with problems that share a distinct taste, which inevitably favors some contestants— just look at the number of counting problems. Personally, many of these statements feel quite artificial, and just not very interesting.
Well, at least the counting problem wasn't mine this time. :)
I agree with this, it's not very healthy for me. Unfortunately, there are not very many Platinum proposals in the database that are not by me ...
Totally agree, I think people who are not xiaowuc1 should stop setting Platinum problems
Can you be hired to set platinum problems? I think USACO would benefit from some data structures problems and some matroid intersection problems.
How to solve Pt 2 ?
First, split the two types of cows into two arrays sorted by their position, afterwards, $$$t=1$$$ is pretty simple, since you can use $$$dp[i][j]$$$ = minimum sum of weights of unpaired cows if we've paired up or left unpaired the first $$$i$$$ cows of the first type and the first $$$j$$$ cows of the second type. For this dp we won't have to worry about the maximal matching part since the needed cost is minimal so we won't ever leave unpaired two cows which could have been paired together.
For $$$t=2$$$ though, the maximal matching requirement becomes a problem, so the first ideea here would be something like $$$dp[i][j][k][0/1] =$$$ maximum sum of weights of unpaired cows if we've paired up or left unpaired the first $$$i$$$ cows of the first type and the first $$$j$$$ cows of the second type, and we aren't allowed to leave any cow unpaired in the next $$$k$$$ cows of the first or second type (given by the 0/1). This works in $$$n^3$$$.
In order to optimize this, let's define $$$dp[i][j][0] =$$$ maximum sum etc. ---||--- if we don't have any restriction going forward (we can leave a cow on either sides unpaired) , $$$dp[i][j][1] =$$$ ---||--- if we are only allowed to leave a cow unpaired on the left side , and $$$dp[i][j][2] =$$$ ---||--- if we are only allowed to leave a cow unpaired on the right side. Notice that in all of these states, we can always pair up the next cows.
Let's see how to calculate this, I'd suggest doing it forward. Say we're in a state of the form $$$(i,j,0)$$$ meaning we paired up all the first $$$i$$$ cows on the left, $$$j$$$ cows on the right, and we can now leave a cow unpaired on either side, then, we can either:
WLOG, let's assume we leave the $$$(i+1)$$$th cow on the left unpaired, this means we now have some $$$k$$$, for which we aren't allowed to leave any right cow unpaired among the next $$$k$$$ cows. So, if we assume we are going to pair up the next $$$k$$$ cows on the right with the next $$$k$$$ cows on the left (and if this is possible) this means, this dp could update $$$dp[i+1+k][j+k][0]$$$. But maybe, we're gonna leave some more cows unpaired on the left, since there isn't anything stopping us, so we should also update $$$dp[i+1][j][1]$$$. It turns out these two are sufficient, since whenever we're going to leave a cow unpaired on the left, that'll also update a dp of type $$$0$$$ in some $$$k'$$$ steps (I'm not sure how clear I explained this, but if you try to prove it, it will probably make sense). Finally, the transitions from other types of dp (such as $$$dp[i][j][1]$$$) are very similar, the only difference is the fact that we aren't allowed to leave a cow unpaired on some side.
Damn! this is a big block of text, sorry for that but idk how to format xD.
Okay so for Silver problem 3 there is a very funny solution that works in $$$\mathcal O(n+m\log m)$$$ time. For all pairs $$$(i, j)$$$ setup polynomials
Notice how the numbers $t_i$ we want from $$$0$$$ to $$$2M$$$ are essentially the coefficients of monomials $$$x^i$$$ in the sum $$$\sum_{i, j} P_{i, j}$$$. In order to solve this problem efficiently note that $$$(1-x)P_{i, j} = x^{a_i+a_j}-x^{b_i+b_j+1}$$$ and thus when we sum this over all pairs, we obtain a sum of
. Now we can use FFT and $$$\mathcal O(m)$$$ computations to solve the problem completely.
Does anybody knows how to re-open problems (or have screenshotted the problems)? (I would really like to ask the solutions from strong CPers who haven't participated in the contest, but I don't remember the samples.)
There is a subproblem I encountered which seems pretty standard but I couldn't come up with a good idea quickly.
Given a set of $$$n$$$ segments and online point queries you need to return all segments that contain this point and you haven't returned before.
I strongly feel like it should have a clean $$$n \log n$$$ solution that is not too hard to implement but for now I can only solve it in $$$n\sqrt n$$$ with some slightly unpleasant code complications. Does anybody know it or have any ideas?
You can maintain a segment tree over the values.If there is a segment (a,b) you basically need to add the index of the segment to the log(n) nodes which cover the (a,b) range.When there is query you can extract the values present in the log(n) nodes which cover the query index i.You have to erase all the values in these nodes also
Oh wow, it's very nice and clean indeed) Thank you! Can't believe I spent a very considerable amount of time on that.
Fun fact: this kind of segment tree is given as the definition of segment tree on Wikipedia.
:D
Here's another (maybe dumber lol) method: for each left endpoint $$$a$$$, sort all segments $$$(a, b)$$$ in increasing $$$b$$$ order. Then maintain a segment tree which stores the maximum $$$b$$$ for each $$$a$$$. Finding whether there currently exists a segment which contains $$$x$$$ can be done by seeing if the max of values in the range $$$[0, x]$$$ is at least $$$x$$$. To get the segment, the segment tree can also return the index of the max, and then it can be replaced with the next longest segment which begins at $$$a$$$.
Is there a way to solve Platinum problem 1 in less than $$$O(N+K\log^2 K)$$$ time?
The problem reduces to dijkstra on O(N+K) vertices and O(N+KlogN) edges, however, only O(K) edges are non-zero, so I suspect that you can solve it in O(N+KlogN) with some modified priority_queue.
I got that it reduces to Dijkstra on $$$O(K)$$$ vertices and $$$O(K\log K)$$$ non-zero edges. It's possible my graph differs from yours.
Fibonacci Heap? $$$O(NlogN+KlogN)$$$
My solution works in $$$O((N + K) \log (N + K))$$$ time.
I think my solution works in $$$O((n+K)\log(n+K))$$$ but I can't find it now. It tested so in random cases(but very slow).
I used a segment tree to optimize Dijsktra directly, instead of adding $$$K\log n$$$ edges.
Reverse the graph first.
For every ticket, insert $$$[l_i,r_i]$$$ into the segment tree.
For each node on the segment tree, only the cheapest ticket might become the next one to use, let its value be $$${mn}_p$$$, and it may start from any station in the segment, let $$$d_p$$$ denote the smallest $$${dis}_i$$$ among $$$l\sim r$$$(where $$$l$$$ and $$$r$$$ are endpoints of the segment).
Every time find $$$\min{{mn}_p+d_p}$$$, by carefully implenting it we can get a $$$O(n\log n)$$$ solution.
But it seems that the constant is rather huge(a lot of maintained on segment tree), I spent a lot of time optimizing it.
How to solve 2nd problem of silver division? I tried to do that with DSU but was unable to get the minimum distance between two pairs of DSUs.
To calculate the cost between two connected components you can use lower_bound to find the closest element in the second set for each one in the first.
Now you can simply brute force the connected component that will be connected to 1's and n's component as it allowed to add at most 2 edges.
To reach O(n*lg(n)) complexity we shall consider each element of the smaller set when calculating the cost.
Hint for Gold Prob2 please?
And also what is the solution for the second subtask of the same problem? (I really hope it's not something randomized, please!)
I don't remember the subtasks, and the problems aren't visible right now. Here are some hints, I hope they are helpful! :)
We can make a binary tree of the permutation. The queries made will correspond to the path from root to $$$x$$$ in this binary tree.
UPD: actually, the queries will correspond to the path from root to $$$x$$$ or $$$x + 1$$$, whichever is present at a greater depth.
Since querying the binary tree for for each query can be $$$N.Q$$$ in the worst case, instead we could lazily propagate some information while building our binary tree, which allows us to answer each query in $$$O(1)$$$ by accessing the vertex which corresponds to $$$x$$$.
Whenever we go from a parent vertex to its left child, it represents "HI", and when we go to its right child it represents "LO". While building the binary tree we can just keep track of the number of "HILO" encountered on the route from root to each vertex.
The second subtask had one constrain that the permutation is randomly generated.
Ah. I think that just means that there are no malicious testcases (no testcases which intentionally lead to $$$O(N.Q)$$$ time if you build and query the binary tree naively.
Now that you say it, I do remember that my first $$$O(N.Q)$$$ submission passed those randomly generated testcases.
Oh, I see now.
And also this idea of binary tree is fabulous, do you remember any other problem using similar ideas like this?
Can't say I do, sorry :(
Glad I could help :)
Hello, I'm sorry but I don't quite understand what a "binary tree" is referring to. Do you mean that we should make a binary heap over the array, or a binary search tree, or is it something else?
Draw the binary search tree and note that on the path from a node to the root, if you mark left edges as L and right edges as H, then the problem reduces to finding number of HLs on path to the root.
Here was my solution (around 30 lines of working code):
The answer differs by at most 1 between
i - 1andi(ibeing a value ofx,iin the range[1, n - 1]).The only point that changes as you step once from
i - 1toiis the guess ati(which moves from the right side ofx + 0.5to the left side).Therefore, if a HILO pattern starts at
i, then you will have to decrement the answer when moving fromx = i - 1tox = i.Similarly, if a HILO pattern ends at
i, you will have to increment the answer.However, if we find answers in order from
x = 0, 1, 2, ... nin order, there isn't any way to quickly find whether a HILO pattern starts or ends atx(at least I haven't found one yet).So, instead, find the change between
x = i - 1andx = iout of order. Then, at the end, put your calculated changes in order and output them.This solution eliminates the need for extra data structures like a BIT (which I think many others used), and is really short to implement.
Woah, you made it seem very simple.
I wonder, was the second problem an easy one for other people? Because, for me, it was a pain to think about it, while on the contrary, the first and the last were somehow trivial.
My code was 350 lines and included a lot of casework + segment tree with lazy propagation (it turns out seg tree isn't needed, but I understood that 50 hours after contest ended). It is different than the binary tree idea and much messier, but I'll share anyways.
The main idea is that if you look at the matrix formed with all the "H"s and "L"s, then all columns have some "?"s followed by some "H"s followed by some "L"s followed by some "L"s. We can identify the transition points, where things change, and since there are at most $$$3N$$$ updates, if we can point update and query number of "HL"s in $$$O(1)$$$ or $$$O(\log N)$$$ we're good. Also, we should stop querying after we know our number.
To point update just look at 2 characters to left and 2 to the right and figure out if things change and if so, by how much.
Well, the final idea and code are simple, but in reality this idea wasn't extremely easy for me to think of. In fact, it took the longest time out of all three problems (around 1 hour and 30 minutes) of thinking for me to come up with this solution XD
Keep the set of pairs (value, position). When you add a new pair $$$(v, p)$$$ check the existing element to the left $$$(v_l, p_l)$$$ and to the right $$$(v_r, p_r)$$$. If $$$p_r > p_l$$$ you need to add 1 to answer on $$$[p, p_r)$$$, which you can do in linear time. If you put proper initial values into the set there are no corner cases. It is about 15 lines of code.
Yep, if I'm not misunderstanding this is what I did (my code isn't the most concise).
Small correction: shouldn't it should be O(n log n) time not linear, since you use a set?
Yeah, you are right actually it is the same, my bad. I was slightly thrown off by your hints 2 and 3 and haven't read the code close enough until now, just skimmed through.
For linear I meant just the part with adding to the answer.
Ah, I see!
I would like to mention a thing about Silver S1. It was a wonderful problem but I submitted a very random code and it managed to pass 8 tests (obviously it's totally wrong) so doing S2, S3 and a random code on S1 could have allowed one to pass silver.
But maybe S1 is the easiest problem among the three problems.
I didn't find it to be that way for me it was as such S1 > S3 > S2 but it could be just me since I am inherently bad at problems involving greedy.
I just upsolved HILO from USACO Gold. I don't see my solution in the editorial. But I think it's a simple O(n) solution:
I simulated the process backwards. I maintain intervals of numbers $$$x+0.5$$$ that are not distinguishable. At the end, all numbers are distinguishable, so all $$$n+1$$$ intervals are of length 1. As you simulate backwards, the intervals above and under the current p[i] get merged, because those weren't distinguishable before.
I only maintain the boundaries between the intervals in an "array linked list" and for each interval, what the number p[i] was that merged it last. (last[a] = the last p[i] that merged the interval underneath a).
Merging is then just removing from the linked list and updating one number.
Which numbers could get a "HILO" in their string at this moment in time? If we have the interval $$$(a,b)$$$ that gets split into $$$(a,p[i])$$$ and $$$(p[i],b)$$$, it can be verified that all numbers $$$x+0.5 \in (last[a],i)$$$ get an extra "HILO". Since we need to support range adds and only query at the end, we can maintain the difference array and do prefix sums at the end.
Sorry, I don't think I understand what "not distinguishable" is referring to. Is it referring to when a number is skipped for consideration since another number before it already revealed enough info (Like skipping 4 because we already know 3 is too high?)
You can think of Elsie's procedure for guessing the number as follows: Elsie keeps the search range [l,r] (at the beginning [0.5, n+0.5]), which is the interval where the number could still be. Her search interval becomes smaller when she does a query, and she gets the answer HI or LO, just like binary search. If the number she's was going to guess is outside the search range, she doesn't ask it at all.
The intervals stored in the array linked list, are exactly the intervals which Elsie could have at this point in time as her search range. So in this way, you can simulate all possible ways for her search to go at once in O(n). If you look in the forwards direction in time, if she guesses a number, it splits the interval that this number lies in in two: The portion where she would answer HI, and the portion where she would answer LO. If you go backwards in time, this corresponds to merging of the intervals above and below the number guessed.
December Silver is very hard for me... I hope next contest silver will not be like this :(
Don't worry. It will be just harder.