Codeforces Round #521 (Div. 3) Editorial

#	User	Rating
1	tourist	3985
2	jiangly	3814
3	jqdai0815	3682
4	Benq	3529
5	orzdevinwang	3526
6	ksun48	3517
7	Radewoosh	3410
8	hos.lyric	3399
9	ecnerwala	3392
9	Um_nik	3392

#	User	Contrib.
1	cry	169
2	maomao90	162
2	Um_nik	162
4	atcoder_official	161
5	djm03178	158
6	-is-this-fft-	157
7	adamant	155
8	awoo	154
8	Dominater069	154
10	luogu_official	150

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 t;
	cin >> t;
	for (int i = 0; i < t; ++i) {
		int a, b, k;
		cin >> a >> b >> k;
		cout << (a - b) * 1ll * (k / 2) + a * (k & 1) << endl;
	}
	
	return 0;
}

1077B - Disturbed People

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];
	}
	
	int ans = 0;
	for (int i = 1; i < n - 1; ++i) {
		if (a[i] == 0 && a[i - 1] == 1 && a[i + 1] == 1) {
			++ans;
			a[i + 1] = 0;
		}
	}
	cout << ans << endl;
	
	return 0;
}

1077C - Good Array

Tutorial

Solution

#include <bits/stdc++.h>

using namespace std;

const int MAX = 1e6;

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	int n;
	cin >> n;
	vector<int> a(n);
	vector<int> cnt(MAX + 1);
	for (int i = 0; i < n; ++i) {
		cin >> a[i];
		++cnt[a[i]];
	}
	long long sum = accumulate(a.begin(), a.end(), 0ll);
	
	vector<int> ans;
	for (int i = 0; i < n; ++i) {
		sum -= a[i];
		--cnt[a[i]];
		if (sum % 2 == 0 && sum / 2 <= MAX && cnt[sum / 2] > 0) {
			ans.push_back(i);
		}
		sum += a[i];
		++cnt[a[i]];
	}
	
	cout << ans.size() << endl;
	for (auto it : ans) cout << it + 1 << " ";
	cout << endl;
	
	return 0;
}

1077D - Cutting Out

Tutorial

Solution

#include <bits/stdc++.h>

using namespace std;

const int MAX = 200 * 1000 + 1;

int n, k;
vector<int> s, t;
vector<int> cnts(MAX);

bool can(int cnt) {
	t.clear();
	for (int i = 0; i < MAX; ++i) {
		int need = min(cnts[i] / cnt, k - int(t.size()));
		for (int j = 0; j < need; ++j) {
			t.push_back(i);
		}
	}
	return int(t.size()) == k;
}

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	cin >> n >> k;
	s = vector<int>(n);
	for (int i = 0; i < n; ++i) {
		cin >> s[i];
	}
	for (auto c : s) {
		++cnts[c];
	}
	
	int l = 0, r = n;
	while (r - l > 1) {
		int mid = (l + r) >> 1;
		if (can(mid)) {
			l = mid;
		} else {
			r = mid;
		}
	}
	if (!can(r)) can(l);
	for (auto it : t) cout << it << " ";
	cout << endl;
	
	return 0;
}

1077E - Thematic Contests

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;
	map<int, int> cnt;
	for (int i = 0; i < n; ++i) {
		int x;
		cin >> x;
		++cnt[x];
	}
	
	vector<int> cnts;
	for (auto it : cnt) {
		cnts.push_back(it.second);
	}
	sort(cnts.begin(), cnts.end());
	
	int ans = 0;
	for (int i = 1; i <= cnts.back(); ++i) {
		int pos = int(cnts.size()) - 1;
		int cur = i;
		int res = cur;
		while (cur % 2 == 0 && pos > 0) {
			cur /= 2;
			--pos;
			if (cnts[pos] < cur) break;
			res += cur;
		}
		ans = max(ans, res);
	}
	cout << ans << endl;
	
	return 0;
}

1077F1 - Pictures with Kittens (easy version)

Tutorial

Solution

#include <bits/stdc++.h>

using namespace std;

const long long INF64 = 1e18;

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	int n, k, x;
	cin >> n >> k >> x;
	vector<int> a(n);
	for (int i = 0; i < n; ++i) {
		cin >> a[i];
	}
	vector<vector<long long>> dp(n + 1, vector<long long>(x + 1, -INF64));
	
	dp[0][x] = 0;
	for (int i = 1; i <= n; ++i) {
		for (int j = 0; j < x; ++j) {
			for (int p = 1; p <= k; ++p) {
				if (i - p < 0) break;
				if (dp[i - p][j + 1] == -INF64) {
					continue;
				}
				dp[i][j] = max(dp[i][j], dp[i - p][j + 1] + a[i - 1]);
			}
		}
	}
	
	long long ans = -INF64;
	for (int i = n - k + 1; i <= n; ++i) {
		ans = max(ans, *max_element(dp[i].begin(), dp[i].end()));
	}
	if (ans == -INF64) ans = -1;
	cout << ans << endl;
	
	return 0;
}

1077F2 - Pictures with Kittens (hard version)

Tutorial

Solution

#include <bits/stdc++.h>

using namespace std;

#define x first
#define y second
#define mp make_pair

typedef long long li;
typedef pair<li, li> pll;

const li INF64 = 1e18;

struct myQueue {
	stack<pll> s1, s2;
	
	int size() {
		return s1.size() + s2.size();
	}
	
	bool isEmpty() {
		return size() == 0;
	}
	
	long long getMax() {
		if (isEmpty()) {
			return -INF64;
		}
		if (!s1.empty() && !s2.empty()) {
			return max(s1.top().y, s2.top().y);
		}
		if (!s1.empty()) {
			return s1.top().y;
		}
		return s2.top().y;
	}
	
	void push(long long val) {
		if (s2.empty()) {
			s2.push(mp(val, val));
		} else {
			s2.push(mp(val, max(val, s2.top().y)));
		}
	}
	
	void pop() {
		if (s1.empty()) {
			while (!s2.empty()) {
				if (s1.empty()) {
					s1.push(mp(s2.top().x, s2.top().x));
				} else {
					s1.push(mp(s2.top().x, max(s2.top().x, s1.top().y)));	
				}
				s2.pop();
			}
		}
		assert(!s1.empty());
		s1.pop();
	}
};

int n, k, x;
vector<int> a;

vector<myQueue> q;
vector<queue<int>> pos;
vector<vector<long long>> dp;

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	cin >> n >> k >> x;
	a = vector<int>(n);
	for (int i = 0; i < n; ++i) {
		cin >> a[i];
	}
	q = vector<myQueue>(x + 1);
	pos = vector<queue<int>>(x + 1);
	dp = vector<vector<long long>>(n + 1, vector<long long>(x + 1, -INF64));
	
	dp[0][x] = 0;
	pos[x].push(-1);
	q[x].push(0ll);
	
	for (int i = 1; i <= n; ++i) {
		for (int j = 0; j <= x; ++j) {
			while (!pos[j].empty() && pos[j].front() < i - k - 1) {
				q[j].pop();
				pos[j].pop();
			}
		}
		for (int j = 0; j < x; ++j) {
			if (!q[j + 1].isEmpty()) {
				dp[i][j] = max(dp[i][j], q[j + 1].getMax() + a[i - 1]);
				q[j].push(dp[i][j]);
				pos[j].push(i - 1);
			}
		}
	}
	
	long long ans = -INF64;
	for (int i = n - k + 1; i <= n; ++i) {
		ans = max(ans, *max_element(dp[i].begin(), dp[i].end()));
	}
	if (ans == -INF64) ans = -1;
	cout << ans << endl;
	
	return 0;
}

Comments (43)

Show archived | Write comment?

Vladislao

6 years ago, # |

← Rev. 2 →

+64

In spite of being (of course) an overkill for problem F1 and F2, it's really interesting to point out that many problems of that kind are solvable with a linear programming approach. For example see this 45824522.

Of course, problem F2 has to be solved with a randomized-pivoting version of simplex algorithm (mine's is much simpler and shorter so it TLE's on Test 37).

The thing is that when you have this kind of conditions, the problem actually becomes solvable, because the matrix you have is totally unimodular (I didn't try to prove it this time, but I relied heavily on Problem D "Delight of a cat" from 2016-2017 NEERC Problemset).

Specially in online-contests on which you are allowed to copy-paste these long pieces of code, it's useful to be aware of this, because the actual writing part of the program is indeed straightforward.

→ Reply

vovuh

6 years ago, # ^ |

+11

Wow, that's quite cool and interesting!

Dhruv_Gheewala

4 years ago, # ^ |

can anyone please explain this simplex algorithm? which type of problem can be solved using this algorithm?

watchdogs132

Could someone explain to me the logic behind this if statement in problem C: if (sum % 2 == 0 && sum / 2 <= MAX && cnt[sum / 2] > 0)?.

apoorv1999

Let i be the index of the number being removed from the array. Hence, the new sum will be equal to sum(original sum)-arr[i]. Now, let arr[j] be the number for with the property holds true. Therefore, arr[j] = sum(new sum) — arr[j] => arr[j] = sum/2. As all the numbers in the array are integers with their maximum value being 10^6, if such an arr[j] exists, sum should be divisible by 2 and sum/2 should be less than or equal to 10^6. cnt[sum/2] simply tells whether such a number exists or not.

Mohit_Thorat

why do we have check sum/2 is less than 10^6?

noteezy

5 years ago, # ^ |

we are looking for a number that equals to the rest of the array. so sum of all elements(including that number) sum = (our number plus rest of array). sum/2 = our number and sum/2 = sum of rest array. but our max value of number equals to 10^6 so that why we check sum/2 < 10^6. idk if it helps, but I tried

Suraj_IOI

I am having trouble understanding tutorial logic,can anyone explain me problem 1077C — Good Array, Thanks

gagannagpal68

← Rev. 8 →

So, think in this manner. For every i, can it be a nice index or not ? How can we think to solve it for every 'i' in reasonable time ? Well, let's try to think what all do we need to calculate to answer that if 'i' is nice or not? So, we need to remove 'i'th element and then check whether the remaining sum is exactly twice of a single element in the array(after excluding ith element).

Finding the remaining sum is easy.(We can have a global sum variable and we will subtract a[i] from it).

Now, How to check whether this is twice of single element or not ? (hash table ?) Sure, we can have a cnt[] array which will say, cnt[5] = 3, that means three 5's are in array. (think of it as occurence/ frequency array).

Now, how this will help in finding the previous question ?

Ans: We have sum(remaining sum after excluding ith element), we can check that if(cnt[sum/2] >1 and sum%2==0). i.e.(sum should be even and there should be an element in array equal to sum/2). But there is a catch. It could happen that ith element itself = sum/2. So. we need to tackle that too. Sure, we can have nasty if else.

Tutorial presents an elegant way, which is:

Find the sum(remaining sum)

subtract this element from cnt array(by decrementing it)

Now check for if(cnt[sum/2] >1 and sum%2==0)

again add this elememt to cnt array.

again add a[i] to sum.

In case of some doubt, feel free to ask.

ABugWithTheBigDreams

10 months ago, # ^ |

awsm explanation

dushyant7917

Can someone please explain why this code gave WA for problem F1 ?

WinstonWolf

Another greedy approach for problem E:

If we have k distinct topics, let's call number of problems for j-th topic k[j] such that 0<=j<=k-1.

the following solution is built on an observation: if the optimal solution is to create X contests, then these X contests could be made from the X topics which have the largest number in array k.

So we need to sort array k to have the largest number in the beginning.

Then we need to know for every X (number of contests) what is the maximum number of problems we can use, let's call this number M.

We already know the answer to make 1 contest M = k[0]. Then for making 2 contests: M = min(M/2, k[1]). Generally M = min(M/2, k[X-1]). And finally for every X compute the answer as follows: ans= max( ans , M * ( 2^(X+1) — 1 ) ).

ArnavGarg

Great solution! Easier to understand than the tutorial one, thanks mate !

CriticalPundit

I solved the problem using exact same approach! However, I cannot understand the solution in tutorial :(

Shohanur_1603020

6 months ago, # ^ |

Awesome ! Your solution is slightly better than mine.

Ahmed_Diab

Can anyone please tell me why problem F2 cannot be solvable with Segment Tree(or any RMQ Data Structure) ?

WolfBlue

Author was not saying it was unsolvable using segment tree, just that their method was easier to code

Lihwy

i got TLE with these data structures :)

Masalmah

Another solution for D without Binary search using priority_queue, 45895914.

VivekKumarChaudhary

why are you doing f[i]/j? please explain.

To include every possible solution can get it from these Frequency, suppose the freq = 5, so i push 5, 2, 1, 1, 1 in priority queue if freq 1 is in the solution this guarantee that 2 and 5 in the solution so the best is to take this number 5 or k times in this case.

mehulcoder

Masalmah How does that maximize the answer?

gagan_sharma

3 years ago, # ^ |

I think your solution passed because of weak test cases. For this test case
6 2
2 2 2 2 1 1
your solution outputs 2 2 while the answer is 1 2.
You can check out my solution. Your priority queue idea was correct but your solution is saving information in a wrong way. Your priority queue for the given testcase looks like.
4 2
2 2
2 1
1 2
1 2
1 1
So your solution thinks that picking two 2s or 1,2 gives 4*2 permutations but that is wrong as picking two 2s gives 4C2 = 6 permutations and picking 1,2 gives 4*2=8. So 1,2 should be the correct answer.

Jesus011115

Can you explain me your idea , please i want to learn

if we can divide the freq of any letter in small group of freq(with same letter), then if the smallest one is in solution the greater also in solution.

Kelly

solved F2 using DP DnC

clafcm

what is DP DnC ?

It's a dynamic programming optimization technique. The DnC stands for divide and conquer. You can learn more from here https://codeforces.net/blog/entry/8219

skmonir

Thanks Kelly! Your comment helped me to learn Divide & Conquer Optimization and solve this beautiful problem for Vova. ^_^

I am having trouble understanding the logic of 1077D — Cutting Out. Can someone please explain it and help me. Thanks!

honeysingh123

NOTE: I was not able to solve it during the contest, but I was able to do it afterwards.

This is one type of binary_search problem. You will encounter many such problems. General binary_search which you might have studied(or will study) in the university is done over an array of numbers. In this kind of problems, you need to perform the binary_search over the entire solution space.

For e.g.: In this problem, you can consider the entire solution space as all numbers ranging from 1 to n (as you cannot have more than "n" copies).

So, step 1 of this problem is to find the maximum number of copies which can be cut out from the the given array. Let me call this value as val. How we are going to find val, I will come back to that later. Let us move to Step 2

Step 2

Now, given that if we want to cut out val copies from the given array, can we do that ?

In order to answer this question we need to first construct a frequency array (In this we will store the frequency of all given numbers).

We need to construct an array of length k We iterate over all elements over the frequency array. First we check that whether the given key in frequency array has value more than val. If it has a value more than val. Then this can be used in the construction of the array.

But there is an interesting catch here. Since, duplicates are allowed in the given answer, we might be able to use the same value again. So, we can use that value atmost floor(value/val) number of times.

So this is basically the can function being talked in the above tutorial.

Now coming back to Step 1.

We need to figure out what values of val are valid. Minimum Val = 0 Maximum Val = n If we do a binary_search over this, then we will be able to get the MAXIMUM possible value of val.

Another thing to note is binary_search can only be done when the array(solution space) is monotonically increasing. In this case, as mentioned in the tutorial, if you can create, val copies you can also create val - 1 copies.

Here is my solution: http://codeforces.net/contest/1077/submission/45915120

Enigmatic_Smile

Can anyone please explain the problem statement of 1077B, I find it confusing especially that explanation of first test case and what does k pairwise district flat means? please illustrate with a test case. Thanks in advance!

gratus907

As I understood pairwise distinct simply means that none of them should be counted (turned-off) twice or more.

Let's consider the first example

1 1 0 1 1 0 1 0 1 0

(Their index is 1-based)

As the statement, No. 3 and No. 6, No. 8 are disturbed (because both people next to them turned on)

To make sure there are nobody "disturbed", you must turn off some lights. One way : we can turn No. 2, 4, 5, 7, 9 off. This way, the testcase turns to

1 0 0 0 0 0 0 0 0 0

This was simple way to do the task : turn every light off which contributes making someone 'disturbed'

However, we can do better. note that if we turn No.2 off, we don't have to turn No.4 off. No. 3 is already in peace.

Note one more : if we turn No.7 off, we can make both No.6 and No.8 'not disturbed' by turning only one light off.

If we turn 2 and 7 off,

1 0 0 1 1 0 0 0 1 0

Nobody is disturbed.

If we turn 4 and 7 off

1 1 0 0 1 0 0 0 1 0

We can't do better (i.e. task is impossible by turning 1 light off), so the answer is 2.

Hope this is helpful :)

Jerry_Mouse

I can't understand, why in problem D solution this line is written ??

" if (!can(r)) can(l); " at the just end of binary search!

DDullahan

cause in binary search, the solution used l = mid; if l = 2, r = 3, mid = 2 and can(mid)=true, this will be infinity loop.

so you can see the loop ends where r-l>1 and after that r maybe an answer and l must be an answer.

but at condition above, we didn't check whether r can be an answer, if it can, this will be the real answer because r>=l

priojeet_priyom

can anyone please explain why i am getting WA. my approach: iterate through X let it be x and iterate through n let it be i. Then find maximum elemment in dp[i-k-k-1: i-1] [x-1], add ara[i] with it and save in dp[i][x]. submission

Leonardo_Paes

C isnt just a max segment tree?

sbhmsh

Can anyone help, why i am getting wrong answer at test case 12 in ques E. Here is my solution-https://codeforces.net/contest/1077/submission/54516795

I found the mistake.Here is accepted code-https://codeforces.net/contest/1077/submission/54522333

gjaiswal108

5 years ago, # |

Getting TLE on using unordered_map, while AC on using map for problem E. Can anyone explain why??(I think unordered_map should be faste than map bcz its time complexity is O(1) for all operation.)

Link for TLE Solution

Link for AC Solution

prabalsingh24

unordered_map's time complexity is O(k) where k is the size of the bucket, usually it is small hence we consider it to be O(1). In your case, there must've been alot of collison hence getting tle. Ordered_map is LogN always.

nishuz

4 years ago, # |

Hey guys.

I used max queue + DP to solve 1077F2 - Pictures with Kittens (hard version) in $$$\mathcal{O}(nx)$$$. Can someone please tell me why 106266241 TLEs and why 106266040 passes? Both codes are the same. The first submission is in C++14 (TLEs for TL = 2500 ms) and the second one is in C++17 (64) (which passes in just 982 ms). Why is the difference so huge? What can I do to avoid this in the future?

arnab_baishnab

5 months ago, # |

Problem F2 can be solved easily using deque data structure. Here's my easy solution using a deque that contains pair of integers {Value, Index}. The logic is this deque (kind of monotonous) will contain elements in increasing order of Value and will always push in front and pop from back.

vovuh's blog