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.

Does the contest have division promotion?

How do I register for it?

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

Thanks

:scare:

I will probably fail Gold again.

nah I believe in you!

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

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)

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

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

Very cool. Wish I had thought of that.

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

run multisource bfs from the input

print C — dist[~x]

genius sir.

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

Check last COCI editorial problem 2

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

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

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?

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

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.

try bessibessie maybe? correct : 10

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

CodeI 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`

Thank you.

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.

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

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

FormulaHow did I find itAfter implementing the brute force I immediately observed that:

2) and 3) implies that it would be a similar procedure as the Euclidean Algorithm. So I'm observing the value of $$$f(x,y)$$$ and $$$f(x,x+y)$$$. And I found that $$$f(x+y,x)=f(x,y)+1$$$ and $$$f(x,x+y)=f(x,y)+1$$$ is true for most of the times. So I implement the following procedure to print the answer at each step of the recursion:

If everything works fine then the difference of the answer at each step should be exactly $$$1$$$. But it turns out if $$$a>b$$$ but $$$a-b<b$$$, then the difference might be greater than $$$1$$$. After checking several more pairs of $$$(a, b)$$$ it seems that's the only case where our "guessed" formula got wrong. So I moved to observe the differences for the pairs $$$(a, b)$$$ and found $$$diff(x+k,x)$$$ has a beautiful pattern.

And by observing the pattern I found that $$$diff(x+k,x)=\left\lceil\frac{x}{k}\right\rceil-1$$$. And I claimed that's true and passed the first two subtasks. It's easy to optimize it by using a similar procedure in Eculidean algorithm. So it can be calculated in $$$O(\log(a)+\log(b))$$$

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

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.

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

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

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.

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

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

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

750

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.

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