### snarknews's blog

By snarknews, history, 13 months ago, translation,

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.

• +20

| Write comment?
 » 13 months ago, # |   0 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”.)
•  » » 13 months ago, # ^ | ← Rev. 2 →   +10 "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.
•  » » » 13 months ago, # ^ |   0 Thank you!
 » 13 months ago, # |   0 Can somebody share a link to the task analysis of the Belarus and Baltics Regional Contest?
 » 13 months ago, # |   +18 will there some tutorial for moscow contest?
 » 13 months ago, # |   +23 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.
 » 13 months ago, # | ← Rev. 3 →   +10 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 Problem and J. Journey in FogRegional 1. Belarus and Baltics 2021 — M. There could be your problem name and K. Split Circles
•  » » 13 months ago, # ^ |   +20 I'm not sure if the "0:00 Jan 15 2021" cutoff is accurate, as the virtual contests are running until Jan 17.
•  » » 12 months ago, # ^ |   +10 My py solution for MFor Belarus and Baltics 2021 — M. There could be your problem name you 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.
•  » » » 12 months ago, # ^ |   +10 I was able to find Russian editorials for 2 contests, but I don't understand Russian. :/
•  » » » » 12 months ago, # ^ |   0 Thank you very much!
•  » » 12 months ago, # ^ |   +10 I'm still interested in seeing a solution to 1% Euclidean, if anyone knows how to solve it.
•  » » » 12 months ago, # ^ | ← Rev. 2 →   +10 Pick $5\cdot 10^7$ random pairs of points, find average distance. I don't know why but it gets OK.
•  » » » 12 months ago, # ^ | ← Rev. 2 →   +51 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: $\int_{0}^{2\pi}\sqrt{(x_1-x_2)^2 + (y_1-y_2)^2} \mathrm d \theta = \int_0^{2\pi} |x_1 - x_2| \cdot |\cos(\theta)| \mathrm d\theta = 4 \cdot |x_1-x_2|$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)$. Code#include const int N = 1e6 + 500; struct pt { long double x, y; } p[N]; int n; long double x[N]; std::mt19937 s(std::chrono::steady_clock::now().time_since_epoch().count()); inline int rnd(int l, int r) { return std::uniform_int_distribution(l, r)(s); } template struct fast_io { char *p1, *p2, *q1, *q2, p[T], q[T]; fast_io() { p1 = p2 = p, q1 = q, q2 = q + T; } inline char gc() { return p1 == p2 && (p2 = (p1 = p) + fread(p, 1, T, stdin), p1 == p2) ? EOF : *p1++; } inline void pc(char ch) { if (q1 == q2) { fwrite(q, 1, T, stdout); q1 = q; } *q1++ = ch; } ~fast_io() { fwrite(q, 1, q1 - q, stdout); } }; fast_io<1024768> io; inline int read() { int res = 0, neg = 1; char ch; do { ch = io.gc(); if (ch == '-') neg = -1; } while (ch < 48 || ch > 57); do res = res * 10 + ch - 48, ch = io.gc(); while (ch >= 48 && ch <= 57); return res * neg; } const long double pi = acosl(-1.0L); int main() { std::ios::sync_with_stdio(false); n = read(); for (int i = 1; i <= n; ++i) { p[i].x = read(); p[i].y = read(); } if (n <= 4000) { double ans = .0; for (int i = 1; i <= n; ++i) { for (int j = i + 1; j <= n; ++j) { ans += std::sqrt((p[i].x - p[j].x) * (p[i].x - p[j].x) + (p[i].y - p[j].y) * (p[i].y - p[j].y)); } } printf("%.10f\n", ans); return 0; } long double ans = 0.0; const int Z = 11; for (int _ = 0; _ < Z; ++_) { long double theta = 2 * pi * _ / Z; long double s = std::sin(theta), c = std::cos(theta); for (int i = 1; i <= n; ++i) { x[i] = (p[i].x * c - p[i].y * s); } std::sort(x + 1, x + n + 1); long double sum = 0; for (int i = 1; i <= n; ++i) { ans += (i - 1) * x[i] - sum; sum += x[i]; } } printf("%.10Lf\n", ans / Z * pi / 2); } 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... Take 1.4*10^7 random pairs of points#include const int N = 1e6 + 500; struct pt { long double x, y; } p[N]; int n; long long x[N], y[N]; std::mt19937 s(std::chrono::steady_clock::now().time_since_epoch().count()); inline int rnd(int l, int r) { return std::uniform_int_distribution(l, r)(s); } template struct fast_io { char *p1, *p2, *q1, *q2, p[T], q[T]; fast_io() { p1 = p2 = p, q1 = q, q2 = q + T; } inline char gc() { return p1 == p2 && (p2 = (p1 = p) + fread(p, 1, T, stdin), p1 == p2) ? EOF : *p1++; } inline void pc(char ch) { if (q1 == q2) { fwrite(q, 1, T, stdout); q1 = q; } *q1++ = ch; } ~fast_io() { fwrite(q, 1, q1 - q, stdout); } }; fast_io<1024768> io; inline int read() { int res = 0, neg = 1; char ch; do { ch = io.gc(); if (ch == '-') neg = -1; } while (ch < 48 || ch > 57); do res = res * 10 + ch - 48, ch = io.gc(); while (ch >= 48 && ch <= 57); return res * neg; } int main() { std::ios::sync_with_stdio(false); time_t a=clock(); double ans = 0.0; n = read(); for (int i = 1; i <= n; ++i) { p[i].x = read(); p[i].y = read(); } std::shuffle(p + 1, p + n + 1, s); if (n <= 4000) { double ans = .0; for (int i = 1; i <= n; ++i) { for (int j = i + 1; j <= n; ++j) { ans += std::sqrt((p[i].x - p[j].x) * (p[i].x - p[j].x) + (p[i].y - p[j].y) * (p[i].y - p[j].y)); } } printf("%.10f\n", ans); } else { long long t = 1.4e7; for (int i = 1; i <= t; ++i) { int a = rnd(1, n); int b = rnd(1, n); if (a == b) { --i; continue; } ans += std::sqrt((p[a].x - p[b].x) * (p[a].x - p[b].x) + (p[a].y - p[b].y) * (p[a].y - p[b].y)); } long long u = 1ll * n * (n - 1) / 2; printf("%.10f\n", ans / t * u); fprintf(stderr, "used %.6fs", (clock()-a)*1.0/CLOCKS_PER_SEC); } } 
 » 13 months ago, # |   0 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.
•  » » 13 months ago, # ^ |   +10 Bump. Since Jan 17 10:00 Moscow Time is over. I hope it's fine to discuss problems now. Also are there any editorials?
•  » » » 13 months ago, # ^ |   +10 You just cannot wait eh :P
•  » » » » 13 months ago, # ^ |   +3 Sorry. Idk why I wrongly remembered that vc time on Yandex ended ~12 hrs ago. So I assumed thats Moscow time 10:00 .
 » 13 months ago, # |   0 Will there be any editorials?
 » 13 months ago, # |   +2 Hello! How to solve Baltic Stage F, H, M, N; Northwestern Russia Stage F, G, I, J; Baltic Stage B, C, K, L, O?
•  » » 13 months ago, # ^ | ← Rev. 2 →   +10 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 :)
•  » » 13 months ago, # ^ |   +20 Baltic HFirst, 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)$.
 » 13 months ago, # |   0 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.com/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?
•  » » 13 months ago, # ^ |   0 If Data Structure had only insert queries then finding maximum length segment is a known problem. hereMy soln was along the lines of Implicit Segment Tree (or similar things only) but it just uses std::set and std::map. SpoilerFirst 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_bound on A. Then --it we 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.
•  » » » 13 months ago, # ^ |   +20 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 :|)