When submitting a solution in C++, please select either C++14 (GCC 6-32) or C++17 (GCC 7-32) as your compiler. ×

xiaowuc1's blog

By xiaowuc1, 14 months ago, In English

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.

  • Vote: I like it
  • +69
  • Vote: I do not like it

| Write comment?
»
14 months ago, # |
Rev. 2   Vote: I like it +9 Vote: I do not like it

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

  • »
    »
    14 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Same. Good luck!

  • »
    »
    14 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Congrats on promoting!

    • »
      »
      »
      14 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

»
14 months ago, # |
  Vote: I like it +5 Vote: I do not like it

pain

»
14 months ago, # |
  Vote: I like it +12 Vote: I do not like it

plat pleaseeeeeeeeeeeee it has been way too long :sob:

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

»
14 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    14 months ago, # ^ |
    Rev. 2   Vote: I like it +17 Vote: I do not like it

    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.

  • »
    »
    14 months ago, # ^ |
      Vote: I like it +30 Vote: I do not like it

    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.

  • »
    »
    14 months ago, # ^ |
      Vote: I like it +16 Vote: I do not like it

    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.

  • »
    »
    14 months ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

    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.

  • »
    »
    14 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    14 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    14 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

  • »
    »
    14 months ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

    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.

»
14 months ago, # |
  Vote: I like it +19 Vote: I do not like it

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

  • »
    »
    14 months ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

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

»
14 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
14 months ago, # |
  Vote: I like it +19 Vote: I do not like it

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.

  • »
    »
    14 months ago, # ^ |
      Vote: I like it +25 Vote: I do not like it

    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.

    • »
      »
      »
      14 months ago, # ^ |
        Vote: I like it +43 Vote: I do not like it

      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.

»
14 months ago, # |
  Vote: I like it +8 Vote: I do not like it

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.

  • »
    »
    14 months ago, # ^ |
    Rev. 2   Vote: I like it +1 Vote: I do not like it

    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}$$$

    • »
      »
      »
      14 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

    • »
      »
      »
      14 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thank you.

»
14 months ago, # |
Rev. 2   Vote: I like it +8 Vote: I do not like it

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!)

  • »
    »
    14 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      14 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

»
14 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Ideas for the first problem in gold?

  • »
    »
    14 months ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    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 :(

    • »
      »
      »
      14 months ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      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

      • »
        »
        »
        »
        14 months ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        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.

  • »
    »
    14 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it
    Here is O(N^2) solution:
  • »
    »
    14 months ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

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

»
14 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

  • »
    »
    14 months ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    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.

»
14 months ago, # |
  Vote: I like it +26 Vote: I do not like it

Posting a neat solution to Plat P1 here

Plat P1
  • »
    »
    13 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

»
14 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Solution to plat p2 or p3?

  • »
    »
    14 months ago, # ^ |
      Vote: I like it +19 Vote: I do not like it
    P3
  • »
    »
    14 months ago, # ^ |
      Vote: I like it +19 Vote: I do not like it

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

  • »
    »
    14 months ago, # ^ |
      Vote: I like it +19 Vote: I do not like it

    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