xiaowuc1's blog

USACO 2021-2022 Third Contest
By xiaowuc1, 2 years ago, In English

Hi all,

The third contest of the 2021-2022 USACO season will be running from February 25th to February 28th 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).

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

Comments Comments (48)
| Write comment?
»
2 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Hope the problems are fun!

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

Wish everyone luck!

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

lets hope for no triple-qi combos

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

is it open to everyone? if yes , how can i participate?

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

Let's hope for 3 data structure problems in plat by xiaowuc1

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

    Do you genuinely want to solve 3 data structure problems? I don't have issues solving them in ICPC competitions (for me it's most of the times applying standard techniques), but I like to participate in IOI-style because having only 3 problems allows to make them harder not only in terms of implementation, but most importantly in terms of ideas.

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

      That's why I want to solve data structure problems

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

    You still have at least 28 ruby data structures problems to do. Get back to work.

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

i doesn't participate previous contest. can i participate in this contest ? if yes, then how ? cause i doesn't find any link which redirect me to February contest. i'm little bit confused. pls anyone help to understand how it works. thanks in advance

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

    Finding the contest is the first test.

    Jokes aside, literally the first thing you see on the USACO website is the announcement for the February contest, and there is a sentence saying "For more details, please visit the contest page here." All you have to do is to click on the word "here" and you get redirected to a page, where if the contest period has started, you can start your 4 hour block there, but at the moment, we have to wait another 2 hours and 30 minutes.

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

      [user:Bungmint]thank you very much for detailed explanation. i check this 1 hour before writing this comment, and in this moment nothing about february contest not posted. but know i saw it. and i'm very glad really)) I have been trying to participate in this competition for a long time, but because of the huge amount of work I do not have time. I think this time I managed to do it

      → Reply
»
2 years ago, # |
← Rev. 2   Vote: I like it -41 Vote: I do not like it

.

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

    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.

    → Reply
  • »
    »
    2 years ago, # ^ |
    ← Rev. 2   Vote: I like it +1 Vote: I do not like it

    I am in the Gold Division, so I have not and cannot look at Silver Division problems. Besides, discussion about them is not allowed until after the window ends.

    To answer your generic question, USACO Silver problems likely correspond to the 1200-1700 interval. It varies a lot by contest, but certainly silver questions' difficulties do not exceed 1700, nor drop below 1200, barring irregular circumstances.

    Keep in mind that the premise of your question is somewhat flawed. USACO contests have only 3 problems and 4 hours whereas Codeforces contests have $$$\ge$$$ 5 problems and last $$$2$$$ to $$$3$$$ hours. With USACO, you devote your exclusive attention to a relativity small subset of problems for much more time. Hence, someone with a CF rating of 1500, may be able to regularly solve 1700-equivalent problems in USACO, due to the increase in time limit and lack of pressure.

    Also, USACO and CF problems are fundamentally different in nature. USACO problems are frequently fairly implementation heavy, whereas CF problems require you to think for more time and type less.

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

      (disclaimer: haven't taken this month's contest, speaking from recent history)

      Silver has been unreasonably buffed as of late. It's expected nowadays for a silver contest to have at least 1 problem above the 1700 rating range, and even 2 half of the time.

      For reference, the silver problems last month would be around 1800, 1400, and 2200 rated by my eye estimate. The hardest problem had a lot of weak testcases that fell to different heuristics, and you essentially needed to either solve it or get really lucky with which "cheese" approach you used to promote.

      USACO problems have gotten more CF-like as of late too. (more math heavy etc.)

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

        I didn't look at recent USACO Silver problems, from the last two contests. I was basing it off of problems from 2020 and before, which I recognize is probably not the best idea.

        I looked at the most recent 3 problems. I would hesitate to agree with your assessment. I think the last problem was probably around 1900 or 2000, which is much higher than my upper bound of 1700. Definitely much harder than in the past, but not 2200.

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

          I think that this website has a solid indicator for the ratings of the past Silver problems: https://codetiger.me/project/usaco/ although some ratings are a bit inconsistent due to the lack of voters on some problems.

          There definitely have been Silver problems that could be considered over the rating of 1700 including Meetings and Cow Steeplechase II.

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

            Yes, you are right — in hindsight, I was largely basing my data on the four USACO Silver contests I had partaken in, which happened to be easier than usual.

            There are many problems that are over 1700 rating, including one 2200 problem.

            Thanks for the correction!

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

What is test 5 on Platinum Problem 2. Sleeping in Class? I had an $$$O(NX + QD/X)$$$ solution where $$$D$$$ = number of divisors of the sum of $$$a_i$$$. (I split the prime divisors into two parts)

Was the intended solution $$$O((N + Q)K + 2^K*D)$$$ where $$$D$$$ is the number of divisors of sum and $$$K$$$ is the number of distinct primes dividing the sum?

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

    My solution is $$$O(NK+DK+Q)$$$（Perhaps $$$O(NK+DK+Q\log D)$$$ if you use map). Let $$$s_i$$$ denote the prefix sum of $$$a$$$, then for a query $$$x$$$, we need to find the number of $$$i$$$ that satisfies $$$x|s_i$$$, which is equivalent to for any prime divisor $$$k$$$, we have $$$f(s_i,k)\ge f(x,k)$$$, where $$$f(a,b)$$$ denotes the maximum $$$q$$$ such that $$$b^q|a$$$. Besides, $$$x$$$ has to be a divisor of $$$s_n$$$ to make the answer non-zero, which means we can only consider all primes divisible by $$$s_n$$$. By doing prework we can find the answer to all divisors of $$$s_n$$$ using the similar techinique as in arc136d in $$$O(DK)$$$ time.

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

How to do the problem 2 from Silver Division. I tried using Meet in the Middle. But it did not work on any of the later testcases where N<=40.

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

    It works. I solved this problem using Meet in the middle + two pointers.

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

      If the sections with the same values on both sides are very long in succession, the two pointers seem to be timed out. How did you solve this problem?

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

        No it doesn't affect. All the index pairs you traverse will also just be the sum of the number coordinates you can get in the first half plus the second half. I am bad at English so if you don't understand you can see my implementation : https://ideone.com/c2Qwta. My solution pass < 1500ms

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

      tried meet in the middle + binary search but tle'd for bigger tests lol. Lesson: Use two ptrs when possible

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

        My $$$O(2^{\frac{n}{2}} \cdot n^2)$$$ solution with binary search gets AC safely below the time limit (< 2s). Though I only perform binary search $$$O(2^{\frac{n}{2}})$$$ times, so that may be the reason.

        My code.

        → Reply
»
2 years ago, # |
  Vote: I like it +10 Vote: I do not like it

Platinum problem 1 resembles JOI Final 2014 Problem 5 :o

→ Reply
»
2 years ago, # |
  Vote: I like it +10 Vote: I do not like it

How to do the problem 1 from Gold Division.

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

    I got 9 test cases :(

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

    Each cow will recive exacly 1 gift and give exacly 1 gift, the In-degree and Out-degree of each vertex is 1 and the final graph will be several cycles.

    Let's dp(i,mask) = we are in vertex i, mask is the bitmask of the vertices unvisited + the begin of the current cycle and the least significant bit of mask is the begin of the current cycle (let's call this lsb). This is important to save complexity (we don't have to save the begin of the cycle as a state). The transitions are:

    For each j, if bit j is active in the mask, j can recive the gift i and j != lsb : dp(i,mask)+= dp(j,mask-(1<<j))

    If lsb can recive the gift i, we can finish the cycle and continue with the new mask and the new lsb : dp(j,mask)+= dp(lsb of (mask-(1<<lsb)), mask-(1<<lsb))

    To answer the queries, let's consider mask1 = bitmask of H and mask2 = bitmask of G, the answer is dp(lsb of mask1,mask1)*dp(lsb of mask2,mask2).

    Here is my code

    Sorry for my bad english.

    → Reply
  • »
    »
    2 years ago, # ^ |
    ← Rev. 7   Vote: I like it +22 Vote: I do not like it
    First Steps
    How to use this structure?
    How to calculate this structure?
    → Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I got 500 on gold division. 0% chance of promotion, right?

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

    Based on the past gold cuts prolly lol. Like the lowest cutoff was something like 600 in 2020

    → Reply
»
2 years ago, # |
← Rev. 2   Vote: I like it +40 Vote: I do not like it

Just my thoughts, but it really feels like Silver and Gold were sorted in descending order of difficulty. Also while the ideas in silver were more standard, they were all or nothing and you could easily get stuck on constant factor optimization in P1 and P2.

In silver:

P1 — Got $$$(2n)^3$$$ edges construction, then wasted 30+ mins thinking of $$$O(n ^ 2)$$$ / $$$O(n ^ 2 \log n)$$$ before getting $$$n^3$$$ edges idea.

P2 — Obviously meet in the middle. Spent 1 hour on constant factor optimization due to poor implementation skills though T_T.

P3 — Main condition about advancing folders is obvious, after that its just fairly simple implementation.

In gold:

P1 — Got $$$O(3^n \cdot n)$$$ fairly quickly, then bricked on a $$$O(2^n \cdot n^2)$$$ for rest of contest due to overcounting.

P2 — Cool problem, intended answer became clear after coding the subtask.

P3 — Guessed the answer as soon as I read $$$0 \leq y \leq 10$$$, it feels much easier than P1 or P2. Though I'm probably biased since a subtask of a problem I set used the same trick, except on Manhattan distance. Still, it was definitely cool to realize why the trick extends to Euclidian distance as well, I had never thought about it before.

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

    How did you manage to do problems from both divisions — did you in-contest promote from silver to gold?

    → Reply
    • »
      »
      »
      2 years ago, # ^ |
      ← Rev. 2   Vote: I like it +4 Vote: I do not like it

      Yeah, the previous contest was my first USACO contest. After solving bronze fairly quickly, I underestimated silver and started it even though I only had around 1.5 hours free. Bricked and left after not getting a single full solve in 1 hour so obviously did not promote.

      This time silver started out similar (no full solve for 1.5+ hours), but managed to full solve it and promote after around 3 hours.

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

where can i find editorial?

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

    U gotta wait til the results come out. Then the editorial should be on the contest page just as any other USACO contests.

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

My sol. for P1 Bronze div. I got the full score in it also it should give TLE for the case of n = 1e5 and all the elements in the array are zeroes (if it exists) My sol. for P2 I really liked this problem , the main observation is that when we move a cow from the right to the left the position of all cows with positions less than that of the currently moved cow increases by one so we can use ordered set to count the number of cows with higher positions than the current one that has been moved to the left efficiently My sol. for P3 it's a basic backtracking problem we can just generate all the strings that can be made and store them in a map

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

Will the Chinese translation be out soon? (Or will it be out?) Some Chinese OJ is waiting for them

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

Interesting fact: I was upsolving the silver problems, and on "Robot Instructions", replacing map<pair<int, int>, ... with unordered_map with the hash function from the editorial increased my score from 50% to 100% o.O

→ Reply