Codeforces Round #544 (Div. 3) Editorial

#	User	Rating
1	tourist	4009
2	jiangly	3831
3	Radewoosh	3646
4	jqdai0815	3620
4	Benq	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	gamegame	3386
10	ksun48	3373

#	User	Contrib.
1	cry	164
1	maomao90	164
3	Um_nik	163
4	atcoder_official	160
5	-is-this-fft-	158
6	awoo	157
7	adamant	156
8	TheScrasse	154
8	nor	154
10	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 h1, m1;
	scanf("%d:%d", &h1, &m1);
	int h2, m2;
	scanf("%d:%d", &h2, &m2);
	int t1 = h1 * 60 + m1;
	int t2 = h2 * 60 + m2;
	int t3 = (t1 + t2) / 2;
	printf("%02d:%02d\n", t3 / 60, t3 % 60);
	
	return 0;
}

1133B - Preparation for International Women's Day

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;
	vector<int> cnt(k);
	for (int i = 0; i < n; ++i) {
		int x;
		cin >> x;
		++cnt[x % k];
	}
	int ans = cnt[0] / 2;
	if (k % 2 == 0) ans += cnt[k / 2] / 2;
	for (int i = 1; i < (k + 1) / 2; ++i) {
		int j = k - i;
		ans += min(cnt[i], cnt[j]);
	}
	
	cout << ans * 2 << endl;
	
	return 0;
}

1133C - Balanced Team

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);
	for (int i = 0; i < n; ++i) {
		cin >> a[i];
	}
	sort(a.begin(), a.end());
	int ans = 0;
	int j = 0;
	for (int i = 0; i < n; ++i) {
		while (j < n && a[j] - a[i] <= 5) {
			++j;
			ans = max(ans, j - i);
		}
	}
	
	cout << ans << endl;
	
	return 0;
}

1133D - Zero Quantity Maximization

Idea: BledDest

Tutorial

Solution

#include<bits/stdc++.h>

using namespace std;

#define x first
#define y second

const int N = 200043;

void norm(pair<int, int>& p)
{
	if(p.x < 0)
	{
		p.x *= -1;
		p.y *= -1;
	}
	else if (p.x == 0 && p.y < 0)
	{
		p.y *= -1;
	}
	int d = __gcd(abs(p.x), abs(p.y));
	p.x /= d;
	p.y /= d;
}

map<pair<int, int>, int> m;

int a[N];
int b[N];
int n;

int main()
{
	scanf("%d", &n);
	for(int i = 0; i < n; i++)
		scanf("%d", &a[i]);
	for(int i = 0; i < n; i++)
		scanf("%d", &b[i]);
	int ans = 0;
	int cnt0 = 0;
	for(int i = 0; i < n; i++)
	{
		if(a[i] == 0)
		{
			if(b[i] == 0)
				cnt0++;
		}
		else
		{
			pair<int, int> p = make_pair(-b[i], a[i]);
			norm(p);
			m[p]++;
			ans = max(ans, m[p]);
		}
	}
	cout << cnt0 + ans << endl;
}

1133E - K Balanced Teams

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;
	vector<int> a(n);
	for (int i = 0; i < n; ++i) {
		cin >> a[i];
	}
	sort(a.begin(), a.end());
	vector<int> cnt(n);
	for (int i = 0; i < n; ++i) {
		while (i + cnt[i] < n && a[i + cnt[i]] - a[i] <= 5) {
			++cnt[i];
		}
	}
	
	vector<vector<int>> dp(n + 1, vector<int>(k + 1));
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j <= k; ++j) {
			dp[i + 1][j] = max(dp[i + 1][j], dp[i][j]);
			if (j + 1 <= k) {
				dp[i + cnt[i]][j + 1] = max(dp[i + cnt[i]][j + 1], dp[i][j] + cnt[i]);
			}
		}
	}
	
	cout << dp[n][k] << endl;
	
	return 0;
}

1133F1 - Spanning Tree with Maximum Degree

Idea: MikeMirzayanov

Tutorial

Solution

#include <bits/stdc++.h>

using namespace std;

int n, m;
vector<vector<int>> g;
vector<int> deg, used;
vector<pair<int, int>> ans;

mt19937 rnd(time(NULL));

void bfs(int s) {
	used = vector<int>(n);
	used[s] = 1;
	queue<int> q;
	q.push(s);
	
	while (!q.empty()) {
		int v = q.front();
		q.pop();
		for (auto to : g[v]) {
			if (used[to]) continue;
			if (rnd() & 1) ans.push_back(make_pair(v, to));
			else ans.push_back(make_pair(to, v));
			used[to] = 1;
			q.push(to);
		}
	}
}

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	cin >> n >> m;
	g = vector<vector<int>>(n);
	deg = vector<int>(n);
	for (int i = 0; i < m; ++i) {
		int x, y;
		cin >> x >> y;
		--x, --y;
		g[x].push_back(y);
		g[y].push_back(x);
		++deg[x];
		++deg[y];
	}
	
	int pos = 0;
	for (int i = 0; i < n; ++i) {
		if (deg[pos] < deg[i]) {
			pos = i;
		}
	}
	
	bfs(pos);
	shuffle(ans.begin(), ans.end(), rnd);
	for (auto it : ans) cout << it.first + 1 << " " << it.second + 1 << endl;
	
	return 0;
}

1133F2 - Spanning Tree with One Fixed Degree

Idea: MikeMirzayanov

Tutorial

Solution

#include <bits/stdc++.h>

using namespace std;

int n, m, D;
vector<vector<int>> g;

int cnt;
vector<int> p, color;
vector<pair<int, int>> ans;

mt19937 rnd(time(NULL));

void bfs(int s, int bad) {
	queue<int> q;
	q.push(s);
	color[s] = cnt;
	while (!q.empty()) {
		int v = q.front();
		q.pop();
		if (p[v] != -1) {
			if (rnd() & 1) ans.push_back(make_pair(p[v], v));
			else ans.push_back(make_pair(v, p[v]));
		}
		for (auto to : g[v]) {
			if (to == bad || color[to] != -1) continue;
			p[to] = v;
			color[to] = cnt;
			q.push(to);
		}
	}
	++cnt;
}

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	cin >> n >> m >> D;
	g = vector<vector<int>>(n);
	for (int i = 0; i < m; ++i) {
		int x, y;
		cin >> x >> y;
		--x, --y;
		g[x].push_back(y);
		g[y].push_back(x);
	}
	
	p = color = vector<int>(n, -1);
	cnt = 0;
	for (int i = 1; i < n; ++i) {
		if (color[i] == -1) {
			bfs(i, 0);
		}
	}
	
	if (cnt > D || D > int(g[0].size())) {
		cout << "NO" << endl;
		return 0;
	}
	
	sort(g[0].begin(), g[0].end(), [](int a, int b) {
		return color[a] < color[b];
	});
	
	for (int i = 0; i < int(g[0].size()); ++i) {
		if (i == 0 || color[g[0][i]] != color[g[0][i - 1]]) {
			ans.push_back(make_pair(0, g[0][i]));
		}
	}
	D -= cnt;
	for (int i = 1; i < int(g[0].size()); ++i) {
		if (D == 0) break;
		if (color[g[0][i]] == color[g[0][i - 1]]) {
			ans.push_back(make_pair(0, g[0][i]));
			--D;
		}
	}
	
	g = vector<vector<int>>(n);
	for (auto it : ans) {
		g[it.first].push_back(it.second);
		g[it.second].push_back(it.first);
	}
	ans.clear();
	p = color = vector<int>(n, -1);
	cnt = 0;
	bfs(0, -1);
	
	shuffle(ans.begin(), ans.end(), rnd);
	cout << "YES" << endl;
	for (auto it : ans) {
		cout << it.first + 1 << " " << it.second + 1 << endl;
	}
	
	return 0;
}

Comments (56)

Show archived | Write comment?

angry_Dmitry

6 years ago, # |

+32

Explanation of f2 is copy-paste of f1, please fix it

→ Reply

saquib2508

+10

F2 tutorial is missing (F1 has been repeated). Also, The problem F1 really should've been ahead of the problem E (if you want to sort the problems according to their difficulties).

kuksag

vovuh , F2 tutorial is missing

diagon_alley

Can F2 be solved by finding articulation edges / bridges in the graph and as soon as we find bridge edge we merge them and after that we pick any random adjacent edges of vertex 1 so as to make its degree exactly d. and after make the whole tree connected using kruskal type algorithm? Here is my submission for reference of what i am talking. I am getting wrong answer on test 37. Pls tell if i am wrong. Thanks

Seyed37

6 years ago, # ^ |

+14

The idea for F2 is that if we remove vertex 1 then the graph will be K components and if K > D there is NO answer otherwise we should connect this K components with D edges after that we can choose any MST of the remaining graph.

BlueBlade

hope this test case will help you to understand why you are getting wa :) 7 8 4 1 2 1 3 1 4 1 5 1 6 1 7 7 6 5 4

abhi2402

The problem is that bridges tell us only that if that edge is removed,the graph will become disconnected, if u remove some set of edges which are not bridges it is still possible that the graph may become disconnected, that is why the above logic doesn't work.

hvk3

Turns out that my solution for D with maps having long double keys passed. I checked the test cases and would suggest the problem setters to do the same too. From what it appears, the cases seem weird. I've linked a screenshot regarding my concerns.

BledDest MikeMirzyanov Vovuh

thatchemguy

5 months ago, # ^ |

My idea for D, we can simply store -bi/ai in long long double in a map and then iterate to find the value for which maximum indices have the same value and it shall work https://codeforces.net/contest/1133/submission/264512885

MotaSanyal

← Rev. 2 →

why does this solution gets TLE whereas this solution gets Accepted?

nikeshthapa255

use pypy, it's faster than pypy3 in terms of basic numerical calculations.

BeheraJi

pypy is faster

sanket

MikeMirzayanov you Have Mistakenly provide E question tutorial in F question. Can you please explain 1133F2 — Spanning Tree with One Fixed Degree solution idea.

a_journey

"How to do transitions from dpi,j? The first transition is pretty intuitive: just skip the i-th (0-indexed) student. Then we can set dp[i+1][j+1]:=max(dp[i+1][j+1],dp[i,j])."

i think it should be dp[i+1][j] as by skipping ith student we are not increasing size. MikeMirzayanov

xiaoshizhan

I think it's a typo. It should be dp[i+1][j+1] = max(dp[i+1][j+1],dp[i][j+1])

dav23rr

I also stumbled upon this, will wait for the clarification of right transition..

noobinho

← Rev. 3 →

I'll will put the way I interpreted it.

When you are in a given state (i , j) (where the students in [1,...,i] are the possible students you can use and 'j' is the maximum quantity of teams you can use) you have to take the best between pick or not the student 'i'.

When you dont't pick student 'i' you will have to pick the solution for the case in which you have the students in [1,...,(i — 1)] as possible students to take and 'j' as the maximum quantity of teams you can use. This describe exactly what is in the state (i — 1 , j).

When you pick student 'i' you have to see what is the best way to pick it. So you look at the states when you allow (j — 1) teams as maximum quantity of teams and students in [1,...,z] (with z <= i) as possible students (states of the form (z , j — 1) with z <= i). When you pick a state like that you could create a new team and put the maximum quantity of possible students (which are in [(z + 1),...,i]) in it to get a candidate for the state (i , j). But remember that you want the student 'i' to be in it. So you want to see only states (z , j — 1) (with z <= i) such that you could create a new team and put all students in [(z + 1),...,i] in it.

With a good care this can be done in O(n*k): 51128813

vovuh

I will fix F2 tutorial in a few hours. Please wait a bit.

Fixed.

BobTheBuiler

In D, why we should ensure numerator is non-negative?

BledDest

We should treat fractions $\text{[math]}$ and $\text{[math]}$ as the same one.

@Vovuh How is ur editorial of F2 different from this? . Aren't they same?

ssetia19

In div2 D, Why does use of unordered_map gives a TLE but normal map works fine ? Solution 51071398 gives TLE with unordered_map but this 51071641 gets Accepted with map

Rahul

unordered_map has O(1) complexity on average, but input can be engineered so that it take O(n) collisions for each access. Read more about it here.

MS1908

How to do problem C using binary search?

Sort the array in ascending order. For every element in the array (let it be arr) find how many elements satisfy ≥ arr_i and ≤ arr_i + 5. Take maximum length of all such ranges. See this code for the implementation.

Mr.Awesome

For problem D we can prevent precision error by using BigDecimal for example in java, the largest fraction is 1000000000 / 999999999 = 1.000000001000000001000000001, the numbers after the 1. well represent the rounding we will use inside the BigDecimal class, 51105537

ldv_IT

In E. Why can't we just simply use two pointers. My idea is to sort this array then use two pointers as below a[n+1] = 2e9; for(int l = 1, r = 1; l <= r && r <= n+1;) { if(a[r] — a[l] <= 5) r++; else{ len[m++] = r-l; l = r; } } sort(len, len+m, greater()); for(int i = 0; i < k; ++i) ans += len[i]; But I get wrong answer on test 25. Can some one help me?

BOGDAN_

This example can help you: 10 1 11 9 8 7 6 5 5 5 5 5

wotanello

← Rev. 7 →

DP in editorial for E is something different from its definition.

In that solution we just skip intermediate students (i, i + cnt_i), but in this case dp[i + z][j + 1] (z = 1 ... cnt_i — 1) is not increased as it should be.

Consider following example: n=3, k=1 a[] = 1 1 1

Then editorial code outputs: dp[i][j]=

But by definition dp[1][1] = dp[2][1] = 1, because we form one team from these students.

Can someone please explain what dp[i][j] really stands for?

mangat

can E be solved using divide and conquer after sorting?

prakhar897

Can anybody tell me why this solution got TLE my submission

LightYear

Can someone explain why the maximum number of students is possible only when there are exactly k teams as written in the solution for E?

Astaroth

f2 is missing!

ShivamPrasad

my solution for F1 https://codeforces.net/contest/1133/submission/51458164 is giving correct output on my computer but I am getting wrong answer on codeforces. I am not able to understand the reason. Can anyone help me out ?

I saw your code and ran it on ideone. It works fine on ideone. So I submitted it just to be sure and got WA, just as you got. Then I noticed the size of the vector you allocated in the bfs function. It should be n+1. I got AC after changing it. https://codeforces.net/contest/1133/submission/51472660 This is the AC code. Only the size is changed, nothing else. It worked on your machine and ideone probably because it allowed out of bound call, and luckily there was no garbage value in that memory.

Yes I got it. Thanks !

In problem E, why can't we just loop k times, in each loop get the team with max members under the given condition, take the remaining students and continue till k teams are formed. My submission

twowrist

4 years ago, # ^ |

I was doing the same thing and got wrong on 52 as well, did you figure it out? Please tell me if you did.

vlad

$$$k = 2$$$

$$$arr = [1, 6, 6, 7, 7, 12]$$$

XNight_KingX

5 years ago, # |

Can any one help why my binary search solution isn't working? https://codeforces.net/contest/1133/submission/55474924

JustasLe

5 years ago, # ^ |

When passing a vector to a function, you should pass it by reference, otherwise it may lead to TLE, just like it did for you (read more here). Also, in your binary search function, you do not define your variable "ans" when you create it, which can be problematic if you never set the value during your binary search.

I would also suggest using standard C++ lower_bound or upper_bound functions when doing a binary search on a sorted array (or in your case, a vector). It might take some time and practice to learn how to use them but it will be really useful and you won't have to write your own binary searches when it is unnecessary.

OMG, this silly mistake I was doing it whole time in many questions, thanks a lot for pointing out, just checked lower_bound function it's really helpful. all the three tips were helpful, BTW, can you help me with this dynamic programming question https://codeforces.net/contest/158/problem/E I am really stuck, not able to understand how to form the base cases (i,e. initial values of 2d array dp[][]). Thanks Again

I can see that the editorial of that contest (link) has a few comments regarding this problem and you might find them helpful.

Also, when you need help with a problem it is a good idea to ask for help by creating a separate blog for it, I have noticed that people tend to answer these more often than comments under blogs like this.

Mooncrater

4 years ago, # |

For 1133E — K Balanced Teams, I've used a backward DP that's my best friend, unlike the forward DP given in the editorial.

Here is my submission.

decoder__

Can you explain your solution?

It's pretty much like in the editorial. The $$$cnt_i$$$ in my solution represents the number of students in a team, if the $$$i^{th}$$$ student is the last one in it.

And the dp goes in the similar manner. The $$$dp_{i,j}$$$ represents the maximum total number of students, in upto j teams, while considering the first $$$i$$$ students.

You can decide to take or not take a student, and the dp simply states that, in the for loops.

It's been 3 months so I had to look into the solution itself again to understand what I'd done. Do let me know if you need more clarification.

f20190474

Can someone help me figure out why am I getting TLE. I have written almost the same code as in the solution provided.84302770

_Sazid_

You can solve that problem C by map easily.

Code

#include<bits/stdc++.h>
using namespace std;

int main(){
    int n, best = 0;
    cin >> n;
    int arr[n];
    map<int, int> mp;
    for(int i = 0; i < n; i++){
        cin >> arr[i];
        for(int k = 0; k <= 5; k++) mp[arr[i] - k]++;
    }
    for(auto it: mp){
        int p = it.second;
        if(p > best) best = p;
    }
    cout << best;
}

vinay_lingam

vovuh, editorials are not linked to contest materials of problems. can u please look into it?

Una_Shem

Thanks!:) Fixed!

Sindy

Why in solution he shuffles the output ?

5 months ago, # |

Vovuh can stay on top of the contributors table just by organizing 1/2 Div. 3 rounds per month xD

vovuh's blog