Three Regionals Cup-2021

→ Pay attention

Before contest
Rayan Programming Contest 2024 - Selection (Codeforces Round, Div. 1 + Div. 2)
6 days
Register now »

*has extra registration

→ Top rated

#	User	Rating
1	tourist	3993
2	jiangly	3743
3	orzdevinwang	3707
4	Radewoosh	3627
5	jqdai0815	3620
6	Benq	3564
7	Kevin114514	3443
8	ksun48	3434
9	Rewinding	3397
10	Um_nik	3396

Countries | Cities | Organizations

View all →

→ Top contributors

#	User	Contrib.
1	cry	167
2	Um_nik	163
3	maomao90	162
3	atcoder_official	162
5	adamant	159
6	-is-this-fft-	158
7	awoo	156
8	TheScrasse	154
9	Dominater069	153
9	nor	153

View all →

→ Find user

→ Recent actions

Detailed →

snarknews's blog

Three Regionals Cup-2021

By snarknews, history, 3 years ago, translation, In English

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.

three regionals cup, nerc regionals

snarknews
3 years ago
26

Comments (25)

Show archived | Write comment?

Rubikun

3 years ago, # |

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

→ Reply

snarknews

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

→ Reply

Rubikun

3 years ago, # ^ |

Thank you!

→ Reply

Fortitude

3 years ago, # |

Can somebody share a link to the task analysis of the Belarus and Baltics Regional Contest?

→ Reply

fufufafa

3 years ago, # |

+18

will there some tutorial for moscow contest?

→ Reply

YaoBIG

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

→ Reply

aryanc403

3 years 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. Treeshop
Regional 2. Northwestern Russia 2021 — E. Extreme Problem and J. Journey in Fog
Regional 1. Belarus and Baltics 2021 — M. There could be your problem name and K. Split Circles

→ Reply

gojira

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

→ Reply

Rhodoks

3 years ago, # ^ |

+10

My py solution for M

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

→ Reply

aryanc403

3 years ago, # ^ |

+10

I was able to find Russian editorials for 2 contests, but I don't understand Russian. :/

Moscow Regional North-Western Russia Regional

→ Reply

Rhodoks

3 years ago, # ^ |

Thank you very much!

→ Reply

mango_lassi

3 years ago, # ^ |

+10

I'm still interested in seeing a solution to 1% Euclidean, if anyone knows how to solve it.

→ Reply

greencis

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

→ Reply

Qingyu

3 years 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 <bits/stdc++.h>

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<int>(l, r)(s);
}

template <int T>
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 <bits/stdc++.h>

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<int>(l, r)(s);
}

template <int T>
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);
	}
}

→ Reply

snarknews

3 years ago, # |

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.

→ Reply

aryanc403

3 years 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?

→ Reply

gojira

3 years ago, # ^ |

+10

You just cannot wait eh :P

→ Reply

aryanc403

3 years ago, # ^ |

Sorry. Idk why I wrongly remembered that vc time on Yandex ended ~12 hrs ago. So I assumed thats Moscow time 10:00 .

→ Reply

_runtimeTerror_

3 years ago, # |

Will there be any editorials?

→ Reply

wyhtxdy

3 years ago, # |

Hello! How to solve Baltic Stage F, H, M, N; Northwestern Russia Stage F, G, I, J; Baltic Stage B, C, K, L, O?

→ Reply

gojira

3 years 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 :)

→ Reply

aryanc403

3 years ago, # ^ |

+20

Baltic H

→ Reply

gojira

3 years ago, # |

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.net/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?

→ Reply

aryanc403

3 years ago, # ^ |

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.

Spoiler

→ Reply

gojira

3 years 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 :|)

→ Reply