Hi all,

The second contest of the 2022-2023 USACO season will be running from January 27th to January 30th. 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?

The contest will open on January 27th. A link to the contest will be posted here shortly after the contest opens.

#### 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?

Petition IOI to add Rust support first.

Hopefully I can get Gold this time around. Edit: Got it!

Same. Good luck!

I think you got it bro.

u got this!

Congrats on promoting!

Thank you so much! But if the cutoff is 900, I'm kinda screwed.

pain

plat pleaseeeeeeeeeeeee it has been way too long :sob:

would kind of sucky if 16 points away from cutoff again :((((

This time you will be 16 points away from scoring 1016

Uncle Ruckus from The Boondocks getting his ancestry result be like

So envy is going to get a 1032

omg same although it hasn't been long only 1 month

Wow how hard is it to get plat O_O. ur CM...

Ask timreizin

IMPOSSIBLE

It really depends on the person, but I got to IM before I got plat ...

Congrats bestie :))))

though i was in fact, 208 points off of 1016 :(

to clear the Bronze, what should be the rating on CF? please reply um noob

I cleared Bronze with 1000 or 1100 CF rating, but CF and USACO problems are different, I also know someone who passed with ~800 CF rating.

I cleared Bronze with 2350 or 2400 CF rating, but CF and USACO problems are different, I also know someone who passed with 1000-1100 CF rating.

I cleared Bronze with 1400 or 1500 CF rating, but CF and USACO problems are different, I also know someone who passed with 2350-2400 CF rating.

I cleared Bronze with 800 or 900 CF rating, but CF and USACO problems are different, I also know someone who passed with 1400-1500 CF rating.

I cleared Bronze with 500 or 600 CF rating, but CF and USACO problems are different,You need to understand.

My username could not clear bronze with 2097 CF rating and it will forever be stuck in bronze.

I cleared Bronze with 1200 or 1300 CF rating, but CF and USACO problems are different, I also know someone who passed with 0 CF rating.

I cleared Bronze with -100 or 0 CF rating, but CF and USACO problems are different, I also know someone who passed without a CF account.

First time plat contestant here. My goal last month was to score 1000 in USACO; have to adjust that number to 100 now xD

As a first time gold contestant, I want to pass :clown:

Gold is too hard for me and I will try the problems of silver too.

I can only speak for silver, but who has noticed that the people writing the contests are different than last year? Perhaps this explains the variability in the problems and why they are more ad-hoc.

From initial post :

****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.

I'm so sorry, I should have specified that this observation comes from the December contest, not the January one. I have not taken the January Contest yet.

I think USACO said at some point they wanted to make the problems more “mathy”.

Does anyone know how USACO proctor its contestants? (I have taken the test already and I have no intention to cheat)

As of 1 hour ago it is January 31 UTC-12 so it is okay to discuss the contest now I believe. Did anyone who solved silver 1 have the idea to count cycles in the directed graph of letters? I implemented this over and over for two hours but couldn't pass any tests. Trying to figure out if my idea was wrong or my implementation was wrong.

Try this test case:

The answer is 5, but many people's programs calculate the result as 4 or 6.

The process of transformation:

$$$\texttt{abcde}\rightarrow\texttt{ebcde}\rightarrow\texttt{eacde}\rightarrow\texttt{eaade}\rightarrow\texttt{eaace}\rightarrow\texttt{baacb}$$$

I see, an existing cycle doesn't always mean the answer will be incremented by one because the 'temp' letter we use can sometimes be optimally processed with some other batch of letters.

Thank you.

Hi, I still had an hour left on my clock when I was doing my gold contest but it ended. Is it normal (I started too late) or is it an error ? Anyway, it does not matter since I am not in any country's IOI preparation. But I was about to submit two bruteforces and grasp some more points haha.

edit : Also, I really enjoyed the problems (I was able to see the silver and gold ones!)

The contest for you ends at your 4 hour mark, or January 31 UTC-12, whichever comes sooner

Okay. My bad I forgot about this rule, I should have started an hour earlier then.

Ideas for the first problem in gold?

Were you able to solve the second one (light and switches one) ? I couldn't come up with any proper strategy to make both the strings equal in minimal moves :(

you are thinking in the wrong direction, there is (to my knowledge) no greedy strategy

Instead, try to divide the operation 1 and 2 and perform them separately (combined with operation 3)

by Doing this, you lose choice in one of them, as the type 2 + 3 operations is fixed, and you can bitmask dp precompute type 1+3 affecting lights bitmask, and then bruteforce over moves, noting its always <=2*n

Oh right we can precompute for each string. I was initially thinking in direction of Bitmask Dp but as T was 2e5 I thought we need to do some o(n^2) stuff for each test case.

my complexity was 2^n * n^2 + T*n

Dominater069 Orzz.

Here is O(N^2) solution:Let's analyze the sample.

$$$l=3$$$, $$$r=8$$$

After reversing:

We want to find

`"bbbdebbb"[3:8]`

which is`"ab"[3:8]`

.The length of

`a`

in the previous operation was 5, and the length of`b`

was 3, so we can get`"bbbde"[3:5]`

+`"bbb"[1:3]`

as answer.By recursively repeating the process above we can get the answer in $$$O(N^2)$$$. I don't know how to solve $$$N=10^5$$$ subtask, though.

I got full score by making a tree using pointers and some small optimisations

Hi,

Is there any silver participant who ACed P1.

Please share your ideas.

I Aced P2 and P3 but messed up p1.

It seems I was way behind the intended solution.

At a first glance it was obvious that problem will revolve around cycles but I messed up after that.

I didn't get P1 completely, only getting a 10/15. However, I'm pretty sure I found the bug in my implementation and that the approach is correct. Basically create a graph between character types where character c1 has a directed edge to c2 if c1 is in the input string and wants to reach c2 in the output string. Observe that each node (a distinct character type) must have an outdegree of at most 1. Otherwise, there's no way to do it. Once you know that the graph is valid, note that the answer is simply the #of edges (not including self-loops) assuming there are no cycles (not including self-loops). If there are cycles, that complicates the solution a little bit. It turns out you'll need to turn one node in the cycle into another character. If any node in the cycle has a child, it's optimal to increase the answer by the length of the cycle, since there's guaranteed to be a valid construction. Otherwise if there's another node that isn't part of any cycle, we can use that and increase the answer by the length of the cycle + 1. Otherwise, it's impossible to fix the cycle. May post some code later, but I need to grab some sleep.

my messy but ac codePosting a neat solution to Plat P1 here

Plat P1Let R_i denote the node with maximum index which is directly connected to i. Similarly define L_i.

So to find the value for (a,b)

we will see 2 arrays a,R_A,R_(R_A),R_(R_(R_a)) and so on till we cross b

let this sequence be x1=a,x2,x3,,,xk=b

similarily define y1=b,y2,y3,,,yk=a

(length of both sequences is same as it is the length of shortest path)

Now you can show that if you sort the xi,yi indices together you would get x1=y1=a<y2<=x2<y3<=x3...y(k-1)<=x_(k-1)<x_k=y_k=b

You can just count the special vertices in [yi,xi] ranges and add them together(ranges are disjoint). Now you can calculate the answer in log(n) using binary lifting and by maintaining sums of prefix sums.

This is a really clever application of binary lifting; do you know any similar problems?

Solution to plat p2 or p3?

P3For every subtree of the tree find 3 values:

$$$dp_0$$$ — just what the problem asks.

$$$dp_1$$$ — answer to the problem, but every vertex in the end has to be active.

$$$dp_2$$$ — answer to the problem if every vertex is active from the beggining.

It's pretty easy to calculate $$$dp_1$$$ and $$$dp_2$$$, the hardest part is calculating $$$dp_0$$$.

Here are two possible ways to calculate $$$dp_0$$$:

1) You choose two children of our vertex, let's name them $$$a$$$ and $$$b$$$, you choose $$$dp_1$$$ from $$$a$$$, then activate whole subtree, then clear every subtree except subtree of $$$b$$$, then choose $$$dp_2$$$ from $$$b$$$ and choose $$$dp_0$$$ from the other children.

2) You just choose $$$dp_0$$$ from every child, and activate the whole subtree when the subtree of the biggest child is activated.

CodeP2: For the first subtask, we can use bitmask DP to solve each query independently. Let dp[m][v] be the maximum mana we can achieve if we visit the fountains represented by the bitmask m, finishing at vertex v. To transition, we can take a path ending at v and append some unvisited vertex u to the end, thus going from dp[m][v] to dp[m|(1<<u)][u]. This changes the resulting mana quantity in two ways: it increases by s * M[u], the mana we consume from u, but forces us to visit all vertices in M earlier, decreasing our total mana by D[v][u] * T[m], where D[v][u] is the length of the shortest path from v to u and T[m] is the total mana accumulation rate summed over all fountains in m. Computing this DP for each query and choosing the maximal dp[m][v] for our end vertex v is sufficient to solve the first subtask.

To solve the next few subtasks, we will compute the DP only once. The idea is that the only part of our transitions which depend on s is adding s * M[u], which happens once for every u in our mask m. Thus, we can ignore this part of our transition when computing our DP. Then, for each query, we can choose m to maximize s * T[m] + dp[m][v]. We still must iterate over every mask for each query, but we no longer have to compute the DP for every query.

To get full points, we observe that the functions s * T[m] + dp[m][v] corresponding to each bitmask are linear in s. As such, each query reduces to finding the maximum value of a set of linear functions at a point, and this is a standard problem which can be solved using the convex hull trick.

I have a different and shorter to code solution to P3. It is optimal to choose a path going up starting at a leaf, where at each node in the path the whole subtree is colored, then choose a path going down to a leaf when uncoloring. The cost of this operation is $$$2 \cdot sub_u$$$, where $$$sub_u$$$ is the subtree size of $$$u$$$ and $$$u$$$ is the top node in the path.

We can make $$$dp_{u, k}$$$ as the minimum cost for a subtree $$$u$$$ where there are $$$k$$$ paths to be used. $$$k$$$ can be $$$1$$$ or $$$2$$$. We denote $$$x$$$ as $$$\sum_{}^{} (dp_{v, 2} + sub_v)$$$, where $$$v$$$ is a child of $$$u$$$. To calcuate the $$$dp$$$ values, we can create $$$cand$$$, which stores the maximum $$$2$$$ values of $$$dp_{v, 2} + sub_v - dp_{v, 1}$$$ in decreasing order. This acts like giving a path to node $$$v$$$.

$$$dp_{u, 1} = x - cand_0$$$

$$$dp_{u, 2} = min(dp_{u, 1}, x - mx, x - cand_0 - cand_1)$$$, where $$$mx$$$ is $$$max(sub_v)$$$, which is basically giving both paths to $$$1$$$ node.

The answer is $$$2 \cdot (dp_{1, 2} + sub_1)$$$.

Code