NWERC 2019 - Codeforces

→ Pay attention

Before contest
Codeforces Round 986 (Div. 2)
09:33:03
Register now »

*has extra registration

→ Streams

Codeforces Round 986 (Div 2) - Solution Discussion

By Shayan

Before stream 11:38:02

View all →

→ Top rated

#	User	Rating
1	tourist	4009
2	jiangly	3821
3	Benq	3736
4	Radewoosh	3631
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3388
10	gamegame	3386

Countries | Cities | Organizations

View all →

→ Top contributors

#	User	Contrib.
1	cry	164
1	maomao90	164
3	Um_nik	163
4	atcoder_official	161
5	-is-this-fft-	158
6	awoo	157
7	adamant	156
8	TheScrasse	154
8	nor	154
10	Dominater069	153

View all →

→ Find user

→ Recent actions

Detailed →

mango_lassi's blog

NWERC 2019

By mango_lassi, history, 5 years ago, In English

The 2019 NWERC (Northwestern European regional contest) is tomorrow. You should see the scoreboard here once the contest starts.

There will be an online mirror here.

Let's discuss the problems after the contest!

#acmicpc2019, online mirror, acm icpc regional

mango_lassi
5 years ago
14

Comments (14)

Write comment?

pwild

5 years ago, # |

+13

The contest starts in 20 minutes, the online mirror starts in 50.

There will also be a live stream on ICPC Live

→ Reply

jcg

5 years ago, # |

+16

How to solve B, D, H, J and K?

→ Reply

mango_lassi

5 years ago, # ^ |

+11

J: Make a segment tree that tells us for every interval how many removals we need to make to make that interval of posts into a alternating sequence that starts with negative / positive and ends with negative/positive. Combining this information is trivial.

Initially each post must either be deleted or have the sign it initially has. Loop the amount of new accounts we create, when the number of accounts goes over $$$abs(votes_i)$$$, that position in the segment tree can now have any sign, so we update it. Every position gets updated at most once, and the segment tree operations work in $$$O(\log n)$$$, so that's our time complexity.

→ Reply

pwild

5 years ago, # ^ |

+21

D: For each edge count, find the shortest path with exactly this many edges when ignoring the constant x that is added to each edge. The actual length of such a path is then a line equation in terms of x. You then need to find all the lines which are minimal for at least one value (kind of like in the convex hull trick). Finally you need to find all the vertices which are on at least one of these paths.

→ Reply

pwild

5 years ago, # ^ |

+21

You can also see the solution presentation if you skip back in the live broadcast.

→ Reply

VladaMG98

5 years ago, # |

Did anybody manage to solve B?

→ Reply

Tutis

5 years ago, # ^ |

← Rev. 2 →

Idk if my solution is correct, but I did manage to squeeze it in 4s

solution

/*input
8 5
3
1
-1
5
7
5
3
7
*/
#pragma GCC optimize ("O3")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
const int mxh = 27;
vector<pair<int, int>> dp[505050][mxh];
vector<int>ch[505050];
int pa[505050];
int h[505050];
int sz[505050];
vector<pair<int, int>>suma( vector<pair<int, int>> & a,  vector<pair<int, int>> & b)
{
	if (a.empty() || b.empty())
		return {};
	vector<pair<int, int>>c;
	if (a.size() + b.size() >= 3)
	{
		return {{a[0].first + b[0].first, a.back().second + b.back().second}};
	}
	int x = 1e8;
	int y = -1;
	for (pair<int, int>i : a)
	{
		for (pair<int, int>j : b)
		{
			x = min(x, i.first + j.first);
			y = max(y, i.second + j.second);
		}
	}
	return {{x, y}};
	//sort(c.begin(), c.end());
	//return fix(c);
}
vector<pair<int, int>>pluss( vector<pair<int, int>> &a)
{
	vector<pair<int, int>>r;
	for (pair<int, int>i : a) {
		r.push_back({i.first + 1, i.second + 1});
	}
	return r;
}
void merge( vector<pair<int, int>> & a,
            vector<pair<int, int>> & b,
            vector<pair<int, int>> & c,
            vector<pair<int, int>> & r)
{
	if (a.size() + b.size() + c.size() >= 4)
	{
		int x = 1e8;
		int y = -1;
		if (!a.empty())
		{
			x = min(x, a[0].first);
			y = max(y, a.back().second);
		}
		if (!b.empty())
		{
			x = min(x, b[0].first);
			y = max(y, b.back().second);
		}
		if (!c.empty())
		{
			x = min(x, c[0].first);
			y = max(y, c.back().second);
		}
		r = {{x, y}};
		return;
	}
	r.clear();
	int i = 0;
	int j = 0;
	int k = 0;
	int d = -100;
	auto add = [&](pair<int, int>i)
	{
		if (i.first <= d)
		{
			r.back().second = max(r.back().second, i.second + 1);
		}
		else
		{
			r.push_back({i.first + 1, i.second + 1});
		}
		d = r.back().second;
	};
	while (i < a.size() && j < b.size() && k < c.size())
	{
		if (a[i] <= b[j])
		{
			if (a[i] <= c[k])
			{
				add(a[i++]);
			}
			else
			{
				add(c[k++]);
			}
		}
		else
		{
			if (b[j] <= c[k])
			{
				add(b[j++]);
			}
			else
			{
				add(c[k++]);
			}
		}
	}
	while (j < b.size() && k < c.size())
	{
		if (b[j] < c[k])
		{
			add(b[j++]);
		}
		else
		{
			add(c[k++]);
		}
	}
	while (i < a.size() && k < c.size())
	{
		if (a[i] < c[k])
		{
			add(a[i++]);
		}
		else
		{
			add(c[k++]);
		}
	}
	while (i < a.size() && j < b.size())
	{
		if (a[i] < b[j])
		{
			add(a[i++]);
		}
		else
		{
			add(b[j++]);
		}
	}
	while (i < a.size())
		add(a[i++]);
	while (j < b.size())
		add(b[j++]);
	while (k < c.size())
		add(c[k++]);
}
void prec(int v)
{
	sz[v] = 1;
	h[v] = 1;
	for (int w : ch[v])
	{
		prec(w);
		sz[v] += sz[w];
		h[v] = max(h[v], h[w] + 1);
	}
	dp[v][0] = {{0, 0}};
	dp[v][1] = {{1, 1}};
	if (ch[v].size() == 1)
	{
		dp[v][2] = {{2, 2}};
	}
	if (ch[v].size() == 2)
	{
		int &l = ch[v][0];
		int &r = ch[v][1];
		if (l > r)
			swap(l, r);
		for (int i = 2; i <= h[v]; i++)
		{
			auto v1 = suma(dp[l][i - 1], dp[r][i - 1]);
			auto v2 = suma(dp[l][i - 1], dp[r][i - 2]);
			auto v3 = suma(dp[l][i - 2], dp[r][i - 1]);
			merge(
			    v1, v2, v3, dp[v][i]
			);
		}
	}
}
int K[505050];
int NE[505050];
int n;
int k;
int r = 1;
void blogas(int i)
{
	if (NE[i])
		return;
	NE[i] = 1;
	for (int j : ch[i])
	{
		blogas(j);
	}
}
void check(int i)
{
	if (K[i] == 1 || NE[i] == 1)
		return;
	vector<int>nauji;
	vector<int>check;
	int j = i;
	while (j != -1)
	{
		if (K[j] == 0)
			nauji.push_back(j);
		check.push_back(j);
		j = pa[j];
	}
	for (int x : nauji)
	{
		K[x] = 1;
	}
	for (int v : check)
	{
		for (int i = 0; i < mxh; i++)
		{
			dp[v][i] = {};
		}
		if (ch[v].size() == 0)
		{
			dp[v][1] = {{1, 1}};
		}
		if (ch[v].size() == 1)
		{
			int w = ch[v][0];
			dp[v][1] = pluss(dp[w][0]);
			dp[v][2] = pluss(dp[w][1]);
		}
		if (ch[v].size() == 2)
		{
			int l = ch[v][0];
			int r = ch[v][1];
			auto v4 = suma(dp[l][0], dp[r][0]);
			dp[v][1] = pluss(v4);
			for (int i = 2; i <= h[v]; i++)
			{
				auto v1 = suma(dp[l][i - 1], dp[r][i - 1]);
				auto v2 = suma(dp[l][i - 1], dp[r][i - 2]);
				auto v3 = suma(dp[l][i - 2], dp[r][i - 1]);
				merge(
				    v1, v2, v3, dp[v][i]
				);
			}
		}
	}
	bool ok = false;
	for (int h = 0; h < mxh; h++)
		for (pair<int, int>a : dp[r][h])
			if (a.first <= k && k <= a.second)
				ok = true;
	if (ok)
		return;
	for (int x : nauji)
	{
		K[x] = 0;
	}
	for (int v : check)
	{
		for (int i = 0; i < mxh; i++)
		{
			dp[v][i] = {};
		}
		if (K[v] == 0)
		{
			dp[v][0] = {{0, 0}};
		}
		else
		{
			if (ch[v].size() == 0)
			{
				dp[v][1] = {{1, 1}};
			}
			if (ch[v].size() == 1)
			{
				int w = ch[v][0];
				dp[v][1] = pluss(dp[w][0]);
			}
			if (ch[v].size() == 2)
			{
				int l = ch[v][0];
				int r = ch[v][1];
				auto v4 = suma(dp[l][0], dp[r][0]);
				dp[v][1] = pluss(v4);
				for (int i = 2; i <= h[v]; i++)
				{
					auto v1 = suma(dp[l][i - 1], dp[r][i - 1]);
					auto v2 = suma(dp[l][i - 1], dp[r][i - 2]);
					auto v3 = suma(dp[l][i - 2], dp[r][i - 1]);
					merge(
					    v1, v2, v3, dp[v][i]
					);
				}
			}
		}
	}
	blogas(i);
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin >> n >> k;
	for (int i = 1; i <= n; i++)
	{
		cin >> pa[i];
		if (pa[i] == -1)
			r = i;
		else
			ch[pa[i]].push_back(i);
	}
	prec(r);
	for (int i = 1; i <= n; i++)
	{
		check(i);
	}
	for (int i = 1; i <= n; i++)
	{
		cout << "01"[K[i]];
	}
}

I maintained all possible subtree sizes with a specific height by a vector of intervals. To get lexicographically smallest subtree I just checked if a specific prefix is possible. This needs some nasty optimizations because in almost all cases dp value is just one interval, but not always. Can anyone find a counter test for my solution?

→ Reply

Benq

5 years ago, # ^ |

← Rev. 2 →

+18

I tried to write $$$O(n\log n)$$$ and got WA, but $$$O(n\log^2n)$$$ passes easily anyways. Designate a set of nodes such that none of them may be erased, and try adding nodes to this set in DFS order. After adding a node to the set, test whether the minimum possible size of a BBST containing all nodes in the set has size at most $$$k;$$$ if not, remove the node from the set.

Code

UPDATE: Here's $$$O(n\log n)$$$ (apparently it's slower tho lol)

Code

→ Reply

Philae

5 years ago, # ^ |

It's also possible in linear time.

→ Reply

allllekssssa

5 years ago, # |

+26

What did happen with Oxford team ? They had 5 harder before frozen, and currently they are not on the leaderboard.

→ Reply

kpw29

5 years ago, # ^ |

I'm not exactly sure, but they were not finals-eligible. Maybe they got disqualified

→ Reply

TimonKnigge

5 years ago, # ^ |

← Rev. 2 →

+18

→ Reply

Roundgod

5 years ago, # |

+24

Will this contest be put into gym/opentrains for virtual participation?

→ Reply

hex539

5 years ago, # ^ |

+10

In theory anyone can do it. The problem packages are available on the site: http://www.nwerc.eu/ -- most of the jury are travelling back from NWERC to our normal lives today. If nobody else has added the packages to Codeforces by the weekend, I can do it.

You can also find the questions on Kattis already because like usual they hosted the semilive contest for us: Problems from Northwestern Europe Regional Contest

→ Reply