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

nah I believe in you!

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

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

run multisource bfs from the input

print C — dist[~x]

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

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

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.

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.

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.

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

750

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