Codeforces Round #653 (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;
	while (t--) {
		int x, y, n;
		cin >> x >> y >> n;
		if (n - n % x + y <= n) {
			cout << n - n % x + y << endl;
		} else {
			cout << n - n % x - (x - y) << endl;
		}
	}
	
	return 0;
}

1374B - Multiply by 2, divide by 6

Idea: vovuh

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;
	while (t--) {
		int n;
		cin >> n;
		int cnt2 = 0, cnt3 = 0;
		while (n % 2 == 0) {
			n /= 2;
			++cnt2;
		}
		while (n % 3 == 0) {
			n /= 3;
			++cnt3;
		}
		if (n == 1 && cnt2 <= cnt3) {
			cout << 2 * cnt3 - cnt2 << endl;
		} else {
			cout << -1 << endl;
		}
	}
	
	return 0;
}

1374C - Move Brackets

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 t;
	cin >> t;
	while (t--) {
		int n;
		string s;
		cin >> n >> s;
		int ans = 0;
		int bal = 0;
		for (int i = 0; i < n; ++i) {
			if (s[i] == '(') ++bal;
			else {
				--bal;
				if (bal < 0) {
					bal = 0;
					++ans;
				}
			}
		}
		cout << ans << endl;
	}
	
	return 0;
}

1374D - Zero Remainder Array

Idea: vovuh

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;
	while (t--) {
		int n, k;
		cin >> n >> k;
		vector<int> a(n);
		for (auto &it : a) cin >> it;
		map<int, int> cnt;
		int mx = 0;
		for (auto &it : a) {
			if (it % k == 0) continue;
			++cnt[k - it % k];
			mx = max(mx, cnt[k - it % k]);
		}
		long long ans = 0;
		for (auto [key, value] : cnt) {
			if (value == mx) {
				ans = k * 1ll * (value - 1) + key + 1;
			}
		}
		cout << ans << endl;
	}
	
	return 0;
}

1374E1 - Reading Books (easy version)

Idea: MikeMirzayanov

Tutorial

Solution

#include <bits/stdc++.h>

using namespace std;

const int INF = 2e9 + 1;

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	int n, k;
	cin >> n >> k;
	vector<int> times[4];
	vector<int> sums[4];
	for (int i = 0; i < n; ++i) {
		int t, a, b;
		cin >> t >> a >> b;
		times[a * 2 + b].push_back(t);
	}
	for (int i = 0; i < 4; ++i) {
		sort(times[i].begin(), times[i].end());
		sums[i].push_back(0);
		for (auto it : times[i]) {
			sums[i].push_back(sums[i].back() + it);
		}
	}
	
	int ans = INF;
	for (int cnt = 0; cnt < min(k + 1, int(sums[3].size())); ++cnt) {
		if (k - cnt < int(sums[1].size()) && k - cnt < int(sums[2].size())) {
			ans = min(ans, sums[3][cnt] + sums[1][k - cnt] + sums[2][k - cnt]);
		}
	}
	
	if (ans == INF) ans = -1;
	cout << ans << endl;
	
	return 0;
}

1374E2 - Reading Books (hard version)

Idea: MikeMirzayanov

Tutorial

Solution

#include <bits/stdc++.h>

using namespace std;

const int INF = 2e9 + 1;

#define size(a) int((a).size())

void updateSt(set<pair<int, int>> &st, set<pair<int, int>> &fr, int &sum, int need) {
	need = max(need, 0);
	while (true) {
		bool useful = false;
		while (size(st) > need) {
			sum -= st.rbegin()->first;
			fr.insert(*st.rbegin());
			st.erase(prev(st.end()));
			useful = true;
		}
		while (size(st) < need && size(fr) > 0) {
			sum += fr.begin()->first;
			st.insert(*fr.begin());
			fr.erase(fr.begin());
			useful = true;
		}
		while (!st.empty() && !fr.empty() && fr.begin()->first < st.rbegin()->first) {
			sum -= st.rbegin()->first;
			sum += fr.begin()->first;
			fr.insert(*st.rbegin());
			st.erase(prev(st.end()));
			st.insert(*fr.begin());
			fr.erase(fr.begin());
			useful = true;
		}
		if (!useful) break;
	}
}

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	int n, m, k;
	cin >> n >> m >> k;
	vector<pair<int, int>> times[4];
	vector<int> sums[4];
	for (int i = 0; i < n; ++i) {
		int t, a, b;
		cin >> t >> a >> b;
		times[a * 2 + b].push_back({t, i});
	}
	for (int i = 0; i < 4; ++i) {
		sort(times[i].begin(), times[i].end());
		sums[i].push_back(0);
		for (auto it : times[i]) {
			sums[i].push_back(sums[i].back() + it.first);
		}
	}
	
	int ans = INF;
	int pos = INF;
	set<pair<int, int>> st;
	set<pair<int, int>> fr;
	int sum = 0;
	vector<int> res;
	for (int iter = 0; iter < 2; ++iter) {
		st.clear();
		fr.clear();
		sum = 0;
		int start = 0;
		while (k - start >= size(sums[1]) || k - start >= size(sums[2]) || m - start - (k - start) * 2 < 0) {
			++start;
		}
		if (start >= size(sums[3])) {
			cout << -1 << endl;
			return 0;
		}
		int need = m - start - (k - start) * 2;
		for (int i = 0; i < 3; ++i) {
			for (int p = size(times[i]) - 1; p >= (i == 0 ? 0 : k - start); --p) {
				fr.insert(times[i][p]);
			}
		}
		updateSt(st, fr, sum, need);
		for (int cnt = start; cnt < (iter == 0 ? size(sums[3]) : pos); ++cnt) {
			if (k - cnt >= 0) {	
				if (cnt + (k - cnt) * 2 + size(st) == m) {
					if (ans > sums[3][cnt] + sums[1][k - cnt] + sums[2][k - cnt] + sum) {
						ans = sums[3][cnt] + sums[1][k - cnt] + sums[2][k - cnt] + sum;
						pos = cnt + 1;
					}
				}
			} else {
				if (cnt + size(st) == m) {
					if (ans > sums[3][cnt] + sum) {
						ans = sums[3][cnt] + sum;
						pos = cnt + 1;
					}
				}
			}
			if (iter == 1 && cnt + 1 == pos) break;
			need -= 1;
			if (k - cnt > 0) {
				need += 2;
				fr.insert(times[1][k - cnt - 1]);
				fr.insert(times[2][k - cnt - 1]);
			}
			updateSt(st, fr, sum, need);
		}
		if (iter == 1) {
			for (int i = 0; i + 1 < pos; ++i) res.push_back(times[3][i].second);
			for (int i = 0; i <= k - pos; ++i) {
				res.push_back(times[1][i].second);
				res.push_back(times[2][i].second);
			}
			for (auto [value, position] : st) res.push_back(position);
		}
	}
	
	cout << ans << endl;
	for (auto it : res) cout << it + 1 << " ";
	cout << endl;
	
	return 0;
}

1374F - Cyclic Shifts Sorting

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
	
	auto make = [](vector<int> &a, int pos) {
		swap(a[pos + 1], a[pos + 2]);
		swap(a[pos], a[pos + 1]);
	};

	int t;
	cin >> t;
	while (t--) {
		int n;
		cin >> n;
		vector<int> a(n);
		vector<pair<int, int>> res(n);
		for (int i = 0; i < n; ++i) {
			cin >> a[i];
			res[i] = { a[i], i };
		}
		sort(res.begin(), res.end());
		for (int i = 0; i < n; ++i) {
			a[res[i].second] = i;
		}
		int cnt = 0;
		for (int i = 0; i < n; ++i) {
			for (int j = i + 1; j < n; ++j) {
				cnt += a[j] < a[i];
			}
		}
		if (cnt & 1) {
			for (int i = 0; i < n - 1; ++i) {
				if (res[i].first == res[i + 1].first) {
					swap(a[res[i].second], a[res[i + 1].second]);
					break;
				}
			}
		}
		vector<int> ans;
		for (int i = 0; i < n - 2; ++i) {
			int pos = min_element(a.begin() + i, a.end()) - a.begin();
			while (pos > i + 1) {
				make(a, pos - 2);
				ans.push_back(pos - 2);
				pos -= 2;
			}
			if (pos != i) {
				make(a, i);
				make(a, i);
				ans.push_back(i);
				ans.push_back(i);
				pos = i;
			}
		}
		for (int i = 0; i < 3; ++i) {
			if (is_sorted(a.begin(), a.end())) {
				break;
			}
			make(a, n - 3);
			ans.push_back(n - 3);
		}
		if (!is_sorted(a.begin(), a.end())) {
			cout << -1 << endl;
		} else {
			cout << ans.size() << endl;
			for (auto it : ans) cout << it + 1 << " ";
			cout << endl;
		}
	}
	
	return 0;
}

Comments (133)

Show archived | Write comment?

codingsamrat

4 years ago, # |

← Rev. 2 →

Please Someone Explain Why i am Getting TLE in Test case#5 of Question D

My Submission is : 85376735

→ Reply

gursharan123

4 years ago, # ^ |

You didn't take into account the case when till the end a[i]==a[j] then first condition is overlooked and cnt is increased and i is incremented and this keeps going on. Then it becomes O(n^2). Also you have to use long long to prevent overflow. I made minor changes to your code, and it got accepted. Link

Thanks...

rajdeepsaha

For problem D-Zero Remainder Array, why does my code get a TLE on test 8 despite using a similar approach? My code: https://mirror.codeforces.com/contest/1374/submission/85382181

the_pythor

Use map instead of unordered map. Unordered map worst time complexity is O(N).Even I got penalty :(

why_I

Please tell me how you come up with an approach to solve the first question.

I just found the nearest factor of x which is less than or equal to n. I'll add y to it and see if it's greater than n. If it's greater than n then I'll subtract x from it

aneee

Even my first submission was with an unordered_map :(. Got penalty.

sahaun

Or, you can use a custom hash function.

This is a really good blog post on the topic.

techno_phyle

← Rev. 4 →

Finally Editorial Published. Thanks vovuh and team.

Ar_Anik

After Long Time

at_kansal

Please organize another div3 round. This was a div3 round after a long time. Newbies like me need div3 rounds continuously.

lordbeerus

Agreed. This one was great round! We need more!

Giga_Cronos

I don't know why, But I get better results in Div2 rounds. The reason could be that I'm to slow when I'm coding

If you think you need speed then you should do atcoder beginner. By doing that you will gain speed and even fast debugging.

Thanks

Satoru

-32

Am I the only one who think that this was the best round ever ?!

Virtual_Contestant

you reached specialist that's why :)) well done

-6

Yeah!

I want more contests made by vovuh <3

majorSSN

← Rev. 3 →

-17

Can E1 be done using DP?

-76

wow newbies know dp greatttt

Rudro25

Bad idea..

fuadhasanc9934

what do you mean?I knew it when I was unrated.

asitnikoff

i don't think so. i don't have any idea about dp. this type of problems always solving with greedy approach

PThakur_16

-39

https://mirror.codeforces.com/contest/1374/submission/85385019 Solution for B

WHY ARE YOU PEOPLE DOWNVOTING ??????

TELL ME IS THERE ANY PROBLEM WITH THIS CODE how can you simply downvote an AC CODE****????

After solved a easy problem no need to comment here that's hide the important comment.

amiralisalimi

+14

Ahsant. problem E2 is really nice (and hard). But the proof is not clear to me. I mean the analysis of number of times the operation is done.

Upd: Yeah got it now. The editorial was also clean. Well that's why I always take part in Div3s.

Induber

I solved E2 by applying ternary search on number of common books, but i don't have any proof that it is unimodal. Can someone explain me how it is unimodal or my solution is hackable?

navneet.h

Can anyone explain other solutions of E2, as I saw many solution using bit tree ,treaps, ternary search.

AbhishekAg

+11

Gr8 set of questions.....All of them seem doable.... although problem E(s) was a bit heavy on maintenance side....

coderboss

Could someone please help me with the problem E1 easy version. I implemented the idea which is iterating over the books of the three vectors and finding the cheapest price, but it always gives a wrong answer on test case 13.My answer is cheaper than the actual answer given by the system. Thanks in advance

This is my submission to the problem

ETheHedgehog

your problem is in line 258, you should make ctr1 = i + 1 not ctr1 = i because you want to test the next two books you can get not books you've already took fix it and you will get AC

@ETheHedgehog Thanks a lot and sorry for the late reply.

Kaleab_Asfaw

For Problem D: Find the ai % k for each element in a. Then find the one with the highest frequency (mode).

Let x be the number with highest frequency and f be the number of times it occurred .

If the new formed array (with ai % k) is empty or full of zeros the answer will be 0. Else the answer will be x + (k * (f — 1)) + 1.

Solution Python3 -- > 85419324

suggi_d_luffy

I did not get the + 1 part as to why the ans = ( ) + 1. Once you reach k times some number, you need key number of steps to reach key. why k *() + key + 1?

spookywooky

The +1 is because the first number used is 0, not 1. So we need one step more than the highest number we need to use.

_Anas__

k*(value-1) + key is such a value of x which makes ai+x divisible by k

k*(value-1) + key comes as a cost of operation 2

+1 comes as a cost of operation 1

SPyofgame

-10

In problem B, I have another simple solution

Spoiler Alert

DragoPhoenix

It is the same thing, you have counted the no. of 2's and 3's in the factorisation of the number in the first loop. Then the remaining 3's in the second loop and no. should be reduced to 1 for answer to exist.

-12

E1 to E2 so big gap.E2 tooo hard for div3..... 
E1-1600 dificulty & E2-2500 dificulty  :(

zino_0

In E1 we can sort all books and pick books greedily. We need to keep track of number books liked by Alice and Bob, and a stack that stores books that are liked by single person only. Code

Messiah_10

Can somebody pls find the error in my code for E2 https://mirror.codeforces.com/contest/1374/submission/85464212. My procedure: Fist solve the problem like E1 and find out the number of items.If it is greater than M then erase 10 and 01 items and add 11 items.If it is less than M then we can add one 01,00,11,10 or we can remove one 11 item and add 01 and 10 items.

singleLOOP

Are you keeping in mind about having k books when deleting?. I think when after doing E1 we have say x books. If x<m then add books greedily from remaining books. If x>m then we have to delete two books (one liked by alice and one liked by bob) and add one book that both of them like

Yes the condition of k is always satisfied and we cant add greedily always maybe we can remove a book both of them likes and add 10 and 01 books

When x<m, why can't we add books of least price from remaining books?. After E1, condition of having k books for both is fulfilled with min price. Now, we need total m books. So, can't we just add books of min price from remaining books?

CSPrajeeth

No,

Won't work on this.

naeem4265

-7

problem E1..wrong ans test case 5...i can't find wrong my code...please help me to finding wrong or give me some small test http://mirror.codeforces.com/contest/1374/submission/85463861

_yuio_

You can put same in spoiler or provide link. Page becomes weird in this way. Their is an option to provide link when you post comment.

Oh. you have already provided link , so what was need of pasting whole code

-9

i pasted code for more attraction...edited

rajiv_kale

This is a trash way of presenting code.

edited

roshanchongder9

Codeforces Round #653 (Div. 3) D. Zero Remainder Array

In this Problem , if we consider a input — 1 2 5 4 4

then as per the solution provided,the output is 7 but if we conside like —

1 .when x = 1 , we will server one of the 4 (4+1=5 and 5%5=0) then x will become 2 2. when x = 2 , we will add it to the remaining 4 and it will become 6 and x will become 3 3. At this step , x is incremented and becomes 4 4. Now if we add 4 to the 6 , it will become 10 and 10%5==0 and then x becomes 5

So the answer should be 5 . . Is it ? ? ?

It was given that you can't apply first operation to same indexed element more than once. You have performed first operation of adding+incrementing x twice on second element

akulenok

No. You can add x for the number in array only one time. You cant do 4 + 2 + 4.

krishna_0_9

No, because this line was mentioned in the question. You cant do more than one operation on the same element "The first operation can be applied no more than once to each i from 1 to n."

harshilbhatia2001

My Video solution for the contest

Problem A,Problem B, Problem C The video is time stamped for your convenience (check the description).

Problem D
Problem E

satynarayan123

Can someone please help me, why my submission of problem A is getting TLE if I'm using a single while loop for a test case.

My submission: https://mirror.codeforces.com/contest/1374/submission/85356771

Thank you!

1000000000 1 99999999

consider this test case provided many times. Your single loop will run 99999998 times in each test case, which will definitely cause TLE

divianshu_14

Can someone please tell me what is wrong with this greedy approach for E2 :

Spoiler

Let's sort the books in 4 types : Type 1 : Books that only Bob likes. Type 2 : Books that only Alice likes. Type 3 : Books that both of them like. Type 4 : Books that none of them like.

Let's find the maximum amount of books of Type 1 or Type 2 that can be picked. They would simply be (m-k). Let's denote it with allowed

Greedily pick those books that either Alex or Bob likes in the following way :
Let t1 denote least time taken for an unpicked book of type 1. 
Similarly t2 for type 2 and t3 for type 3 following above criteria.

Pick book based on which value is smaller of (t1+t2) or t3. If we had already picked up "allowed" amount of books of type 1, we would have to pick up book of type 3. Now this picking process continues till we had already picked up at least k books of liking for Alice and Bob.

We can fill in the rest of the remaining books with those unpicked books taking least time.

This approach fetched me a WA on test 12. I looked in the status and a lot of people got the same result on same test case. Can someone pls help. Thanks in advance

robostac

+35

Consider the test case below — your method would choose book 3 over 1+2 but then you still need to add another book which leaves you with a best cost of 5. You could instead pick 1+2 and get a cost of 4.

shahil_005

"and move it to the beginning (so the negative balance becomes zero again and the answer increases by one). This move is much more optimally than moving the current closing bracket to the right."

"Moving a closing bracket to end" or "an opening bracket to beginning",doing either of these will result in the same answer ,so why the second one is optimal ?

vovuh

I think you are right, these moves are equal. I can be very stupid sometimes, sorry for this confusing sentence, I'll remove it from the editorial.

h_squared

Can someone explain me why I am getting Wrong Answer in E2. https://mirror.codeforces.com/contest/1374/submission/85472085

My logic: lets call the 1 1 books as both. if both+Alice < k: then not possible also if both+Bob <k then not possible

Otherwise I sort the books. Then fulfill the condition of k by taking the cheapest book. Finally I take the remaining elements and sort them and take the cheapest books to complete the set

Edit: I am new to competitive programming so can you also help me to make my code efficient.

Vlaine

Man, if you are a newbie, why then try a problem that only grandmasters can solve?

+16

Why not solve it just for the sake of problem solving.

baddestguy

+13

Just like Errichto said if you have ideas for a problem then exhaust them before checking the solution. If in the end he cannot solve it, then fine but don't discourage people from trying

lucasxia01

I had a really simple solution for E1:

I claim that Alice and Bob will both read exactly $$$k$$$ books that they each like. If we had a selection where both of them read more than $$$k$$$ books that they liked, then we can subtract out books (which decreases the total time) of $$$11, 10, 01$$$ until one of them has read exactly $$$k$$$ books that they like and the other has read $$$K \geq k$$$ books that they like. However, if one of them has liked $$$K-k$$$ more books, then they must have read at least $$$K-k$$$ books where they were the only one to like it. Thus, we can take out these books as well, which gives us a selection of books where they read exactly $$$k$$$ books that they each like, which is better than the original selection (where at least one person liked more than $$$k$$$ books).

Now, based on the claim, if they read a $$$10$$$ book, they must also read a corresponding $$$01$$$ book in the optimal solution. Thus, the problem now just comes down to pairing these $$$10$$$ and $$$01$$$ books. We can do this greedily (I'll leave the proof for you). We sort the $$$10$$$ and $$$01$$$ books independently, and match them from lowest time to highest. Now, we essentially have created $$$11$$$ books from $$$10$$$ and $$$01$$$ books, where the time of this double-book is the sum of times of its two parts. We can just treat this double-book the same as a normal $$$11$$$ book, so we can sort the $$$11$$$ and $$$10+01$$$ books all together and take the first $$$k$$$ smallest times to find our answer.

Code: https://mirror.codeforces.com/contest/1374/submission/85336049

apurva_nitdgp

Has anyone solved problem D using sorting and 2 pointer approach?

devil_17

Check this.

shantanu_p_101_

Can anyone please help why am i getting wrong answer on test case 12 of problem E2. My code — https://mirror.codeforces.com/contest/1374/submission/85427982 Initially I have taken all books which is interesting for both.Then if it is less than k then i have taken from remaining books which are in sorted order until the count of interesting books for both is equal to k.After that i have replaced the books interesting for both with books interesting to 1 only(2 books added for each 1 book interesting to both removed).Afterwards I have just added more books to make the total count m.I am not being able to figure out what is wrong in this approach. Plz. help.

RedDreams

← Rev. 5 →

I had different approach to E1, solved it greedily.

We can separate books into 3 groups : the ones that Alice, Bob and both of them like respectively.

Sort them, and if the sum of the minimum element in "Alice" group and "Bob" group is less than the minimum element in "Both of them like" group, then i add up this sum to the answer, otherwise i add to the answer the minimum number from the "Both of them like" group.

Proof:

There are finite number of possibilities so the answer exsistes. If we replace books from the answer, that only Alice likes, by the same number of the smallest elements from the "Alice" group, answer will stay the answer, i mean that value of the answer won't get bigger. The same for the books from the answer, that only Bob likes.

If the sum of the smallest(unused) book from the asnwer, that only Alice likes and the one only Bob likes is smaller than biggest book that both Alice and Bob like, then we replace that one book by these two books, value of the answer won't get bigger, so it will remain an answer. Do it untill can't be done.

If the smallest book(unused) that both ALice and Bob like, has value smaller or equal to, the sum of the biggest by value book from the answer, that only Alice likes, and from the ones, that only Bob likes, then we can repalce these two books by that one book, and answer will remain answer, i mean answer value cannot get bigger. We do these untill it can be done.

And if we replace all the books from the answer, that both Alice and Bob like, by the same amount of smallest by value books from the group "Both ALice and Bob like", answer cannot get bigger, so it will remain an answer.

It is obvious, that there is only one such set of books to which any replacements from the above cannot be done and as shown above it is the answer.

The result we get from our greedy approach cannot have any of the replacement above, so it is the answer.

My submission

The_First_Avenger

Why i am getting wrong answer for this submission(Problem E1): https://mirror.codeforces.com/contest/1374/submission/85476850 Please help!!

_-pratik_shukla-_

https://mirror.codeforces.com/contest/1374/submission/85367241 problem D.. idk why i am getting WA on tc 2...i had the same approach as in editorial...can someon help please!!

I_love_joulej

Imho this approach for E2 is easier: first, let's take k elements from 11 group (if this group is smaller than k — take all books from 11 group and first k - size(11) books from each 01 and 10). If number of books that we took is greater than m — the answer is -1. Now, we have some set ans of books that we took (size(ans) <= m), and we have 5 possible transitions: first 4 is to simply add the cheapest book from one of the sets, and 5th is to delete the most expensive book from 11 set and add 2 books from 01 and 10 sets (after this transition we will add cost(added) - cost(deleted) to the answer. After each of this transitions number of books in ans increases by 1, thus we have to make m - size(ans) iterations, (in each iteration we will try to add as less as possible to the answer). This approach can be easily implemented by storing pointers for each group. My code — 85363378.

rohitm1

When you say “ first, let's take m elements from 11 group (if this group is smaller than m — take all books from 11 group and first m — size(11) books from each 01 and 10” I guess you mean K instead of m

regnarock35

Can somebody explain E2

Wild4Stone

I think my approach could be a bit easier to understand. Time complexity : O(n*logn^2).

My approach matches with Mike for the beginning.

First create 4 separate prefix sum arrays for 11,01,10,00 types.

For each i from 0 to m, choose i 11-types and then select best (k-i) books of 01 and 10 types in order to fulfill the requirement. So till now we have selected a total of (i + (k-i) + (k-i) = 2k-i) books. We now need m-(2k-i) more books. Let's say this value as X.

So now you need X smallest numbers from the 3 sorted arrays(01,10,00 types)

From here you can just apply a simple binary search to find the Xth smallest number from the 3 sorted arrays of 01,10,00 types and get the indices upto which you must include to get the total X books

Note1: you must apply binary search on the original sorted arrays, NOT the prefix arrays.

Note2: for 01 and 10 types, the starting indices for binary search will be from (k-i) because you have already chosen them before to fulfill the requirement.

Now since you have found the indices(upto which you must have to include) for each array with binary search, you can simply calculate the total sum and compare it with the current minimum.

P.S: implementation could be a bit heavy with this approach

yaswanth

Another solution for E1: I sorted 01, 10, 11 books independently. Now you need to reach k books for both Alice and Bob. So we either have to pick 11 or (a 10 and a 01). We can greedily pick whichever is cheapest. Create a new v10[i] + v01[i] books. Combine v11 books with this new tuple of books, sort them and pick the k smallest values. 85376690

wishcode

please someone explain me this..

Then we need to find two consecutive pairs with the same first values and swap these two elements in the permutation. Because in fact these two numbers are equal in the array and have consecutive values in the permutation, we guaranteed change the parity of number of inversions.

Problem F

Rocky_311

Pls explain why I'm getting WA in testcase2 of problem D. https://mirror.codeforces.com/contest/1374/submission/85355292

Here in your code variable ele is storing the minimum value of all i%k whose if condition is true. lets understand this with an example,
1
3 3
1 2 2
Here d={1: 1, 2: 2} Initially, maxi=0
Firstly, value of i will be 1 and d[1]>maxi i.e 1>0
so, maxi becomes 1 and ele becomes 1.
now, for i=2 condition is true, i.e d[2]>maxi i.e 2>1
so, maxi becomes 2 but ele remains 1 as you are storing minimum value encountered. So, this is wrong as if you change maxi you should change ele accordingly.

you can make it right by using a condition that if maxi==d[i%k] then you should choose the minimum i%k, else you should change the value of ele to current i%k.

            if d[i%k]>=maxi:
                if(maxi==d[i%k]):
                    ele=min(i%k,ele)
                else:
                    ele=i%k
                maxi=d[i%k]

With it your submission gets AC 85494164

Meijer

For anyone having trouble understanding the 1374E2 - Reading Books (hard version) editorial: I think they meant 'but elements of 11-group are not free' instead of 'but elements of 00-group are not free'.

laxsuryavanshi

For problem D, consider the test case n=3, k=7 and a={1, 1, 1}. With this approach the answer would be 21. But we can do it in 7 steps only. The required remainders are {6, 6, 6}. Which can be obtained by 1+5, 2+4 and 6. So array {7, 7, 7} can be obtained in one full cycle only.

kartik8800

You can only perform the add operation at a particular index Atmost once.

If the problem was actually what you interpreted it to be, I guess it would've been much harder.

wery0

-18

E2 is shit!

vivekcrux

Hey guys, if any of you having difficulty in understanding the editorial of problem E1. Here's a video to help you out.
Thank you!

IS THERE ANY PROBLEM WITH THIS CODE FOR PROB B https://mirror.codeforces.com/contest/1374/submission/85385019

BY THE WAY THIS IS AC code

If you not found any problem with your solution.then why you post here your solution for twice.we have editorial..No need your solution for B.

babu1998

Can't understand cyclic shifts sorting. Can someone explain why odd parity fails to give answer ?

Also why in the end two elements wont be sorted?

open_criminal

Let's consider you are doing cyclic shift with permutation a1,a2,a3 then after doing cyclic shift the permutation will be a3,a1,a2 . Now one thing to note here is that the number of inversions done in one cyclic shift is 2(a3 is now before a1 and a2) , so every time we perform cyclic shift, the number of inversions done are increased by two or in another way we can say that we can never swap two numbers therefore if the required number of inversions have an odd parity we can never sort them.

Thanks, also why in the end two elements wont be sorted?

I think that if we have put all the elements till the last third element(in the sorted order) at their correct positions then we won't get last two elements unsorted as if we get the last two elements unsorted than the parity of the number of inversions in that sub problem(that particular state) will be 1(i.e. odd) which cannot happen.

Also as it was not mentioned in the problem that all the numbers are different therefore such a condition may arise when we have two equal numbers. But contradictory if we have equal numbers then i think we might be able to sort even if we have number of inversions with odd parity as:-

Let's consider 1 3 1

The number of inversions is 1 but after one cyclic shift we can actually sort it.

Because two unsorted elements is one inversion, and we cannot get rid of one inversion.

"Then let's just cut off the first element and solve the problem without it. At the end we have only two numbers that can be not sorted and we can check all three possibilities and choose one which is suitable for us (it's always exists because the number of inversions is even)."

Picked this from editorial. What are the three possibilities?

The three possibilities are the three cyclic permutations of the last three elements. 123 -> 123,231,312

The_mysterio

Sir, if you can kindly say what we are going to do if there are duplicate elements in the array? I am unable to understand the editorial. Plz pLz help

I think in that case we should skip checking the parity of the number of inversions and do next step as it is.

If it takes us to a situation in which the last two elements are unsorted then we can check for all the three permutations(cyclic) of the last three elements and if none of them makes the array sorted then there won't be any possible answer.

i_wanna_be_pink

Please Someone Explain Why i am Getting TLE in Test case#5

my submission is : 85516199

try test case, where size of string is 1e6 and every bracket is ')'

Gamechanger

Can someone help me i am getting TLE in D part Here is my submission https://mirror.codeforces.com/contest/1374/submission/85529755 Thanks

try test case t = 1 1 1000000000 999999999

123priyankarai

please help me with my solution for E1. Am getting WA. link

The problem is in this part of your code

for(ll j=x;j<x+k-c;j++)
{
sm=sm+v[x];
}

It must be v[j] instead of v[x]

Please help.I am Getting WA in Problem E2. My code:(https://mirror.codeforces.com/contest/1374/submission/85530060)

Refer to https://mirror.codeforces.com/blog/entry/79517?#comment-652813

0xDkXy

sorry,the code of the solution of E2 have some errors, it can't run in my computer,such as

for (auto [value, position] : st) res.push_back(position);

in the line 119 and

st.erase(prev(st.end()));

in the line 26

could any one help me? thank

Quicksnipe

Can anybody help me? for E2 (reading books hard version). I m getting wrong answer in test case 12 and my answer only differs by 1 from real answer.

my code if https://mirror.codeforces.com/contest/1374/submission/85595106

rahulpahuja

Can anyone help, what I'm doing wrong? I'm getting WA in E2.

My logic for solving this —

Make min heap for all 00, 01, 10, 11.
Get element from 11 or (01 and 10) whoever gives me lowest sum for contributing to k likes.
After repeating step 2 for k times, get element from 00, 01, 10, 11 whichever contributes minimum to sum and repeat this till total books read goes to m.

my submission — 85968003

Thanks in advance!

seeva92

My approach:
First step:
I am greedily allocating the common taste books, followed by remaining books of alice and bob. With this, I am ensuring at-least k-books are included in the list and the time is minimized.

With this, easy version got accepted.

Second step:
If booksRead > m, I am reducing the numbers by replacing the individual taste with the common taste books. If booksRead < m, I am greedily allocating the least time taken book from the remaining entire books available.

It seems that I am missing something in my code. Due to that, the hard version got failed in the test case 12. Here's the submission link: https://mirror.codeforces.com/contest/1374/submission/86028907

Can someone please explain what I am missing in my code?

Could you explain little more on this?

Your program gives the output 5 whereas the optimal output is 4 (take 1, 2).

Rasel

Please help me i am getting TLE in question no. D

My submission : https://mirror.codeforces.com/contest/1374/submission/86383860

I assume it is IO problem. You are doing ios_base::sync_with_stdio(0);cin.tie(0); and then mixing cin and scanf. Try using only one of the IO stacks, or do not disable the sync of both.

ayushgupta_

I am not getting why I am getting wrong answer for problem E. Here is my solution: https://mirror.codeforces.com/contest/1374/submission/86808426

*(For E2)

AvsUmNVipeR

MikeMirzayanov,vovuh
In the problem 1374F - Cyclic Shifts Sorting, is the order of indices for performing the operations fixed?

While performing the greedy algorithm, I chose the maximum element instead and moved it to the last position. Wouldn't that give me a different order of indices?

The solution 86861838 having taken the maximum element isn't being accepted. Please clarify.

If you perform the shift with the triple $$$[p_i, p_{i + 1}, p_{i + 2}]$$$, you need to print the index $$$i$$$, not $$$i+1$$$ and not $$$i+2$$$. Make sure that all indices you print are indices you (and checker) want to see.

qingyuge006

Could someone help my E1 code out? I got TLE at case4. CODE

← Rev. 6 →

Problem D

Why max count always giving the maximum final value of x? (x from problem description).

Because :

say, min possible value with maxCount < max possible value with less than maxCount

which is => (maxCount-1)*k + 1 + 1 < (maxCount-2)*k + (k-1) + 1

=> 2<0 ; Impossible .

Look at this Accepted Code

        for(int i=0; i<n; i++){
            cin>>a[i];
            if(a[i]%k == 0) continue;
            cnt[k-a[i]%k]++;
        }
        lli ans = 0;
        for(auto [key, value] : cnt){
            ans = max(ans, (value-1)*1LL*k + key + 1);
        }

cr7_adi

This works too for problem B

if(n==1) return 0;
		int c{0};
		while(n>1)
		{
			if(n%6==0)
			{
				n=n/6;
			}
			else if(n%2!=0)
			{
				n=n*2;
			}
			else
			{
				return -1;
			}
			c++;
		}
		return c;

Sai_t

I think this is similar to the editoral.

The official editoral just separated 6 into 2 and 3 ,and then count their times respectively.

mrslowmo

3 years ago, # |

Please someone, explain why am I getting Memory Limit in Test Case #5 for Question D

This is my submission: 142601616

yogomate

for problem B why was it (cnt3−cnt2)+cnt3 please anyone explain me i am just a beginner

beethoven97

3 years ago, # ^ |

(cnt3-cnt2) is the extra number of twos you should multiply it by n. after multiplication by twos you should divide n by cnt3 of number 6 to get zero.

NeverCompromise

21 month(s) ago, # |

I really really hated E2 because its a really easy question, but the implementation required is nightmarish.

Anyways, alternate O(n*log^2(n)) solution using two fenwick trees which can be quite easily optimised to O(n*log(n)) using a segment tree (but I'm too lazy to implement it).

Anways, my solution is similar to the editorial in the sense that we iterate over the number of (11's) used and then we use k — (11's) used (01's and 10's). But I use the fenwick trees to simulate this entire process.

This question can also be implemented with indexed multiset but I'm too lazy for that.

21 month(s) ago, # ^ |

Well, for some reason (probably the terrible constant factor due to my shabby implementation), the O(nlogn) solution with a segment tree runs slower than the O(nlog^2n) with fenwick trees.

O(nlogn): https://mirror.codeforces.com/contest/1374/submission/197149916

O(nlog^2n): https://mirror.codeforces.com/contest/1374/submission/197141328

p.cyanide_

11 months ago, # |

Why are some people crazy? Why are they showing up the solution without hiding? There is an editorial. You can make an important contribution by writing a comment that will help someone. Don't ruin anyone's importance. thank you.

vovuh's blog