xiaowuc1's blog

By xiaowuc1, 12 months ago, In English

Hi all,

The final contest of the 2022-2023 USACO season will be running from March 24th to March 27th. 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 March 24th.

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
  • +74
  • Vote: I do not like it

| Write comment?
»
12 months ago, # |
  Vote: I like it +9 Vote: I do not like it

Does the contest have division promotion?

»
12 months ago, # |
  Vote: I like it -7 Vote: I do not like it

How do I register for it?

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

    There is no registration. When the contest opens you can participate from the main page of usaco.org. why did this get downvoted

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

:scare:

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

I will probably fail Gold again.

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

Can anyone give me the intuition to solve silver P2 — FieldDay?

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

    I couldn't prove my solution but it seems like if we have a lot of unique teams (or numbers if you convert them into bitmasks) in the input, then chances of having a very close team match with any other team increase.

    So I did n ^ 2 for around 4000 ish unique numbers and for > 4000 I tried checking if a team difference starting from 0,1,2.. and onwards could be formed or not.

    some precomputation is involved which can be done in c * (2 ^ c).

    I didn't expect it to AC for full points. (actually I don't remember if it was maximum matching or minimum matching teams but either ways this method is applicable)

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

    make a graph with nodes from $$$[0,2^c)$$$. make edges between nodes with one bit difference. so there's an edge between 10011 and 11011 for example. Now the main part is that you want an $$$a[j]$$$ that is most similar to $$$rev[a[i]]$$$ where $$$rev[a[i]]$$$ is $$$a[i]$$$ but with each bit flipped ($$$1$$$ to $$$0$$$ and $$$0$$$ to $$$1$$$). then you do a multisource bfs from all nodes in $$$a[i]$$$ as source. The answer for each $$$a[i]$$$ is $$$c-dist[rev[a[i]]$$$.

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

      Mind-blowing approach. Thanks a lot for sharing it :D

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

      Very cool. Wish I had thought of that.

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

    max distance of a bitmask x = C — min distance of inverteed bitmask

    run multisource bfs from the input

    print C — dist[~x]

  • »
    »
    12 months ago, # ^ |
    Rev. 3   Vote: I like it +6 Vote: I do not like it

    This problem similar with "COCI 2022/2023 -> Contest #5 -> Problem B". You can view here

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

    Check last COCI editorial problem 2

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

    thanks everyone for the solutions! expansion of my sight :D

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

Expect to score 650 points. Maybe I will have a 3% chance of promotion? :')

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

I tried to do some binary search from each 'b' to the next index of the next 'e' to next index of the next 's', 's', 'i', 'e'... for silver P3 and only passed the n<4000 cases. I wrote a brute forcer to check my binary search algorithm and couldn't find a countercase to it the entire time. Did anyone AC it with a similar approach?

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

    I mean this solution is correct but is not $$$O(n^2logn)$$$? ALso, it's extremely difficult to create good tests as a checker anyways btw

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

      I only binary searched to the nearest bessie completion. Then I added n-(last index) to my running count. So I only did 5 binary searches per index, so it would be n log n. I couldn't prove this to be correct, but like I said I tried a bunch of random strings and it matched the brute force every time.

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

        try bessibessie maybe? correct : 10

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

          My code works for that case, here it is if you want to take a look at it, I'd appreciate it if you could find a counter case

          Code
          • »
            »
            »
            »
            »
            »
            12 months ago, # ^ |
              Vote: I like it +8 Vote: I do not like it

            I choose to be optimistic that you will take this as a moment to teach the importance of proving your algorithms (brute force is not a replacement for a proof). And often when you can't prove an algorithm, you will find that the mistake lies in the part you couldn't prove.

            Anyway the fact that your solution passed for n<4000 was just luck: bessibessibessie

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

    Same passed for first 5 cases with binary search approach. I don't know why it is not working for larger values, i wasted a lot of time debugging it and trying all possibilities, still couldn't manage to get it AC.

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

      I was almost sure it was integer overflow, but I made sure everything was a long long so many times.

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

How did you solve Platinum P2? I solved it by implementing brute force and observing the patterns. I'm wondering if there's any solution that do not depend on observing it...

Formula
How did I find it
  • »
    »
    12 months ago, # ^ |
      Vote: I like it +18 Vote: I do not like it

    Observe that a prefix of the string with $$$x$$$ 0's and $$$y$$$ 1's essentially tells us, for each $$$a < x$$$ and $$$b < y$$$, whether $$$\frac{b}{a} \ge \frac{y}{x}$$$ or $$$\frac{b}{a} < \frac{y}{x}$$$. Thus, $$$f(A, B)$$$ is essentially the number of fractions $$$\frac{b}{a}$$$ such that there are no fractions with numerator/denominator less than $$$b$$$/$$$a$$$ which are between $$$\frac{B}{A} - \varepsilon$$$ and $$$\frac{b}{a} - \varepsilon$$$. The simplest way to analyze this is using the Stern-Brocot tree: if you consider the two best approximations of $$$\frac{B}{A}$$$, the next best approximation is their mediant. The rest of the problem is bookkeeping, making sure to deal with cases where $$$\gcd(a, b) > 1$$$.

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

    My approach doesn't rely on any unmotivated observations, though it does depend on knowing a bit of contest lore. I'll attempt an explanation below.

    Note that whether we add a $$$0$$$ or $$$1$$$ depends on whether $$$\frac{ia}{ib} \leq \frac{a}{b}$$$, so we can think about each stage of the process as partitioning the range $$$\frac{a}{b}$$$ must fall in to match the current prefix. Initially, every $$$\frac{a}{b}$$$ will match our prefix; after the first nontrivial step, we partition the possible ranges into $$$(0, 1)$$$ and $$$[1, \infty)$$$. After the next step, we find that the ranges are partitioned with respect to $$$1/2$$$ and $$$2$$$. More generally, it can be shown that after step $$$i$$$ of the process, the range containing values of $$$\frac{a}{b}$$$ matching the current prefix is partitioned with respect to any values of $$$\frac{ia}{ib}$$$ in the range for which $$$ia + ib = i$$$. If such a partition point lies in our range, then $$$\text{get_string}(ia, ib)$$$ gives the current prefix, so we increment the answer.

    For seven TCs, we can brute force using this observation, iterating over $$$ia + ib$$$ in increasing order and using e.g. binary search to check if there is a partition point within our current range.

    For thirteen TCs, we make a mathematical observation. Suppose our current range is $$$[w/x, y/z)$$$. It can be shown that the partition point with the smallest denominator lying in $$$(w/x, y/z)$$$ is $$$\frac{w+y}{x+z}$$$. (See here for related background; the section on mediants and binary search outlines essentially the same algorithm I'm describing here.) This is probably the least motivated observation of the problem; it was luckily familiar to me from math competitions.

    Hence, we can find the next point that will partition our range in $$$O(1)$$$. Note that we also need to factor in e.g. $$$2w/2x, 3w/3x,$$$ etc, if any such fractions have a smaller numerator/denominator sum than $$$\frac{w+y}{x+z}.$$$ This lets us compute our result in time proportional to the answer, which is fast enough to get the first thirteen cases.

    For full credit, rather than simulating one partition at a time, at each stage of this process, suppose WLOG that the next partition in the interior of $$$[w/x, y/z)$$$ will shift the right bound in (i.e., $$$a/b \in [w/x, (w+y)/(x+z))$$$). Then we binary search for how many operations in a row will shift the right bound in before the next operation moving the left bound and simulate all of those operations at once.

    This turns out to require $$$O(\log_{1.5} 4 \cdot 10^{18})$$$ binary searches. Indeed, we can show that $$$w+x+y+z$$$ is multiplied by a factor of at least $$$1.5$$$ with each operation; it can be proven that if we e.g. shift the right bound in while our left bound was shifted in as the last operation, then prior to the operation $$$w+x > y+z$$$, meaning that when we shift from $$$[w/x, y/z)$$$ to $$$[w/x, (w+y)/(x+z))$$$, the total sum of our numerators and denominators goes from $$$w+x+y+z$$$ to $$$w+x+(w+y)+(x+z)=2w+2x+y+z$$$, and because $$$w+x > y+z$$$, this is larger than $$$1.5(w+x+y+z).$$$ Because $$$w+x$$$ and $$$y+z$$$ are bounded above by $$$a+b$$$, the process must terminate before $$$w+x+y+z = 2a+2b \leq 4 \cdot 10^{18}$$$, giving the desired complexity bound.

    To intuitively understand why this approach leads to an improvement in our asymptotic complexity, note that the earlier solution TLEs on cases like $$$a = 10^{17} + 1, b = 10^{17}$$$. In this case, our ranges after partitioning will include $$$[1, \infty), [1, 2), [1, 3/2), [1, 4/3),$$$ and so on, i.e., we partition at $$$\frac{x+1}{x}$$$ for all $$$x$$$ up to a very large value. Using our mediant property, each new partition takes us from $$$[1, x/y)$$$ to $$$[1, (x+1)/(y+1))$$$, and we may have to increase $$$x$$$ and $$$y$$$ by $$$1$$$ many times before $$$x+y$$$ approaches $$$a+b$$$. The more efficient solution fixes this problem for reasons outlined in the complexity analysis: at each step, we are increasing the fraction whose numerator/denominator sum is smaller by the larger numerator/denominator sum, which makes the total numerator/denominator sum of the two fractions exponential rather than linear in the number of steps we've performed.

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

      Note that you can replace the binary search with a simple division: note that $$$(w + ky) / (x + kz) < a/b$$$ iff $$$bw + kby < ax + kaz$$$ iff $$$k (by - az) < (ax - bw)$$$, so $$$k$$$ is just the floor of the ratio of $$$ax - bw$$$ and $$$by - az$$$. (Here, you can start to see the connections to the Euclidean algorithm: these two "cross products" are exactly the residues in the Euclidean algorithm, and $$$w,x,y,z$$$ are the coefficients in the extended Euclidean algorithm.)

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

Why does it always take so long to see the results?

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

    There's a lot of manual work that needs to happen between end-of-contest and result-release, and it's mostly done exclusively by the contest director.

    I'm not privy to all of the details but things like the promotion thresholds require manual intervention. Submissions also get looked at to determine if new test cases need to be added (yes, that clause still exists) and that can't be automated either.

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

Does anyone know when camp emails get sent out? (Particularly asking for EGOI camp emails.) Is it mid-April? Or May? Or even...March?

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

    Historically, finalist emails have been sent in mid-late April (around the 15th-25th). (I'm not sure whether EGOI finalist emails are sent at the same time.)

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

Based on the difficulty, what do you guys think the cutoff will be for promotion from Silver to Gold for this contest?

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

Is there a bug in the problem "Milk Visits" of silver division? I'm getting wrong answer on test 2 while I get AC on big tests, also I saw that I have the same solution as the editorial so I'm a bit confused.

Thanks in advanced.

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

    Have you downloaded testcase from Usaco site and locally re-test your code?