xiaowuc1's blog

By xiaowuc1, 2 years ago, In English

Hi all,

The first contest of the 2022-2023 USACO season will be running from December 16th to December 19th this weekend. 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?

This contest runs until December 19th, 23:59 UTC-12 and is four hours long. The URL for the contest page can be found here.

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?

Probably not. Petition IOI to add Rust support first.

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

| Write comment?
»
2 years ago, # |
  Vote: I like it +27 Vote: I do not like it

hopefully before 2022 is over i will not be missing the shiny gold coloring on both cf and usaco :)

gl everyone!

  • »
    »
    2 years ago, # ^ |
      Vote: I like it +32 Vote: I do not like it

    You will miss it by getting platinum color in usaco

    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      Congrats on scoring 866 in Gold (and AKing silver); this qualifies for Plat without any doubt.

      Waiting for my turn next month now...

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

        ty bestie

        ur turn will come jan when u join me :DDD

        • »
          »
          »
          »
          »
          2 years ago, # ^ |
            Vote: I like it +8 Vote: I do not like it

          Yeah you really cracked off this contest. And to anyone else hoping to qual for plat, don't forget that jan and feb are still there.

  • »
    »
    2 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    I want gold too

  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    omeganot, more like omegaorz. If you don't get gold, I'm screwed in silver

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

    hyper orz

»
2 years ago, # |
  Vote: I like it +4 Vote: I do not like it

My first USACO contest. I hope I can get to gold

»
2 years ago, # |
  Vote: I like it +4 Vote: I do not like it

Can we write some template at the beggining of the contest?

(Sorry, it will be my first USACO contest).

  • »
    »
    2 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    No, you are not allowed to use any prewritten code during the contest. All code you submit must be written within the time of the contest.

    edit: i can't read, see below

    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it -48 Vote: I do not like it

      how will u catch them? I used template in previous usaco contest but nothing happened.

      • »
        »
        »
        »
        2 years ago, # ^ |
          Vote: I like it +24 Vote: I do not like it

        man really admitted to breaking the rules :sob:

        • »
          »
          »
          »
          »
          2 years ago, # ^ |
          Rev. 2   Vote: I like it +53 Vote: I do not like it

          Can we all realize that this entire discussion really just started about writing a template during the contest

          • »
            »
            »
            »
            »
            »
            2 years ago, # ^ |
              Vote: I like it +21 Vote: I do not like it

            wait i actually can't read

            JanBobi Yes you can write the template after the beginning of the contest. So you can write it out from memory and then copy and paste it for your other submissions.

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

              Ok, thanks!

            • »
              »
              »
              »
              »
              »
              »
              2 years ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              Can I copy a piece of text unrelated directly to competitive programming from the internet?

              • »
                »
                »
                »
                »
                »
                »
                »
                2 years ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

                Not too sure, but USACO rules say that you can only search up stuff relating to the syntax of your language. So I guess (maybe?) you can copy-paste really basic stuff like take input, initialize vector, etc. but of course there's not much point of that.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  2 years ago, # ^ |
                    Vote: I like it -11 Vote: I do not like it

                  What if I have prewritten not-code. Can I copy it to my source code in contest?

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  2 years ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  I assume not, otherwise you could just write whatever templates you have in pseudo-code and convert it to C++ during the contest :P

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  2 years ago, # ^ |
                    Vote: I like it -6 Vote: I do not like it

                  What if I have a prewritten piece of literature. Can I copy it to my source code in contest?

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

                  I'm sure the USACO grading servers will enjoy reading some Shakespeare but they'll also refuse to compile it.

»
2 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it
USACO
  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    USACO
»
2 years ago, # |
  Vote: I like it +5 Vote: I do not like it

glhf!

yall got this <33

»
2 years ago, # |
  Vote: I like it +65 Vote: I do not like it

Are the exact times when the contest window is open and closed published anywhere? Also, what is the duration?

  • »
    »
    2 years ago, # ^ |
    Rev. 2   Vote: I like it +30 Vote: I do not like it

    I believe it runs from 5AM on the 16th to 5AM on the 20th (both times in Pacific Standard Time; it's 1PM UTC).

    You can take the contest in any 4-hour window over those 4 days. Note that if you start too late, the 4-day contest period may end before your 4-hour window ends.

    More information can be found here.

    xiaowuc1, could you add this to the post?

    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it +18 Vote: I do not like it

      I think you were off by 1h. Should be 4am pst unless my memory very bad since I always took in last 4 hours possible :clown:.

    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      If you are right, time period is 3 days, not 4 days. The correct time period is 4 days.

  • »
    »
    2 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    The exact parameters are not published until the contest goes live, I have updated the blog post accordingly. This contest runs for four hours and closes on December 19th at 23:59, UTC-12.

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

Hope I get silver! Have been practicing hard recently! Good luck to everyone else!

»
2 years ago, # |
  Vote: I like it +21 Vote: I do not like it

Excited to get smashed by new problems! YaYYYYYYY

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can I participate in USACO contest. If yes, how?

»
2 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

It's going to be super fun bricking silver. Edit: Bricked Silver. Jesus Christ, I don't even remember a time when I wasn't in silver smh.

»
2 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

[deleted]

»
2 years ago, # |
Rev. 2   Vote: I like it +3 Vote: I do not like it

Whom can I ask a question about P3 in Silver?...

I'm getting the strangest verdict in my entire life

My answer for the sample is correct, but I keep getting this:

  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I tried to print "W", and it still says that my answer is incorrect D:

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

    At the bottom of the contest page: “Please email the contest director (bcdean@clemson.edu) if you come across any technical problems.”

    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      Thanks! But I highly doubt that I will recieve an answer till the end of my virtual contest(

      • »
        »
        »
        »
        2 years ago, # ^ |
          Vote: I like it +8 Vote: I do not like it

        USACO grading is sometimes strict, you may have to put exactly one newline at the end of your output. But more likely they are having a grader bug which you will have to wait to get fixed D:

        • »
          »
          »
          »
          »
          2 years ago, # ^ |
            Vote: I like it +8 Vote: I do not like it

          Thanks! It would be sad if there's a bug, because I also wanted to try Gold and Platinum :D

  • »
    »
    2 years ago, # ^ |
      Vote: I like it +24 Vote: I do not like it

    The checker is space sensitive.

    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      Damn! Thank you so much, now it works!!!

»
2 years ago, # |
Rev. 2   Vote: I like it -52 Vote: I do not like it

deleted

  • »
    »
    2 years ago, # ^ |
      Vote: I like it +37 Vote: I do not like it

    You are not allowed to discuss anything about the problem during the contest window. Please delete this comment immediately. If you have any questions about a problem, email the contest director at bcdean@clemson.edu.

»
2 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Hi! I am facing an issue participating in USACO.

I submitted my code to problem A (Gold), and it kept telling me "Waiting for Available Grading Server" for minutes and then ended up with "Grading Failure due to Internal Error; Contact USACO Staff".

What should I do now, or am I going to end USACO2022DEC contest without any valid submission? :(

UPD: The grading server works now.

»
2 years ago, # |
  Vote: I like it +51 Vote: I do not like it

Reminder: this blog post is not actively monitored by the contest director. The contest site provides an email address to contact about technical problems; posting here is ineffectual at best and, in most cases (including all three clarification requests posted in this thread), doing so communicates information about the problems/your performance, which is prohibited by the rules of the competition.

»
2 years ago, # |
Rev. 2   Vote: I like it -97 Vote: I do not like it

.

»
2 years ago, # |
  Vote: I like it +6 Vote: I do not like it

I think the deadline has passed? Can we discuss the solution now?

»
2 years ago, # |
  Vote: I like it +1 Vote: I do not like it

I really liked the problems from gold division, especially "Mountains".

For the platinum division, I liked the problems, but "Breakdown" is much harder compared to the other two problems. I got AC on "Palindromes" and "Making Friends" in ~1h30min and spent the rest of the contest trying to solve k = 5 and optimize k = 4 (I solved it in n³ but was getting MLE).

Does anyone that solved "Breakdown" (or at least k >= 5) can give me some hints? Thanks in advance :).

  • »
    »
    2 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    How to solve "Mountains"? I can only manage to solve it with QN^2 , pass half of the testcases.

    I also wondering how to solve the rest two. For "Bribing Friends" I can only solve it with dp[2][costa][costb] pass 15/20, and for "Strongest Friendship Group", although I passed all the test cases, what I do is just enumerate minimal degree and combine with SCC

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

      for bribing friends notice that for some subset of cows, it's optimal to use ice creams on the smallest x cows. So this also means that using that greedy on some subset will never result in more than one cow being split between money/ice creams used on it. So sort by x value, run one knapsack dp on the ice creams in O(NB), then transition to using moneys through the one(or zero) split cow, and run another knapsack on money in O(NA).

      • »
        »
        »
        »
        2 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Thanks~, I got it.

        Just wondering how do you come up with the greedy? The left is just standard problem with a little trick

    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Can you elaborate on p3 (Strongest Friendship Group)?

      By the way I too passed half of the testcases in Mountains and got 15/20 in Bribing Friends so I guess p3 kept me from reaching Plat :)

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

        For P3.

        1. just enumerate the minimal degree of the subgraph

        2. for the given degree d, erase all the nodes that degree < d and also remove the edges.

        3. go back to 2 and make the subgraph "converge".

        And Also I use lots of constant optimization to pass all the testcases.

        Wondering is this the intended solution?

        • »
          »
          »
          »
          »
          2 years ago, # ^ |
          Rev. 2   Vote: I like it +3 Vote: I do not like it

          Maintain the order of edge removal. Then, using DSU, add edges to the empty graph in reverse order, so that connected components are only merged and we can easily keep track of the maximum size in $$$O(n+m\alpha (n))$$$ instead of brute-forcing in $$$O((n+m)\sqrt{m})$$$.

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

          I had a $$$O(m\log n + n\alpha(n))$$$ solution, where I first maintain a set of vertices that are not erased, and in each iteration, I erase the vertex with the lowest degree and update the adjacent vertices. I store the order of removal in an array, and reverse the array. Then, I maintain a DSU and then iterate over the array, adding edges in the DSU.

    • »
      »
      »
      2 years ago, # ^ |
      Rev. 3   Vote: I like it +11 Vote: I do not like it

      Solution of "Bribing Friends":

      I don´t remember what was used to get the discounts, but I will assume it is cones.

      Let's order the friends from greatest to smallest Xi, we can prove that if our optimal answer is the set of friends, $$$id_1,id_2...id_k$$$, such that id is increasing, we will take a suffix $$$(i+1,k)$$$ for free (apply the discount until it is free), paying a total of 0 mooneis and $$$C_{id_j}*X_{id_j}$$$ cones for every $$$i+1 <= j <= k$$$., and take a partial discount for $$$id_i$$$, paying a total of $$$C_{id_i} - \lfloor ConesRemaining/X_{id_i} \rfloor$$$.

      In the optimal answer, we use only mooney from $$$1$$$ to $$$i-1$$$, mooney and cones in $$$i$$$, and only cones from $$$i+1$$$ to $$$n$$$. Now we can solve this problems with two DP:

      $$$dpc_{i,j}$$$ = maximum popularity solving for $$$(1,i)$$$, spending j mooneis and 0 cones.

      $$$dpx_{i,j}$$$ = maximum popularity solving for $$$(1,i)$$$, spending j cones and $$$at$$$ $$$ most$$$ A mooneis.

      Transitions:

      $$$dpc_{i,j} = max(dpc_{i-1,j}, dpc_{i-1,j-C_i}+P_i)$$$

      $$$dpx_{i,j} = max(dpx_{i-1,j}, dpx_{i-1,j-C_i*X_i}+P_i, dpc_{i-1,A-\lfloor j/X_i\rfloor})$$$ -> You also need to check whether you can use all cones $$$j$$$ cones remaining on $$$i$$$.

      The answer will be $$$max(dpx_{n,j})$$$ for every $$$1 <= j <= B$$$.

      Hope that this can help you to understand the problem :)

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

        Thank you very much!

        It seems that I can get the intuition that why we need to sort by xi desc then use find the suffix of friends by exchange Cones (maybe it will be more possible to get the "P freely")

        But I have two questions about it.

        1. Although it's correct and meet my intuition, but can we prove it is correct?

        2. When you are solving this problem, how do you come up with this idea? It's hard for me to come up with this.

        • »
          »
          »
          »
          »
          2 years ago, # ^ |
            Vote: I like it +6 Vote: I do not like it
          1. To prove that the optimal answer is in this format: If we fix the set of friends that we want to choose, and now we are trying to discover the least amout of mooney spend to pay them, the best way to lower the total amout of mooney spend is applying the discount in the friend with the smallest Xi, since it will always decrease the total amout of mooney spend by 1. So the "greedy" ideia is to apply the discount to the friend (from the set of friends that we want do choose) with the smallest Xi until it's not free, and them get doing it until I cannot apply any new discount.

          2. To come up with this ideia I think about how the optimal answer would look like and how I can apply some restrictions to the answer so I can optimize my DP. When the problem looks like a DP problem and I have to reduce the amout of states, it is very usual to try to restrict the answer.

  • »
    »
    2 years ago, # ^ |
      Vote: I like it +28 Vote: I do not like it

    If you go backwards you can easily update 2-edge distance (and 1-edge distances of course) between all pair of vertices. That's already enough for $$$k<=4$$$ — you just check all possible middle vertices on the path from 1 to $$$n$$$.

    $k<=6$
    $k<=8$
    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it +14 Vote: I do not like it

      I got AC in 1.4 second by just running Dijkstra every time I add a new vertex, starting from the tail of the added edge. I run Dijkstra on modified graph where vertices are (k, v) for v any original vertex and 0<=k<=K. I guess tests were weak.

      • »
        »
        »
        »
        2 years ago, # ^ |
          Vote: I like it -10 Vote: I do not like it

        I ran nsqrt(m) and then binary searched on TLE/WA with how far up the sqrt(m) I really search before breaking :) weak pretests op

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve "Reverse Engineering" problem from Bronze division?

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

    Bump, also couldn't figure out.

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

    You can incrementally build the program one if statement at a time until either your program can handle all the pairs or it's impossible to distinguish them.

»
2 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

I think the last window is still active as one can start their window at last second and will still get 4 hours. So, I think it would be better to wait for discussion till the last 4 hours end, which ends in about 2 hrs 35 mins from the time of this comment

Edit : Wrong Info

  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    The contest closes Dec 19 at 23:59 UTC-12 time (even if your personal clock is still running at that time, so do not wait until the very last minute to start!).

»
2 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

How do you guys find the difficulty of bronze problems ? I think that the first one is pretty easy , the second one is very nice and suitable for P2 and the third one is very hard :(

»
2 years ago, # |
Rev. 2   Vote: I like it +57 Vote: I do not like it

Platinum Solutions:

Problem 1
Problem 2
Problem 3
  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Problem 2 can be solved in $$$O(nlogn)$$$ and Problem 3 can be solved in $$$O(n^2)$$$.

    I suppose the $$$O(n^2logn)$$$ solution for Problem 3 shouldn't pass.

    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it +4 Vote: I do not like it

      I used a $$$O(n²logn)$$$ solution with BIT and It worked in ~1300ms

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

      Problem 2 can actually be solved in $$$O(n \alpha(n))$$$ time by counting contribution by the larger of $$$u$$$ and $$$v$$$. Consider the "union-find tree" of components that we encounter as we build the MST. Then, the contribution of $$$v$$$ is the total number of ancestors (without multiplicity) of the smaller vertices it has direct edges to. This requires only LCA queries to answer, which we can do with Tarjan's offline LCA algorithm.

      We can speed this up further to $$$O(n)$$$ time using linear-time MST and linear-time LCA, but those both require using the WordRAM Model.

  • »
    »
    2 years ago, # ^ |
    Rev. 2   Vote: I like it +10 Vote: I do not like it

    Use a pointer and a bucket instead of Fenwick tree. When you you want to query the sum of some prefix, move the pointer to this position and subtract/add the values on the positions passed. It can be shown that the distant sum is $$$O(n^2)$$$

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Did anyone else feel that the silver and gold divisons were slightly easier than average this time?

I AKed silver after giving up on USACO last year and am motivated to try to reach Plat in the next 3 contests :)

»
2 years ago, # |
Rev. 2   Vote: I like it +6 Vote: I do not like it

thoughts on cutoff & 750?

  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    um tbh i wouldn’t count it on too hard

    I thought this contest was easier than last open quite a bit (in terms of getting over 800 points) and last open had a 800 cutoff..

»
2 years ago, # |
  Vote: I like it +21 Vote: I do not like it

It seems that some people's $$$n^2\log n$$$ solution can pass problem 3. My $$$n^2$$$ even runs slower than $$$n^2\log n$$$.

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone provide solutions for the bronze problems?

»
2 years ago, # |
  Vote: I like it +3 Vote: I do not like it

What is the silver cutoff going to be? Any estimates/guesses?

»
2 years ago, # |
  Vote: I like it +3 Vote: I do not like it

couldn't ak silver

»
2 years ago, # |
  Vote: I like it +13 Vote: I do not like it

Results are available in the website

»
2 years ago, # |
  Vote: I like it +16 Vote: I do not like it

There are some solutions with wrong time complexity can pass all the tests of the Platinum problem Breakdown. For example, run Bellman-Ford after adding every edge can pass the problem in $$$O(kn^4)$$$ and it is much faster than my $$$O(n^3)$$$ solution. Besides, the wrong solutions is much easier than the right solution.

»
2 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

When I open my submission for Bribing Friends in Gold, it show a blank page: http://usaco.org/current/viewsource.php?sid=4318354 Is this intended? (my other submissions are all shown correctly)

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

If anyone who solved Bronze 3 could give it a difficulty in CF rating how would you gauge it? I usually AC bronze but that one bamboozled me.