Hi all,

The second contest of the 2020-2021 USACO season will be running from January 22nd to January 25th 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.

Thefirstcontest of the 2020-2021 USACOThere is a typo first -> second.

Nope 1st contest already happened at "Dec 18-21: First Contest".

Yes..that is what DividedByZero is saying...

Hoping to make Gold. Do you think someone with my rating graph has a decent chance at making Gold?

f, i didn't expect that

WHAT?????

I'm interested in why you think so...I mean I kinda base my progress on my rating.

It's just something people say when they feel bad about their rating to make themselves feel better (at least me :clown:). It's not perfect (especially for lower placement OI progress where it corresponds least), but it still

~~is~~should be the unarguably the best measure of progress relative to others right now, assuming you have decent amount of data points.Most gold are high specialist or low expert I think, so you probably have somewhat decent chance.

f, i didn't expect that

I only said because of the existence of highs is not so proportional to your ability at all.This is why you need decent amount of data points, because highs and lows should average out to a close representation of your skill. But yeah, one large drop in rating, or one large rise, doesn't mean much on it's own.

I'm a "her" FYI.

I didn't know, sorry.

I hope too. Good luck for everyone and especially for you)

Yes, it's possible. I think, you can get Gold. I believe in you!

yay, Gold! :)

Congrats!

How do I register and participate? I opened the Contests page but there are only previous contests there.

here

Thank you. Apparently the link to the contest page is located on the top of the Overview page.

Is there a way to see the standings? I am completely new to the USACO platform. Thank you.

No, you can't see live standings. That's because it's an IOI-like contest.

After the contest ends, you can see your standing.

Why are people downvoting me? Did I ask something wrong? I already said that I am new to that platform :(

From post:

Sorry for that. Will keep in mind from next time.

Solve all the silver using 3hours and 56 minutes.....

Think the problem for a lot of time, good problem!

Please don't discuss anything about the contest right now; I mean discuss literally NOTHING.

When can we discuss?

It's best to wait until the USACO website states that the contest is over (though I don't know when that will be).

I believe it's okay to discuss now. Can anyone confirm?

Yes.

Here are my solutions to all of the gold problems:

Problem 1: Uddered But Not HerdThe goal is to partition the array into subarrays s.t. there is a minimum # of subarrays, and the partition is valid. Note that there are only 20 distinct characters in the string. Consider a graph where the nodes are those distinct characters. For every pair of adjacent characters, add an edge from the left one to the right one. A partition can be represented by removing some of these edges. It can be shown that this graph is only valid iff there are no cycles (because if there is a cycle there is no topsort and therefore no alphabet). Thus this problem can be reduced to the problem “minimum feedback arc set”, a well known problem that has a $$$n^2 2^n$$$ bitmask dp solution on the topsort.

Problem 2: TelephoneThe obvious dijkstra approach is too slow, because there can be $$$n^2$$$ edges. The way you can fix this is by changing your state. Let $$$dist[i][j]$$$ be the minimum total distance cows need to walk s.t. a cow with color $$$j$$$ is at position $$$i$$$. Your answer is $$$dist[n][color[n]]$$$. The transitions are:

You can solve this shortest path problem with 0-1 BFS. Another implementation detail is that the last edge taken must be of type 3. You can encode another dimension in your state, which represents a boolean value that is true if the last edge was of type 3 and false otherwise. This solution runs in $$$O(n*k)$$$ time.

Problem 3: Dance MoovesLet $$$locs[i]$$$ represent the set of unique positions that cow $$$i$$$ would go to in the first $$$k$$$ moves. The sum of the sizes of $$$locs[i]$$$ is $$$\leq 2*k$$$, so you can store and compute it naively. Consider the inverse of the final permutation formed. You can solve for each cycle in that permutation independently. Let's call "hitting" a node $$$i$$$ visiting everything $$$locs[i]$$$. Each node in the cycle hits some (constant sized) range of other elements in the cycle. It also goes to some prefix of $$$locs[i]$$$ for some node $$$i$$$. You can do a sliding window on $$$locs$$$ to calculate the answer for every node in the cycle in amortized linear time. The final complexity is $$$O(n+k)$$$.

Side Note: Was it intentional to make it hard to notice that there are $$$\leq 20$$$ distinct characters in the string in problem 1?

Also: Does anyone know the solution for Plat Problem 3? I implemented Offline Dynamic Connectivity, but it had a complexity of $$$q*n*log(q)*log^2(n)$$$ with a bad constant, so it was too slow.

I agree, spent about 30 minutes thinking that there are <=26 characters instead and tried to find a polynomial solution because I thought <= 20 was a subtask. I wish they had stated that clearly in the problem statement, not just in the subtask list...

Same here! Except in my case I spent a lot more than 30 minutes :(. The fact that they mentioned 26 in the statement made it even more confusing.

Hii!!!!

Was it intentional to make it hard to notice that there are ≤20 distinct characters in the string in problem 1?

Are you sure ??????????... Because i solved it for 2 hours with this very obvious $$$n^{2}*2^{n}$$$ solution which is a kind of repeat to this problem https://codeforces.com/problemset/problem/1238/E

Wait a minute!! I just went through the question and read it 10 times then i noticed the scoring portion. Are you talking about

Mildred ?? If yes, then its insane.For Problem 2, my friends qwerty190 osmium Freaksus got AC by doing Dijkstra, even there were n^2 edges. I am so confused why those solutions got passed.

Would they be comfortable sharing their code? Sometimes brute force approaches with things like pragmas and heuristics pass, which is unfortunate.

As far as I know, they don't use this kinda stuffs. I am contacting them, as soon as they reach me, they would reply to you in this comment!

Edit: They didn't save their codes, so they can't get access to them right now. After this session's USACO problem page opens, they would get the codes. Moreover sorry for the misinformation, one of my friends got all ac by doing Dijkstra, but the other two got 12 test-cases out of 13.

Yeah, I also know some friends that passed with just a brute force (without any pragmas or the sort.) I hope USACO adds some tests and rejudges, because a naive N^2 dijkstra should not get 12 or 13 cases.

You can solve plat problem 3 in $$$O(NM + Q(N+M))$$$; essentially, you approximate the answer by counting how many CC's have their upper left corner inside the query rectangle using prefix sums, and then you walk around the perimeter of the query rectangle to fix your approximation. There are various strategies to handle the details of the counting/overcounting; the cleanest strategy I know is to consider the (planar) graph of lattice points and use the Euler characteristic formula V-E+F = # cc's + 1.

How do you count the number of faces efficiently in this graph?

Note that each face/cycle of the original graph is either fully contained within the query rectangle, or it merges with the "outside" face (that extends to infinity) and doesn't contribute to the count. Thus, we just need to count the number of original faces fully contained within the query rectangle. From now on, "faces" will refer to faces of the original, whole graph.

First, number the faces, and for each lattice point (corner between 4 tiles), precompute which face it belongs to using flood-fill. Now, for each face, pick one lattice point in it as the "representative", and compute rectangular prefix sums for the number of representatives in a region. This is our approximation/overcount for the number of faces fully contained; it may include some extra faces whose representative point is inside the query, but are not fully contained. Fortunately, these faces must intersect the boundary of the query rectangle. Thus, walk along perimeter of the query region, and subtract off the number of faces which intersect the perimeter at least once and whose representative is inside the query region; we can count these in linear time with a boolean array or a hashset. Then, we will be left with exactly those faces which are fully included, so V-E+F will work.

As ecnerwala said: the graph is planar, so we want to know the value of $$$V - E + C$$$, where $$$V$$$ stands for the number of vertices, $$$E$$$ for the number of edges and $$$C$$$ for the number of cycles. $$$V$$$ and $$$E$$$ can easy be calculated in constant time per query with prefix sums. To calculate general cycles we can just run DSU on the dual graph. Then for each connected component in dual graph we calculate its bounding box.

So, we are given a list of rectangles (at most $$$n \cdot m$$$) and for each query we have to count how many of them are inside query's rectangle. It's easy to see that at this point complexity $$$O(q \cdot n \cdot m)$$$ is enough, as it's a very simple check.

Making strong tests is hard :(

I think my original proposal had $$$Q \leq 5000$$$ and $$$N, M \leq 2000$$$ without the increased TL — do you think the $$$O(QNM)$$$ solution still would've passed with those constraints?

Don't forget that you can count number of small bounding boxes (e.g. 1x1) insde of query in linear time, so this solution would have very small constant.

I think if you use prefix sums for all bounding boxes with max side length at most $$$n^{1/3}$$$, you can get $$$O(1000^{8/3})$$$ runtime.

In case of generalization, we can try squeezing using different constants(for higher constraints) because I assume creating test with evenly distributed boxes is probably impossible.

Don't worry, it's not about the tests, just the limitations. As Andrew wrote it can be squeezed even more. I think that for all rectangles (assume there are $$$c$$$ of them and assume $$$n=m$$$) with fixed height and width limited by some $$$x$$$ we can solve the problem in $$$O(n^2 + c \cdot x + q)$$$, so we can solve rectangles with height and width small smaller than $$$\sqrt{n}$$$ in $$$O((n+q) \cdot n \cdot \sqrt{n})$$$. Then, there are at most $$$n \cdot \sqrt{n}$$$ rectangles, so the whole complexity would be like $$$O((n+q)^{5/3})$$$.

Btw. there are always at most $$$20-30$$$ tests. Are they tests or are they really groups of tests?

USACO doesn't use grouped tests, so they're just single tests. I think it's because their servers aren't powerful enough to handle so many tests for so many people. (The camp contests have grouped tests though)

Uhoh... I wrote some weird bitset shit that gives $$$O(\frac{NMQ}{B} + Q 2^B)$$$ time complexity. I thought I got the intended solution and thought the problem was weird, but the model solution is actually nice.

If you had $$$Q \le 5000$$$ then I might try to use the brain :) It doesn't look like tight limit at all.

I think tests are actually a bit weak. I managed to AC dynamic connectivity (written in part by 12tqian) solution with $$$N^2 log^2{N} + N^3/64$$$ in about 2.7/3 seconds. It's worth noting because it's in essence the "trivial" dynamic connectivity solution with relatively few constant optimizations.

Here's my implementation: link.

I have no idea why changing the types of

`g, h, v`

from`int`

to`short`

makes it AC, but apparently it does.gold P2 can be solved with djikstra,you can reduce the number of edges to $$$O(nk)$$$ with the following observation :

given node $$$v$$$ and the set of groups that is compatible with $$$v$$$,you only need to connect $$$v$$$ to two nodes in each such groups namely the node closest to $$$v$$$ from the right and closest to $$$v$$$ from the left

the proof is as follows:

assume you have a optimal path $$$A$$$ $$$\to$$$ $$$B$$$ $$$\to$$$ $$$C$$$ and that $$$B$$$ is neither the closest node to the right or left of $$$A$$$ (within the same group as $$$B$$$),then you can modify $$$B$$$ accordingly to be one of the two nodes described above with some casework

the final step is to connect edges to $$$n$$$ whenever possible,each node atmost have $$$2k+1$$$ edges so there are atmost $$$2nk + n-1$$$ edges

Could you share the "minimum feedback arc set" dp solution on the topsort pls?

See 46:06 of this Algorithm's Live! video by tehqin. The problem Order of the Hats mentioned in the video is the minimum feedback arc set problem, and this gold problem can be reduced to it as I mentioned in my comment above. Also my solution ended up being pretty much the same as the editorial, so reading that will definitely help.

Could you share video link or code pls?

Oh I'm sorry, I forgot to link the video. Here

many thank!

There were problems initially with the output files of Gold P1. Spent 2 hours before rage quitting wondering why my '3' is not their '3'.

Really appreciate though that the issue was recognised and quickly resolved after I sent an email.

^ why you never take USACO at the start of the contest window

How to solve Silver P1 ? Does it involve bitsets ?

It was the classic swapping graph-theory problem! See my code below if you're curious.

Consider the cycles in the final permutation produced after doing the $$$k$$$ moves. Each cycle is independent, and it can be shown that every node in the cycle has the same answer. The answer for some node in the cycle is the size of the union of the sets of all distinct locations each node in the cycle visited in the first $$$k$$$ moves (this is because each node in the cycle visits the locations of every node in the cycle). This value can be calculated in amortized linear time, as the sum of sizes of the sets is $$$\leq 2k$$$. The final complexity is $$$O(n+k)$$$.

Very Nice Solution. Thanks for the explanation!

My USACO Silver solutions (finished with 15 minutes to spare, only)

Problem 1Problem 2Problem 3Full Disclaimer: My solutions are somewhat messily written due to the time pressure.

I will also share my solutions for the gold division. I’ve managed to get full credit on Problem 1, got 12/13 tests on Problem 2 (will talk about that when describing its solution), and 5/20 on Problem 3.

Problem 1After finally understanding the statement, we get that we can have at most 20 letters. This usually points to a solution using bitmasks, but how? First things first, let’s talk about the first subtask (which meant we have at most 8 letters if I remember correctly). We assign a “score” to each letter, from 1 to 8. We go through each permutation. Say we have string “abdcefghab” and the values a = 1, b = 2, and so on. The string will become “1234567812”. Now, how do we count the number of times we have to say the alphabet? Well, when we get from a bigger to a smaller value, we simply add 1 to “ans”. The answer will be ans + 1. Now, we can’t simply go through the string for each permutation, but we can make the observation that we only care about consecutive pairs. We count the frequency of each pair. For example, in “abc” we count (a, b) and (b, c) once. Now, when we have a permutation, we simply add the frequency of the pairs that are of the form (nr1, nr2), where nr1 >= nr2. But, how do we solve the full problem? We will solve it using bitmask dp. Our mask will consist of 0’s (indicating we don’t consider that letter and put a “_” instead) and 1’s (we consider that letter). For example, “Mildred” and our mask considers letters “d” and “i”, we have

i_d_d. Now, iterate through each letter in the mask and suppose it has the greatest “score”. Let’s denote it as “ch”. This means that if we encounter pairs of (ch, some other letter in the mask), we have to “split” the sequence and count the number of times we do this. The recurrence is dp[mask] = the number of splits + dp[mask]-(1<<(the bit corresponding to ch)); Note that when I was referring to pairs, I was considering it in the same way as in the first subtask solution, consecutive letters. The overall time complexity is O(2^n * nr_distinct_letters^2).Problem 2On this problem, I’ve got 12/13 tests. I had an observation, which made sense in my mind, but I don’t know if it’s completely true and I just missed a case, or if it’s false and got lucky with the tests. The observation was that you only care about the first and the last cows (I can’t remember what the problem was about) of each type. Why? Suppose you want to go from type “a” to type “c”, using type “b”. Say we have something like a__cb__b__ (and you can go from a to b and from b to c). In this case, you choose the first b. In fact, you always choose the first b (unless b is at position n, which ends the process). My explanation was that if the next character you go to is before the first b, then you choose the first b, to minimize the steps you go back (you are obligated to take at least n — 1 steps, the backward steps are the problem), and if c is after the first b, you again go to the first b, to go to c for “free” (I only consider the cost of backward steps). So we only care about 2 cows of each type, create a graph, and do Dijkstra. (I picked 2 cows, because, as I’ve said earlier, you may want to end the process by going to the nth position). I have no idea if this is correct, feel free to counter my argument.

I won’t describe Problem 3, since I’ve only managed to solve the first Subtask. Overall, a pretty interesting and hard Gold Round. Def easier than December though (In December I’ve scored around 400 and now around 720). What do you think will be the score needed to promote?

EDIT: Regarding problem 2, I only care about the first and the last cow of each type, not about the first 2.

Can you share your code for problem 2? I want to try to break it, but I don't fully understand the solution. I can also stress test it (I have a generator and a correct solution already), and I'll tell you if I can find a counter test.

As for the promotion cutoff, I would guess either a 700 or a 750. I'm probably biased here because I solved all of the problems (and I'm good at graph problems), but this contest didn't feel absurdly hard (unlike the last one). For reference, last contest I got a 200 on gold, but in this one I ICP'd and got a 450 on platinum. I think a 700 or a 750 cutoff would be reasonable, but we'll have to wait and see.

Code on Pastebin

It's terrible, don't judge it, please.

I found a counter test, your lemma is wrong.

Counter Test9 5

1 2 4 2 3 2 4 2 5

00010

00100

00001

01000

00000

The only possible path will have these transfers (based on color): $$$1 \rightarrow 4 \rightarrow 2 \rightarrow 3 \rightarrow 5$$$. In this case, checking only the first and last occurrences of each character is not sufficient.

Thank you! I guess I got lucky with the tests. I will now try to solve it properly.

i have 749 points (full + 11/13 + 8/20) and I'm praying for 700... Missing plat by 1 point will be super sad...

What does everyone expected the gold cutoff to be? I'm thinking 750-800.

I'm pretty curious about the silver-->gold cutoff. I made it with a 1000, but since last contest I got only 350, I was thinking maybe I got lucky and it was just an easy contest. Did you guys think it was an abnormally easy silver contest?

A friend and I both found this silver contest much harder than the December contest, but maybe that's just because our skill set is different than yours. I'm interested in checking out the official solutions and cutoff scores after they come out though.

Admittedly, I still don't get the intuition behind the second December silver problem. I get the solution, but I still don't get how to come up with the solution, I guess.

I definitely thought it was easier — Q3 in the December contest felt way harder than Jan Q3

Interestingly enough, Q3 took me the least amount of time. My times:

Q1--2 hours (bugs :)

Q2--1 hour

Q3--45 minutes

Is it intended to make P1 < P2 < P3 or is it rather random?

From the USACO Guide:

I actually found P1 the hardest, any hints on its solution?

Try to think about the shortest odd and even paths in every graph.

Waiting for hint/editorial for P1 platinum also.

Solution for Plat P1First, let's try to figure out how to actually find the shortest path to some tuple efficiently. Consider each separate node in the tuple (call it $$$c$$$). Let $$$dist[c][0]$$$ be the min distance to get to $$$c$$$ within it's own graph s.t. it's at an even distance away from node 1, and $$$dist[c][1]$$$ be the min distance to get to $$$c$$$ s.t. it's at an odd distance away from node 1. Both of these quantities can be calculated easy using a bfs. The answer for some tuple is $$$min(max(dist[c][0]), max(dist[c][1]))$$$. This is because if everything has the same parity, every node that get's there before the node with the max distance can just move back and forth along an edge. Fix the node and the parity that contributes the answer. You can sweep from least to greatest for the corresponding parity and maintain the number of tuples efficiently using a segment tree. The final complexity is $$$O(n*log(n))$$$ where $$$n$$$ is the sum of the individual graph sizes.

There is no need for a segment tree. Using the fact that

helps a lot. Infinity contributes 0 to the answer.

How to solve Platinum P2 and P3?

Solution to Plat P2Consider the process in reverse. Now it can be shown that for a certain column, you will move up to a certain row before moving to the left. For a column $$$i$$$ call that row $$$opt[i]$$$. $$$opt[1]$$$ is obviously $$$1$$$. For every other $$$i$$$, ternary search on $$$opt[i]$$$. Let's focus on calculating the min cost for the query $$$(n, i)$$$ and a fixed $$$opt[i]$$$, assuming you calculated $$$opt[j]$$$ for all $$$j < i$$$. You are going to go up until you hit $$$opt[i]$$$ then move to the left, and then move down until $$$opt[i-1]$$$. From there, you can use a pre-calculated answer to find out the answer. Now, you can ternary search to find the $$$opt$$$ values. About the pre-calculated values I mentioned earlier, call $$$pre[i]$$$ the answer for the prefix of $$$i$$$ columns, given that the query position is $$$opt[i]$$$. You can calculate this using the same calculation as before (and $$$pre[1] = 0$$$). Now you can use this same calculation to answer the queries as well.

One more implementation detail: what happens when the column in the query is $$$ < opt[i]$$$? You would keep moving left until you hit column with a greater $$$opt$$$. To calculate what this would be efficiently, you can use something similar to binary lifting.

Here is my code.

For P3, ecnerwala described a solution in a comment above.

What do you mean by not being sure? Do you mean that the tests might be not strong enough to detect an incorrect solution or that you haven't submitted during the contest?

I finished this right after the contest, so I couldn't submit. I stress-tested it after against the obvious $$$O(n*m)$$$ dp.

Edit: Submitted it after the contest and it passed.

I wrote about P3 above. P2 is a history exam about problem "Icy Roads" from Gennady Korotkevich contest 1 from 2013.

Where do you find these contests?

P2 intuitive solution w/o knowing some obscure contest$$$N<=1e9$$$ immediately screams solving offline over columns and keeping the answer for each row in graph form. Turns out, this is possible. The answer for the first row is obviously $$$y=c_1x$$$. Transitioning to the second row, the graph becomes $$$y=x^2+c_1x$$$. Then, transitioning down the row is exactly equivalent to drawing a line of slope $$$c_j$$$ at some point of the current graph. If you can visualize this for the second column, it's obvious that the optimal place to transition is

ONLYat the tangent line. Generally, the solution becomes: maintain $$$ax^2+bx+c$$$ and the interval that it is optimal. When transitioning across a column, the do increment $$$a$$$ for all quadratics in the set. To transition down the row, note across the set of quadratics that we're maintaining convexity and differentiability holds everywhere even after transitioning. So simply take the derivative of the quadratic and find when the slope of the tangent line is equal to $$$c_j$$$. If it's less than the range of optimality of the current polynomial, pop it out. At the end, add a new polynomial $$$y=0x^2+c_j(x -x_{tangent}) + y_{tangent}$$$. Finally, calculating answer for a query can be done by binary search.A general summary of the technique is to consider the values of the "naive DP" as a function in one of the state variables, and try to identify/prove if it's convex; if so, try to maintain it or its derivative as piecewise linear or quadratic. (Depending on the problem, you may want to store inflection points or segments or something else.)

Oh, this strategy seems sort of similar to the slope trick I guess (which is only for linear functions).

sorry to comment something during the contest. (got so many downvotes...)

This is my first time to do usaco contest brozon & silver.

I spend nearly one hour to figure out the simple dp solution for the 3rd problem, and another one hour to transfrom the second question to a well known question.

For the second, get L[i], r[i] be the first smaller position from left and right of i-th number, then answer is about distinct elements in range. This is a well known problem called D-query in spoj.

For the third, consider by row, thus two rows will be the same or complete different. We can do it using dp[N][2]. Then swap the element by main diagonal, do the dp again.

DP was actually not needed for the 3rd problem!

HintFix the game board to be a checkerboard (ie alternating C and '). See what happens when we change a C to a ' and vice-versa.

When will the results post?

For Gold problem 2, if you're currently at cow A and are looking to travel to a cow of breed B, is it correct that you only have to check the cows in B closest to A in either direction and the rightmost cow of B? Because (I think) the only time it's optimal to go all the way right is if you can get to cow N. Otherwise, let's say that the next cow you want to travel to is cow C, the cow from breed B closest to A on the left L, and the cow from B closest to A on the right R. Since the answer can be represented as

`(N-1) + 2 * (backwards distance traveled)`

, the goal is to minimize the total backwards distance traveled. If C is left of L, then no matter what you'll have to travel at least`A-C`

distance to get there, so one of your best paths are guaranteed to be`A -> L -> C`

. If C is right of L and left of R, then at least one of the optimal paths are`A -> L -> C`

or`A -> R -> C`

, whichever of the two travels backwards less. Otherwise, if C is right of R, then your one of your best paths are guaranteed to be`A -> R -> C`

.Welp I implemented and submitted and it got AC so I'll assume for the time being that the idea is valid xd

Results are out!

`(int) m%k`

instead of`(int) (m%k)`

What a great way to miss an icp.