XXII Open Cup, Grand Prix of Xi'an

→ Обратите внимание

До соревнования
Codeforces Round 941 (Div. 1)
3 дня
Зарегистрироваться »

*есть доп. регистрация

До соревнования
Codeforces Round 941 (Div. 2)
3 дня
Зарегистрироваться »

*есть доп. регистрация

→ Лидеры (рейтинг)

№	Пользователь	Рейтинг
1	ecnerwala	3649
2	Benq	3581
3	orzdevinwang	3570
4	Geothermal	3569
4	cnnfls_csy	3569
6	tourist	3565
7	maroonrk	3531
8	Radewoosh	3521
9	Um_nik	3482
10	jiangly	3468

Страны | Города | Организации

Всё →

→ Лидеры (вклад)

№	Пользователь	Вклад
1	maomao90	174
2	awoo	164
3	adamant	162
4	TheScrasse	159
5	nor	158
6	maroonrk	156
7	-is-this-fft-	151
8	SecondThread	147
9	orz	146
10	pajenegod	145

Всё →

→ Найти пользователя

→ Прямой эфир

Детальнее →

Блог пользователя Qingyu

XXII Open Cup, Grand Prix of Xi'an

Автор Qingyu, история, 3 года назад, По-английски

Could not find an official announcement, let's discuss problems here.

Обсуждение 2020-2021 Summer Petrozavodsk Camp, Day 6: XJTU Contest (XXII Open Cup, Grand Prix of XiAn)

+133

Qingyu
3 года назад
11

Комментарии (11)

Написать комментарий?

moscow01

3 года назад, # |

← Rev. 2 →

+14

How to solve Div.2 M(Colors and Pearls) and P(Number Sequence)?

→ Ответить

Qingyu

3 года назад, # ^ |

+49

It looks like the problems for Div.2 were taken from some past ICPC Asia online contests...

M: A brute force solution is to denote $$$f_n$$$ as the answer for $$$a_{1} \cdots a_n$$$, then $$$f_n = \min_{0 \leq i < n} (f_i+v^2(i,n))$$$. Note that $$$f_n \leq n$$$, so we only need to keep the states that satisfy $$$v(i,n)\leq \sqrt n$$$. Time complexity is $$$\Theta(n \sqrt n)$$$.

Code

#include <bits/stdc++.h>

using namespace std;

const int N = 2e5 + 50;

int a[N], dp[N], f[N], g[N], lst[N];

int main()
{
	int n;
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	while (cin >> n)
	{
		for (int i = 1; i <= n; ++i) cin >> a[i];
		for (int i = 1; i <= n; ++i)
		{
			lst[i] = g[a[i]];
			g[a[i]] = i;
		}
		int tot = 0;
		memset(dp, 0x3f, n + 1 << 2);
		memset(f, 0, n + 1 << 2);
		memset(g, 0, n + 1 << 2);
		dp[0] = 0;
		for (int i = 1; i <= n; ++i)
		{
			int cnt = 0;
			g[++cnt] = i;
			for (int k = 1; k <= tot; ++k)
				if (a[f[k]] != a[i])
					g[++cnt] = f[k];
			for (int i = 1; i <= cnt; ++i) f[i] = g[i]; 
			tot = cnt;
			tot = std::min(tot, (int)sqrt(i) + 1);
			for (int k = 1; k <= tot; ++k)
				dp[i] = std::min(1ll * dp[i], dp[f[k + 1]] + 1ll * k * k);
		}
		printf("%d\n", dp[n]);
	}
}

N: For a pile of stones, we have $$$\mathcal G_n = \operatorname{mex}_{i+j<n} ( \mathcal G_i, \mathcal G_{i} \stackrel{*}{+} G_j )$$$, and you can proof $$$\mathcal G_n = *_n$$$ by induction. So the whole game is equivalent to the regular Nim game.

Code

#include <bits/stdc++.h>

using namespace std;

int main()
{
	int T, n;
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	while ((cin >> n))
	{
		int sum = 0, x;
		while (n--) { cin >> x; sum ^= x; }
		puts(sum ? "Win" : "Lose");
	}
}

O is just a simple breadth first search problem.

P: We can make each $$$a_i\oplus b_i$$$ become $$$(111\cdots 1)_2$$$ by greedily pairing. This is obviously the optimal answer.

Code

#include <bits/stdc++.h>

const int N = 1e5 + 50;
int a[N], b[N], n;
long long s, o, tot;

int main()
{
	while (~scanf("%d", &n))
	{
		s = 0;
		memset(b, -1, sizeof b);
		for (int i = 0; i <= n; ++i)
			scanf("%d", a + i);
		for (int i = n; i >= 0; --i)
			if (b[i] == -1)
			{
				tot = 1;
				while (tot <= i) tot <<= 1;
				tot--;
				o = tot ^ i;
				s += tot * 2;
				b[i] = o;
				b[o] = i;
			}
		printf("%lld\n", s);
		for (int i = 0; i <= n; ++i)
			printf(i == n ? "%d\n" : "%d ", b[a[i]]);
	}
	return 0;
}

→ Ответить

nor

3 года назад, # |

+19

Thanks to the problemsetters, the problems were really nice (D in particular). How to solve C, G, J and K?

→ Ответить

Qingyu

3 года назад, # ^ |

+65

There's an editorial prepared by the problemsetters.

→ Ответить

DrSwad

3 года назад, # ^ |

← Rev. 2 →

+10

I had been looking for the editorial since the end of the contest, but couldn't seem to find it anywhere. Do you mind sharing how you found it? Most of the previous GP editorials were usually posted in the respective CF announcements, but this one doesn't seem to have any official announcement post.

Thanks for sharing the editorial btw.

→ Ответить

Qingyu

3 года назад, # ^ |

+26

Well... In fact, the contest was used in Petrozavodsk Camp, and it was shared by the problemsetters during the camp.

→ Ответить

MiceMirzayanov

3 года назад, # ^ |

-75

baaki sab ban gaya bhai?

→ Ответить

18o3

3 года назад, # ^ |

Tere ban gaye kya?

→ Ответить

hos.lyric

3 года назад, # |

+36

Thanks to problem F! I learned something new.

Here is a tricky case not in the judge tests (it's OK as I know it's not easy to create a strong cases):

1
10 9 100 3 -63 4

We have $$$E = \{ (3,1), (6,2), (9,3), (12,4), (15,5) \}$$$ and the answer should be 701423582.

My first attempt used quadtree-like DFS but I only checked the center of the ellipse and the boundary lattice points of the square to decide that they have any intersection. It is not correct for thin ellipses.

→ Ответить