Codeforces Round #540 (Div. 3) Editorial

#	User	Rating
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

#	User	Contrib.
1	cry	166
2	maomao90	163
2	Um_nik	163
4	atcoder_official	161
5	adamant	159
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	nor	153
9	Dominater069	153

Tutorial

Solution

#include <bits/stdc++.h>

using namespace std;

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	int q;
	cin >> q;
	
	for (int i = 0; i < q; ++i) {
		long long n;
		int a, b;
		cin >> n >> a >> b;
		cout << (n / 2) * min(2 * a, b) + (n % 2) * a << endl;
	}
	
	return 0;
}

1118B - Tanya and Candies

Idea: MikeMirzayanov

Tutorial

Solution

#include <bits/stdc++.h>

using namespace std;

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif

	int n;
	cin >> n;
	
	vector<int> a(n);
	
	int ePref = 0, oPref = 0, eSuf = 0, oSuf = 0;
	for (int i = 0; i < n; ++i) {
		cin >> a[i];
		if (i & 1) eSuf += a[i];
		else oSuf += a[i];
	}
	
	int ans = 0;
	for (int i = 0; i < n; ++i) {
		if (i & 1) eSuf -= a[i];
		else oSuf -= a[i];
		if (ePref + oSuf == oPref + eSuf) {
			++ans;
		}
		if (i & 1) ePref += a[i];
		else oPref += a[i];
	}
	
	cout << ans << endl;
	
	return 0;
}

1118C - Palindromic Matrix

Idea: MikeMirzayanov

I should mention this blog because it is amazing! This is a tutorial of this problem from MikeMirzayanov.

Tutorial

Solution

#include <bits/stdc++.h>

#define forn(i, n) for (int i = 0; i < int(n); i++)

using namespace std;

typedef pair<int, int> pt;

const int N = 1000 + 7;

int cnt[N];
int a[20][20];

int main() {
	int n;
	scanf("%d", &n);
	forn(i, n * n){
		int x;
		scanf("%d", &x);
		++cnt[x];
	}
	
	vector<pair<int, pt>> cells;
	forn(i, (n + 1) / 2) forn(j, (n + 1) / 2){
		if (i != n - i - 1 && j != n - j - 1)
			cells.push_back({4, {i, j}});
		else if ((i != n - i - 1) ^ (j != n - j - 1))
			cells.push_back({2, {i, j}});
		else
			cells.push_back({1, {i, j}});
	}
	
	for (auto cur : {4, 2, 1}){
		int lst = 1;
		for (auto it : cells){
			if (it.first != cur) continue;
			int i = it.second.first;
			int j = it.second.second;
			while (lst < N && cnt[lst] < cur)
				++lst;
			if (lst == N){
				puts("NO");
				return 0;
			}
			a[i][j] = a[n - i - 1][j] = a[i][n - j - 1] = a[n - i - 1][n - j - 1] = lst;
			cnt[lst] -= cur;
		}
	}
	
	puts("YES");
	forn(i, n){
		forn(j, n)
			printf("%d ", a[i][j]);
		puts("");
	}
	return 0;
}

1118D1 - Coffee and Coursework (Easy version)

Idea: MikeMirzayanov

Tutorial

Solution

#include <bits/stdc++.h>

using namespace std;

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	int n, m;
	cin >> n >> m;
	
	vector<int> a(n);
	for (int i = 0; i < n; ++i) {
		cin >> a[i];
	}
	sort(a.rbegin(), a.rend());
	
	for (int i = 1; i <= n; ++i) {
		int sum = 0;
		for (int j = 0; j < n; ++j) {
			sum += max(a[j] - j / i, 0);
		}
		if (sum >= m) {
			cout << i << endl;
			return 0;
		}
	}
	
	cout << -1 << endl;
	
	return 0;
}

1118D2 - Coffee and Coursework (Hard Version)

Idea: MikeMirzayanov

Tutorial

Solution

#include <bits/stdc++.h>

using namespace std;

int n, m;
vector<int> a;

bool can(int i) {
	long long sum = 0; // there can be a bug
	for (int j = 0; j < n; ++j) {
		sum += max(a[j] - j / i, 0);
	}
	return sum >= m;
}

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	cin >> n >> m;
	
	a = vector<int>(n);
	for (int i = 0; i < n; ++i) {
		cin >> a[i];
	}
	sort(a.rbegin(), a.rend());
	
	int l = 1, r = n;
	while (r - l > 1) {
		int mid = (l + r) >> 1;
		if (can(mid)) r = mid;
		else l = mid;
	}
	
	if (can(l)) cout << l << endl;
	else if (can(r)) cout << r << endl;
	else cout << -1 << endl;
	
	return 0;
}

1118E - Yet Another Ball Problem

Idea: MikeMirzayanov

Tutorial

Solution

#include <bits/stdc++.h>

using namespace std;

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	int n, k;
	cin >> n >> k;
	
	if (n > k * 1ll * (k - 1)) {
		cout << "NO" << endl;
	} else {
		cout << "YES" << endl;
		int cur = 0;
		for (int i = 0; i < n; ++i) {
			cur += (i % k == 0);
			cout << i % k + 1 << " " << (cur + i % k) % k + 1 << endl;
		}
	}
	
	return 0;
}

1118F1 - Tree Cutting (Easy Version)

Idea: MikeMirzayanov

Tutorial

Solution

#include <bits/stdc++.h>

#define forn(i, n) for (int i = 0; i < int(n); i++)

using namespace std;

const int N = 300 * 1000 + 13;

int n;
int a[N];
vector<int> g[N];
int red, blue;
int ans;

pair<int, int> dfs(int v, int p = -1){
	int r = (a[v] == 1), b = (a[v] == 2);
	for (auto u : g[v]) if (u != p){
		auto tmp = dfs(u, v);
		ans += (tmp.first == red && tmp.second == 0);
		ans += (tmp.first == 0 && tmp.second == blue);
		r += tmp.first;
		b += tmp.second;
	}
	return make_pair(r, b);
}

int main() {
	int n;
	scanf("%d", &n);
	
	forn(i, n){
		scanf("%d", &a[i]);
		red += (a[i] == 1);
		blue += (a[i] == 2);
	}
	
	forn(i, n - 1){
		int v, u;
		scanf("%d%d", &v, &u);
		--v, --u;
		g[v].push_back(u);
		g[u].push_back(v);
	}
	
	ans = 0;
	dfs(0);
	printf("%d\n", ans);
	return 0;
}

1118F2 - Tree Cutting (Hard Version)

Idea: MikeMirzayanov

Tutorial

Solution

#include <bits/stdc++.h>

#define forn(i, n) for (int i = 0; i < int(n); i++)

using namespace std;

const int N = 300 * 1000 + 13;
const int LOGN = 19;
const int MOD = 998244353;

int add(int a, int b){
	a += b;
	if (a >= MOD)
		a -= MOD;
	if (a < 0)
		a += MOD;
	return a;
}

int mul(int a, int b){
	return a * 1ll * b % MOD;
}

int a[N];
vector<int> g[N];
int up[N][LOGN];
int d[N];

void init(int v, int p = -1){
	for (auto u : g[v]) if (u != p){
		up[u][0] = v;
		for (int i = 1; i < LOGN; ++i)
			up[u][i] = up[up[u][i - 1]][i - 1];
		d[u] = d[v] + 1;
		init(u, v);
	}
}

int lca(int v, int u){
	if (d[v] < d[u]) swap(v, u);
	for (int i = LOGN - 1; i >= 0; --i)
		if (d[up[v][i]] >= d[u])
			v = up[v][i];
	if (v == u) return v;
	for (int i = LOGN - 1; i >= 0; --i)
		if (up[v][i] != up[u][i]){
			v = up[v][i];
			u = up[u][i];
		}
	return up[v][0];
}

int l[N];
int dp[N][2];

int dfs(int v, int p = -1){
	vector<pair<int, int>> cur;
	for (auto u : g[v]) if (u != p){
		int c = dfs(u, v);
		if (c != 0)
			cur.push_back(make_pair(c, u));
	}
	
	vector<int> vals;
	forn(i, cur.size()) if (cur[i].first > 0)
		vals.push_back(cur[i].first);
	
	sort(vals.begin(), vals.end());
	vals.resize(unique(vals.begin(), vals.end()) - vals.begin());
	
	if (int(vals.size()) > 1){
		puts("0");
		exit(0);
	}
	
	if (a[v] != 0 && !vals.empty() && vals[0] != a[v]){
		puts("0");
		exit(0);
	}
	
	if (a[v] == 0 && cur.empty())
		return 0;
	
	if (a[v] == 0 && vals.empty()){		
		vector<int> pr(1, 1), su(1, 1);
		forn(i, cur.size())
			pr.push_back(mul(pr.back(), add(dp[cur[i].second][0], dp[cur[i].second][1])));
		for (int i = int(cur.size()) - 1; i >= 0; --i)
			su.push_back(mul(su.back(), add(dp[cur[i].second][0], dp[cur[i].second][1])));
		reverse(su.begin(), su.end());
		dp[v][1] = 0;
		forn(i, cur.size())
			dp[v][1] = add(dp[v][1], mul(mul(pr[i], su[i + 1]), dp[cur[i].second][1]));
		dp[v][0] = add(dp[v][0], pr[cur.size()]);
		return -1;
	}
	
	dp[v][1] = 1;
	for (auto it : cur){
		if (it.first == -1)
			dp[v][1] = mul(dp[v][1], add(dp[it.second][0], dp[it.second][1]));	
		else
			dp[v][1] = mul(dp[v][1], dp[it.second][1]);
	}
	
	if (a[v] == 0)
		return vals[0];
	
	return (l[a[v]] == v ? -1 : a[v]);
}

int main() {
	int n, k;
	scanf("%d%d", &n, &k);
	
	forn(i, n)
		scanf("%d", &a[i]);
	
	forn(i, n - 1){
		int v, u;
		scanf("%d%d", &v, &u);
		--v, --u;
		g[v].push_back(u);
		g[u].push_back(v);
	}
	
	init(0);
	
	memset(l, -1, sizeof(l));
	forn(i, n) if (a[i] != 0)
		l[a[i]] = (l[a[i]] == -1 ? i : lca(l[a[i]], i));
	
	for (int i = 1; i <= k; ++i){
		if (a[l[i]] != 0 && a[l[i]] != i){
			puts("0");
			exit(0);
		}
		a[l[i]] = i;
	}
	
	dfs(0);
	
	printf("%d\n", dp[0][1]);
	return 0;
}

Comments (33)

Show archived | Write comment?

oknehcajd

6 years ago, # |

good contest!

→ Reply

DeerInForestovo

+12

nice!f2 is a interesting problem,and i learned a lot from it.

nilesh8757

What's the proof of optimality for D for given coffee distribution-strategy ? Is it just intuitive or we can prove it ?

nethish

6 years ago, # ^ |

← Rev. 2 →

Yes we can prove it.The approach is greedy. Consider the caffeine values 6 5 5 3 1 1 in order and consider the distribution for 2 days and in each day you are taking 3 cups.

6 + 5 + (5 — 1) + (3 — 1) + max(0, 1 — 2) + max(0, 1 — 2) = 17

If you consider this case 6 5 1 1 3 5 in order

6 + 5 + (1 — 1) + (1 — 1) + (3 — 2) + (5 — 2) = 15

This is because in the first case max(0, -1) + max(0, -1) hides subtracting 2 from the final output.

Sorry for my bad example.

onthefloor

+25

If you can bear some algebra then you can better appreciate the proof. ;)

So again let's sort it in decreasing order a₀ ≥ a₁ ≥ ... ≥ a_n - 1, and we consider the sum $\text{[math]}$ . Now there exists an m such that this sum is equal to $\text{[math]}$ : $\text{[math]}$ is strictly decreasing as i increases. In other words we can 'assume' that a₀ through a_m - 1 are strictly greater than $\text{[math]}$ , and the rest at most $\text{[math]}$ .

To show that this is optimally, let b₀, ... , b_n - 1 be a permutation of these a_i's, and since we spread it over k days, at most k of the coffee cups are the first of the days (hence 0 penalty), at most k of them has penalty 1, and so on. Hence the sum is now at most $\text{[math]}$ . Choosing only those i's that are relevant, we see that this sum is also equal to $\text{[math]}$ .

Now if p is the number of those i's satisfying $\text{[math]}$ , we can split the sum $\text{[math]}$ into two categories: the b_i's contain at most m integers from a₀, ... , a_m - 1 and the rest are not more than $\text{[math]}$ ; so $\text{[math]}$ . On the other hand, the sum $\text{[math]}$ (considering only those i's that are relevant) at at least $\text{[math]}$ so $\text{[math]}$

$\text{[math]}$

$\text{[math]}$ , as desired.

Amazing! That's what I was looking for. Thanks.

Anonymous

Rahul

+24

E has another simple solution.
Traverse all pairs in increasing order (starting from (1, 2), (1, 3), ...) and print each pair followed by its flipped pair (not repeating any).

sdssudhu

Yeah I also used the same strategy.

Leonardo_Paes

i used this too, nice!

← Rev. 3 →

There is another solution where in we could start with say pair (1,2) and keep incrementing both the elements of the pair until the second element of the pair reaches k.

After that, we flip the pair and keep decrementing both x and y until y becomes 1. Repeat this process and we get the correct answer.

anupamshah_

Yeah ! It is the simplest approach.

samarth1402

Can someone please explain me the tutorial of F1.

It would be of great help.

arpit040199

I solved it in following steps:

Suppose root of the tree is 1.
Then by single dfs we find how many red and blue vertices are present in subtree of each vertex.
Then we see each parent to child edge, if child's subtree contains 0 blue vertices and all red vertices(or 0 red vertices and all blue vertices) then this edge is good.

priyanshu_98

+10

I think this contest have much tricky questions then previous div3 contest.

....................

-31

the contest was terrible and now seeing from this editorial you really didn't care about us. it's a joke, especially problem D. i'm at a loss of words trying to explain myself why you keep mixing math with programming. what connection do you see between the two? genuinely

amitnsky

In Problem B for n=1 ans should be 0, bcoz if there is only one candy, tanya will give that's one to his father, since now there is no candy she could not eat any day.(There is no candy). Shouldn't it be 0 ? (My soln got hacked just due to only this case which i made myself ans = 0 if n==1) :(

TheOneYouWant

No, because if dad eats the 1-th candy, sum of weights of candies Tanya eats in even days = sum of weights of candies Tanya eats in odd days = 0.

mdallrosa

i've learned a lot from this contest, specially that i must read the entire problem set.

divman78

Can someone suggest some other approach for F2. Thanks.

m4h

Hi, my solution is still similar to the editorial but maybe it can help.
I first run a DFS to do a minimal merge of the components of the same color: I colorize the entire path between each vertex of color, and check for collisions. You only have to keep a count of number of components per color to know if the child has to give its color to his parent.
Then instead of counting the ways of cutting, i count the number of valid colorings, where a color for a node is either "in subtree" or "not in subT". Then for the second DFS I just compute the possibilities for these two "colors". The formulas are similar to editorial.
Solution in O(n log mod) runs in 0.5s, because I took modular inverse to obtain the product of "all but one".
Hope it helps, my code here: 50352250

mikimowski

Could You explain how counting works? I haven't really understood it from the tutorial. Although I understand all the rest.

Either you already have made # of colors in subtree cuts in this subtree or you have made this number minus one. In my case corresponds to "is this node color in the subree?". You can think of DP0 as "am i done here? = has color of parent" so naturally you can keep a color and get from color of child to color of parent but not the converse. Then like classical tree DP you sum possibilities of disjoint events (like choosing one children color) and multiply the ones for independent events (like choosing a color for each subtree). This is not an easy DP pb because you have to keep track of both. Try to get the intuition behind the formulae before looking at tricks for computing it faster.

Okey, I think I am starting to understand it now. One more question. How do we know in our dp that we cut exactly k-1 times? No more no less?

I will try solving some easier problems with tags (trees, combinatorics) and then come back to this one. Thanks

1: you checked there were no collisions during the minimal merging
2: at each cut your separating the "top" color from the "bottom" one, the components stay connected. When you already cut it, a color disappears from the possibilities (DP1->DP0) and becomes a color not in subtree. DP0 means we are done w/ all colors of subtree, DP1 there is one left at the root of subtree.
3: Since you want the root node to have a color from its subtree, you return DP1. Each color except this one has been cut -> K-1.

ahmed_drawy

can anybody take a look to my post here

and help me to optimize my dp solution for the D1 to solve D2

thanks in advance

Its painful to read code of other people sometimes. Let me know if you haven't understood from editorial.

I can’t figure out the counting part. Logic behind dp[v][1] and dp[v][0]

AaronSwartz

1118D1 — Coffee and Coursework (Easy version)

Let the current number of days be k. The best way to distribute first cups of coffee for each day is to take k maximums in the array

How do you know that it's the best way to distribute? I don't get that

skyscraper

5 years ago, # ^ |

Checking on samples and doing some casework and observations, It is better to use maximum values initially because they may get depleted later on.

saquib2508

5 years ago, # |

Need help with the problem F2. What I've done is-

For every color, tried to build $$$k$$$ same-colored subtrees. If not possible (collision occurs), the answer is trivially $$$0$$$.
For simplicity, let's call uncolored vertices as black vertices. When an answer exists, there will be many (possibly $$$0$$$) subtrees induced by black vertices, whose leaves will have many colored components(sub-trees) adjacent to them. Let's call the set of these colored component/sub-trees $$$S_T$$$ and the black components $$$B_T$$$. Instead of cutting $$$k-1$$$ edges, I tried to color the black vertices in a way such that:

a. only the trees in $$$S_T$$$ get larger

b. no new subtrees form.

c. all the vertices get colored.

Clearly, doing step 2 for all the black sub-trees in $$$B_T$$$ will lead us to the result. The answer will be the product of $$$count(coloring_.a_.black_.component_.in_.B_T)$$$. So, all I need is to find a way to count the colorings of $$$1$$$ black component. It should be an easy DP but somehow I'm failing to grasp it. The tutorial did not help (sorry). Any help is welcome. Thanks.

Oom9

The way Mike has explained F2 is remarkable. Thanks Mike and Vovuh.

__LAKSHAY__

8 months ago, # |

For problem F2 I have an approach. However I am stuck at some part Please read this blog for my approach. Note: For good coders you will find one more interesting problem to solve.

vovuh's blog