### xiaowuc1's blog

By xiaowuc1, 2 weeks ago,

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.

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.

• +69

 » 2 weeks ago, # | ← Rev. 2 →   +9 Hopefully I can get Gold this time around. Edit: Got it!
•  » » 2 weeks ago, # ^ |   0 Same. Good luck!
•  » » 13 days ago, # ^ |   0 I think you got it bro.
•  » » 11 days ago, # ^ |   0 u got this!
•  » » 5 days ago, # ^ |   +3 Congrats on promoting!
•  » » » 5 days ago, # ^ |   0 Thank you so much! But if the cutoff is 900, I'm kinda screwed.
 » 2 weeks ago, # |   +5 pain
 » 2 weeks ago, # |   +12 plat pleaseeeeeeeeeeeee it has been way too long :sob:would kind of sucky if 16 points away from cutoff again :((((
•  » » 2 weeks ago, # ^ |   +40 This time you will be 16 points away from scoring 1016
•  » » » 13 days ago, # ^ |   +10 Uncle Ruckus from The Boondocks getting his ancestry result be like
•  » » » 13 days ago, # ^ | ← Rev. 2 →   +24 So envy is going to get a 1032
•  » » 2 weeks ago, # ^ |   0 omg same although it hasn't been long only 1 month
•  » » 2 weeks ago, # ^ |   0 Wow how hard is it to get plat O_O. ur CM...
•  » » » 13 days ago, # ^ |   +10 Ask timreizin
•  » » » » 12 days ago, # ^ |   +21 IMPOSSIBLE
•  » » » 13 days ago, # ^ |   +9 It really depends on the person, but I got to IM before I got plat ...
•  » » 5 days ago, # ^ |   +3 Congrats bestie :))))
•  » » » 5 days ago, # ^ |   +3 though i was in fact, 208 points off of 1016 :(
 » 13 days ago, # |   0 to clear the Bronze, what should be the rating on CF? please reply um noob
•  » » 13 days ago, # ^ | ← Rev. 2 →   +17 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.
•  » » 13 days ago, # ^ |   +30 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.
•  » » 12 days ago, # ^ |   +16 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.
•  » » 11 days ago, # ^ |   +13 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.
•  » » 11 days ago, # ^ |   0 I cleared Bronze with 500 or 600 CF rating, but CF and USACO problems are different,You need to understand.
•  » » 11 days ago, # ^ |   0 My username could not clear bronze with 2097 CF rating and it will forever be stuck in bronze.
•  » » 7 days ago, # ^ |   0 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.
•  » » 5 days ago, # ^ |   +9 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.
 » 13 days ago, # |   +19 First time plat contestant here. My goal last month was to score 1000 in USACO; have to adjust that number to 100 now xD
•  » » 13 days ago, # ^ |   +6 As a first time gold contestant, I want to pass :clown:
 » 10 days ago, # |   0 Gold is too hard for me and I will try the problems of silver too.
 » 8 days ago, # |   +19 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.
•  » » 8 days ago, # ^ |   +25 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.
•  » » » 8 days ago, # ^ |   +43 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.
•  » » 8 days ago, # ^ |   -16 I think USACO said at some point they wanted to make the problems more “mathy”.
 » 8 days ago, # | ← Rev. 2 →   0 Does anyone know how USACO proctor its contestants? (I have taken the test already and I have no intention to cheat)
 » 5 days ago, # |   +8 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.
•  » » 4 days ago, # ^ | ← Rev. 2 →   +1 Try this test case: 1 abcde baacb 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}$
•  » » » 4 days ago, # ^ |   0 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.
•  » » » 4 days ago, # ^ |   0 Thank you.
 » 5 days ago, # | ← Rev. 2 →   +8 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!)
•  » » 5 days ago, # ^ |   0 The contest for you ends at your 4 hour mark, or January 31 UTC-12, whichever comes sooner
•  » » » 5 days ago, # ^ |   0 Okay. My bad I forgot about this rule, I should have started an hour earlier then.
 » 5 days ago, # |   0 Ideas for the first problem in gold?
•  » » 5 days ago, # ^ |   +5 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 :(
•  » » » 5 days ago, # ^ |   +3 you are thinking in the wrong direction, there is (to my knowledge) no greedy strategyInstead, 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
•  » » » » 5 days ago, # ^ |   +3 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.
•  » » » » » 5 days ago, # ^ |   0 my complexity was 2^n * n^2 + T*n
•  » » » » » » 5 days ago, # ^ |   0 Dominater069 Orzz.
•  » » 5 days ago, # ^ |   +3 Here is O(N^2) solution:Let's analyze the sample.$l=3$, $r=8$ 'a' -> "ab", 'a' -> "bc", 'c' -> "de", 'b' -> "bbb" After reversing: 'b' -> "bbb" 'c' -> "de" 'a' -> "bc" = "bbb" + "de" 'a' -> "ab" = "bbbde" + "bbb" 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.
•  » » 5 days ago, # ^ |   +6 I got full score by making a tree using pointers and some small optimisations
 » 5 days ago, # |   0 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.
•  » » 5 days ago, # ^ | ← Rev. 3 →   0 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.
•  » » 4 days ago, # ^ |   0 my messy but ac code#include using namespace std; #define dg(x) cout<<#x<<"="< g[N]; int cal(char x){ if ('a'<=x && x<='z'){ return x-'a'; } else{ return x-'A'+26; } } void dfs(int v){ // cout<1); cur=fa[cur]; } ff|=(cc[u]>1); cnt-=ff; allcyc+=c+1; bad|=(c+1==52); } } vis[v]=2; } void find_cycles(){ cnt=0; bad=0; allcyc=0; for (int i=0; i>s>>t; set st; for (int i=0; i"<1 || g[i].size() && no[i]){ cout<<-1<>t; while (t--){ solve(); } return 0; } 
 » 5 days ago, # |   +26 Posting 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
•  » » 2 days ago, # ^ |   0 This is a really clever application of binary lifting; do you know any similar problems?
 » 5 days ago, # |   0 Solution to plat p2 or p3?
•  » » 4 days ago, # ^ |   +19 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. Code#include using namespace std; using ll = long long; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; vector p(n), sz(n); vector dp(n, array{}); //dp[i][0] - just what the problem asks vector> adj(n); for (int i = 1; i < n; ++i) { cin >> p[i]; p[i] -= 1; adj[p[i]].push_back(i); } for (int i = n - 1; i >= 0; --i) { dp[i][0] = dp[i][1] = dp[i][2] = numeric_limits::max() / 2; sz[i] = 1; for (int to : adj[i]) { sz[i] += sz[to]; } if (adj[i].empty()) { dp[i][0] = 2, dp[i][1] = 1, dp[i][2] = 1; continue; } if (adj[i].size() == 1) { dp[i][0] = dp[adj[i][0]][0] + 2; dp[i][1] = dp[adj[i][0]][1] + 1; dp[i][2] = dp[adj[i][0]][2] + 1; continue; } ll sum = 0, best = 0; for (int to : adj[i]) { sum += dp[to][0] + sz[to]; best = min(best, dp[to][1] - (dp[to][0] + sz[to])); } dp[i][1] = sum + best + 1; sum = best = 0; for (int to : adj[i]) { sum += dp[to][0] + sz[to]; best = min(best, dp[to][2] - (dp[to][0] + sz[to])); } dp[i][2] = sum + best + 1; sum = 0, best = 0; for (int to : adj[i]) { sum += dp[to][0] + 2 * sz[to]; best = min(best, -2LL * sz[to]); } dp[i][0] = sum + best + 2; sum = 0; vector> a2, a1; for (int to : adj[i]) { ll val = dp[to][0] + sz[to] * 2; sum += val; a2.emplace_back(dp[to][2] + sz[to] - val, to); a1.emplace_back(dp[to][1] + sz[to] - val, to); } sort(a1.begin(), a1.end()), sort(a2.begin(), a2.end()); if (a1.front().second != a2.front().second) { dp[i][0] = min(dp[i][0], sum + a1.front().first + a2.front().first + 2); } else { dp[i][0] = min({dp[i][0], sum + a1[0].first + a2[1].first + 2, sum + a1[1].first + a2[0].first + 2}); } } cout << dp[0][0] << '\n'; return 0; } 
•  » » 4 days ago, # ^ |   +19 P2: 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<
•  » » 4 days ago, # ^ |   +19 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#include using namespace std; typedef long long ll; const int N = 200005; const ll inf = 1e18 + 5; vector adj[N]; ll dp[N][2], sub[N]; int n; int main() { cin >> n; for (int i = 1; i < n; i++) { int p; cin >> p; p--; adj[p].push_back(i); } for (int u = n - 1; u >= 0; u--) { sub[u] = 1; ll x = 0, mx = -inf; vector best; for (int v : adj[u]) { sub[u] += sub[v], mx = max(mx, sub[v]); x += dp[v][1] + sub[v]; best.push_back(dp[v][1] + sub[v] - dp[v][0]); sort(best.rbegin(), best.rend()); if (best.size() > 2) best.pop_back(); } if (best.size() > 0) dp[u][0] = dp[u][1] = x - best[0]; if (best.size() > 0) dp[u][1] = min(dp[u][1], x - mx); if (best.size() > 1) dp[u][1] = min(dp[u][1], x - best[0] - best[1]); } cout << (dp[0][1] + sub[0]) * 2 << "\n"; }