Three Regionals Cup — 2021 on the tasks of Moscow Regionals 2021, Belarus and Baltic Regionals 2021, and Northwestern Russia Regionals 2021 is traditionally running at the Yandex.Contest platform in the format of three virtual contests. On the cup page, you may register for those contests.
You may use the plain Yandex logins or OpenCup or other pre-generated logins (choose the appropriate link at the top of the page).
The regionals results will be included in the cup standings. The result of the Cup is the sum of the Grand Prix 100 (similar to Opencup) scores for all three regionals at 0:00 Jan 15 2021.
Do you have any plans to use the problem set in opencup or other places?
If not, I'd like to participate in the contest. (I'm worried because there is a button that says "opencup login”.)
"Opencup login" link is the way to login using the pre-generated logins (for example, for Opencup, MW camp etc), so if you (or your team) prefer to use this type of login instead of personal credentials of Yandex, the "opencup login" link shall be used.
The contests are already in use on Three Regionals Cup, so they will not be used at Opencup etc.
Thank you!
Can somebody share a link to the task analysis of the Belarus and Baltics Regional Contest?
will there some tutorial for moscow contest?
Thank you for these three wonderful contests!
By the way I want to ask whether we can still virtually participate these contests after Jan 15th or not? I am not sure if they are only available by Jan 15th or only the scores are only counted by Jan 15th.
Thanks for the beautiful contests. We really had fun solving them. Are there any editorials?
Since Jan 15, 2021, 0:00 (Moscow time) is over. I hope it's fine to discuss the problems now.
Anyways, how to solve -
Regional 3. Moscow 2021 —
I. 1%-Euclidean,K. Efficient Interception,O. TreeshopRegional 2. Northwestern Russia 2021 —
E. Extreme ProblemandJ. Journey in FogRegional 1. Belarus and Baltics 2021 —
M. There could be your problem nameandK. Split CirclesI'm not sure if the "0:00 Jan 15 2021" cutoff is accurate, as the virtual contests are running until Jan 17.
My py solution for M
For
Belarus and Baltics 2021 — M. There could be your problem nameyou can refer to this similar problem. My comment explains a solution with $$$O(|n|^3)$$$ complexity.Also, ftiasch reduces the complexity to $$$O(|n|^2)$$$ by amortizing the big integer calculation. She used this problem with $$$|n|=5000$$$ in CCPC Final 2020.
At last, if you have gotten official editorials, could you share them with me? Or we can share solutions with each other.
I was able to find Russian editorials for 2 contests, but I don't understand Russian. :/
Moscow Regional North-Western Russia Regional
Thank you very much!
I'm still interested in seeing a solution to 1% Euclidean, if anyone knows how to solve it.
Pick $$$5\cdot 10^7$$$ random pairs of points, find average distance. I don't know why but it gets OK.
In fact, this task was discussed in an olympiad training camp in Shandong, China last year, but I didn't know how it was done until recently.
First, this problem can be easily solved in $$$O(n \log n)$$$ if all points satisfy $$$y_i = 0$$$. The answer will be $$$\sum_{1 \leq i < j \leq n} |x_i - x_j|$$$.
Note that for any two points $$$(x_1,y_1)$$$ and $$$(x_2,y_2)$$$, the distance of these two points $$$\sqrt{(x_1-x_2)^2 + (y_1-y_2)^2} = |x_1 - x_2| \cdot |\cos(\theta)|$$$, then we have:
Let $$$f(\theta)$$$ denote the value of $$$\sum_{1 \leq i < j \leq n} |x_i-x_j|$$$ after rotating all points counterclockwise by $$$\theta$$$. Then the answer is just $$$4 \cdot \int_0^{2\pi} f(\theta) \mathrm d\theta$$$. If we take $$$T$$$ values $$$\xi_i = \frac{i}{T} \cdot 2\pi$$$ and use $$$\frac{1}{2\pi T} \sum_{i=0}^{T-1} f(\xi_i)$$$ to estimate the value of the integral above, then the error is $$$O(T^{-2})$$$ which is acceptable for $$$T =\frac{1}{\sqrt \varepsilon}$$$. The time complexity is $$$O\left(\frac{n \log n}{\sqrt{\varepsilon}}\right)$$$.
By the way, it seems the test cases are really weak. It can be passed by taking about $$$10^7$$$ random pairs of points and using the average distance to estimate the answer...
Several teams asked to allow to run the contests at the current weekend, so the deadline is moved forward to Jan 17 10:00 Moscow Time.
Bump. Since Jan 17 10:00 Moscow Time is over. I hope it's fine to discuss problems now. Also are there any editorials?
You just cannot wait eh :P
Sorry. Idk why I wrongly remembered that vc time on Yandex ended ~12 hrs ago. So I assumed thats Moscow time 10:00 .
Will there be any editorials?
Hello! How to solve Baltic Stage F, H, M, N; Northwestern Russia Stage F, G, I, J; Baltic Stage B, C, K, L, O?
I only happened to solve Moscow L (which I assume you're asking about since you said "Baltic" twice?), and the answer for that might be frustrating... Maximum Flow :)
First, crucial observation is - Let $$$p$$$ be the probability that the sum of the first $$$n$$$ nos is equal to the sum of the last $$$n$$$ nos. Then answer is $$$(1-p)/2$$$, we will calculate $$$p$$$ now.
The second crucial observation is - Lets generate $$$n$$$ nos in range $$$[0,2*L]$$$ and last $$$n$$$ nos in range $$$[-2*L,0]$$$ (basically generate $$$-a_i$$$ instead of $$$a_i$$$)
Now, all we need is sum of these $$$2*n$$$ nos should be $$$0$$$.
After this, it's Generating Functions math to calculate this using binomial coefficient. I will just state in formal math notations.
No of ways to generate $$$n$$$ nos in the range $$$[0,2*L]$$$ which sum upto $$$S$$$ is coefficient of $$$X^S$$$ in $$$(1+x+...+x^{2*L-1}+x^{2*L})^n$$$
Similar for another half $$$(1+x^{-1}+...+x^{-2*L+1}+x^{-2*L})^n$$$ = $$$x^{-2*n*L}*(1+x+...+x^{2*L-1}+x^{2*L})^n$$$
To find sum zero is coefficient of $$$x^0$$$ in $$$(1+x+...+x^{2*L-1}+x^{2*L})^n * x^{-2*n*L}*(1+x+...+x^{2*L-1}+x^{2*L})^n = x^{-2*n*L}*(1+x+...+x^{2*L-1}+x^{2*L})^{2*n}$$$
which is equal to coefficient of $$$x^{2*n*L}$$$ in $$$(1+x+...+x^{2*L-1}+x^{2*L})^{2*n}$$$
$$$(1+x+...+x^{2*L-1}+x^{2*L})^{2*n}$$$ = $$$(1-x^{2*L+1})^{2*n}/(1-x)^{2*n}$$$ = $$$(1-x^{2*L+1})^{2*n}*(1-x)^{-2*n}$$$
First-term has only $$$2*n+1$$$ distinct terms with non zero coefficients and those are binomial coefficients as well. Coefficient of $$$x^i$$$ in $$$(1-x)^{-2n}$$$ is a well known binomial coefficient.
You can precalculate all factorials and their inverses to calculate those $$$C(i,j)$$$ in $$$O(1)$$$. You will have to precalculate $$$O(2*n*L)$$$ factorials and their inverses and the rest part can be done in $$$O(n)$$$.
How do you y'all solve Northwest Russia problem D (Day Streak)? Are you using Implicit Segment Tree (that I just happened to read about in https://codeforces.me/blog/entry/99074), or some other data structure?
During the contest, I tried implementing something that would track the set of non-overlapping intervals, and recalculate them in logarithmic time when a problem moves across timezones, but I quickly got bogged down in details (e.g., did an interval break up? did two intervals merge? etc.). Is there a known data structure that maintains the data in this fashion?
If Data Structure had only insert queries then finding maximum length segment is a known problem. here
My soln was along the lines of Implicit Segment Tree (or similar things only) but it just uses std::set and std::map.
First we should only check on O(n) timezones.
The problem can be restated as -
1. Given a multiset s, find the length of the longest continuous range on it.
2. Remove x from s and add x+1 to s. Each element in the original set would be updated atmax once.
Lets create a new set T, $$$x \in T \iff$$$ there exists $$$y \in S$$$ such that
abs(x-y)<=2The thing I did over here was to maintain a set $$$A = T - S$$$, then we can always query for smaller non-existent value > x ($$$x \in S$$$) in S using
lower_boundon A. Then--itwe can also find largest non-extent value <= x ($$$x \in S$$$)After batch updates, we can just check the updated values to find the length of the longest interval they belong to. Update final answer if it changes.
You can look at my submission for more implementation details.
I see, always removing an interval before adding it seems to eliminate a lot of complexity. Neat trick!
(That said, C++ has more palatable map interface for this than Java's TreeSet provides, so I think overall I'll stick with implicit segment trees over TreeSet implementation :|)