Codeforces Round #598 (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 <iostream>

using namespace std;

int main() {
	int q;
	cin >> q;

	for (int qr = 0; qr < q; ++qr) {
		int a, b, n, s;
		cin >> a >> b >> n >> s;

		if (s % n <= b && 1ll * a * n + b >= s) {
			cout << "YES\n";
		}
		else {
			cout << "NO\n";
		}
	}
}

1256B - Minimize the Permutation

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 q;
	cin >> q;
	for (int i = 0; i < q; ++i) {
		int n;
		cin >> n;
		vector<int> a(n);
		for (int j = 0; j < n; ++j) {
			cin >> a[j];
			--a[j];
		}
		int pos = 0;
		while (pos < n) {
			int nxt = min_element(a.begin() + pos, a.end()) - a.begin();
			int el = a[nxt];
			a.erase(a.begin() + nxt);
			a.insert(a.begin() + pos, el);
			if (pos == nxt) pos = nxt + 1;
			else pos = nxt;
		}
		for (auto it : a) cout << it + 1 << " ";
		cout << endl;
	}
	
	return 0;
}

1256C - Platforms Jumping

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, d;
	cin >> n >> m >> d;
	vector<int> c(m);
	for (int i = 0; i < m; ++i) {
		cin >> c[i];
	}
	
	vector<int> ans(n + 2);
	for (int i = m - 1, pos = n; i >= 0; --i) {
		for (int len = 0; len < c[i]; ++len) {
			ans[pos - len] = i + 1;
		}
		pos -= c[i];
	}
	
	int now = 0;
	while (true) {
		while (now + 1 < n + 1 && ans[now + 1] > 0) ++now;
		if (now + d >= n + 1) break;
		if (ans[now + d] == 0) {
			int lpos = -1;
			for (int i = now + d; i < n + 2; ++i) {
				if (ans[i] != 0) {
					lpos = i;
					break;
				}
			}
			if (lpos == -1) {
				cout << "NO" << endl;
				return 0;
			}
			int rpos = -1;
			for (int i = lpos; i < n + 2; ++i) {
				if (ans[i] == ans[lpos]) rpos = i;
			}
			while (ans[now + d] == 0) {
				swap(ans[lpos - 1], ans[rpos]);
				--lpos, --rpos;
			}
		}
		now += d;
	}
	
	cout << "YES" << endl;
	for (int i = 1; i <= n; ++i) {
		cout << ans[i] << " ";
	}
	cout << endl;
	
	return 0;
}

1256D - Binary String Minimizing

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 q;
	cin >> q;
	while (q--) {
		int n;
		long long k;
		string s;
		cin >> n >> k >> s;
		string res;
		int cnt = 0;
		bool printed = false;
		for (int i = 0; i < n; ++i) {
			if (s[i] == '0') {
				if (cnt <= k) {
					res += '0';
					k -= cnt;
				} else {
					res += string(cnt - k, '1');
					res += '0';
					res += string(k, '1');
					res += s.substr(i + 1);
					cout << res << endl;
					printed = true;
					break;
				}
			} else {
				++cnt;
			}
		}
	
		if (!printed) {
			res += string(cnt, '1');
			cout << res << endl;
		}
	}
	
	return 0;
}

1256E - Yet Another Division Into Teams

Idea: MikeMirzayanov

Tutorial

Solution

#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> pt;

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

const int N = 200043;
const int INF = int(1e9) + 43;

int n;
int dp[N];
int p[N];
pt a[N];
int t[N];

int main() {
    scanf("%d", &n);
    for(int i = 0; i < n; i++)
    {
    	a[i].y = i;
    	scanf("%d", &a[i].x);
    }
    sort(a, a + n);
    for(int i = 1; i <= n; i++)
    {
    	dp[i] = INF;
    	p[i] = -1;
    }
    for(int i = 0; i < n; i++)
    	for(int j = 3; j <= 5 && i + j <= n; j++)
    	{
    		int diff = a[i + j - 1].x - a[i].x;
    		if(dp[i + j] > dp[i] + diff)
    		{
    			p[i + j] = i;
    			dp[i + j] = dp[i] + diff;
    		}
    	}
    int cur = n;
    int cnt = 0;
    while(cur != 0)
    {
    	for(int i = cur - 1; i >= p[cur]; i--)
    		t[a[i].y] = cnt;
    	cnt++;
    	cur = p[cur]; 
    }
    printf("%d %d\n", dp[n], cnt);
    for(int i = 0; i < n; i++)
    {
    	if(i) printf(" ");
    	printf("%d", t[i] + 1); 
    }
    puts("");
    return 0;
}

1256F - Equalizing Two Strings

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 q;
	cin >> q;
	for (int i = 0; i < q; ++i) {
		int n;
		string s, t;
		cin >> n >> s >> t;
		vector<int> cnts(26), cntt(26);
		for (int j = 0; j < n; ++j) {
			++cnts[s[j] - 'a'];
			++cntt[t[j] - 'a'];
		}
		bool ok = true;
		bool good = false;
		for (int j = 0; j < 26; ++j) {
			ok &= cnts[j] == cntt[j];
			good |= cnts[j] > 1;
		}
		if (!ok) {
			cout << "NO" << endl;
			continue;
		}
		if (good) {
			cout << "YES" << endl;
			continue;
		}
		int invs = 0, invt = 0;
		for (int l = 0; l < n; ++l) {
			for (int r = 0; r < l; ++r) {
				invs += s[l] > s[r];
				invt += t[l] > t[r];
			}
		}
		ok &= (invs & 1) == (invt & 1);
		if (ok) cout << "YES" << endl;
		else cout << "NO" << endl;
	}
	
	return 0;
}

int len = 0;int temp = 0; for (int i = 5; i < n; i++) { if(dp[i - 3].first + wd[i].first - wd[i - 2].first < dp[i - 4].first + wd[i].first - wd[i - 3].first) { len = 3; temp = dp[i - 3].first + wd[i].first - wd[i - 2].first;} else { len = 4; temp = dp[i - 4].first + wd[i].first - wd[i - 3].first;} if(temp > dp[i - 5].first + wd[i].first - wd[i - 4].first) { len = 5; temp = dp[i - 5].first + wd[i].first - wd[i - 4].first;} dp[i].first = temp; dp[i].second = len; }

Comments (55)

Show archived | Write comment?

Hemengjie

5 years ago, # |

For Problem C,I imimplemented in O(n). 64249894

Main idea is like the tutorial:First place the platform as rightmost as we can ,if the rest positions can't place later platforms,we need move current platform to left.Maybe I am lucky enough to pass all tests.

→ Reply

prakhar_111

+34

Very Greedy Contest.

zarif_2002

C in O(n). It's just placing the platforms leftmost you can at first. Got hacked for a simple mistake unfortunately. here 64283716

r57shell

← Rev. 6 →

My solution for C is very simple $$$O(n)$$$ 64233289 Idea is following:

Set positions of all platforms with space in between exactly $$$d-1$$$. Just don't care about width of river.
Now, if beginning of next "virtual" platform is $$$n+1$$$ or greater, then answer is YES otherwise is NO.
Last step, we need to pack all platforms back into river. It's very easy to do. Let $$$n+1$$$ to be beginning of "virtual" platform, now iterate over all platforms from the last to the first, and if the platform overlap "virtual" platform, them align end of the platform to beginning of virtual platform. Now, set virtual platform to be this aligned (or not) platform and continue.

barun511

5 years ago, # ^ |

This is awesome, thank you!

Dedalius

-6

This is Python, Python is a very dangerous language, none of my colleagues think well of it

loochek

Python is so dangerous that it will kill you at night

spookywooky

No risk no fun

decoder__

4 years ago, # ^ |

Can you explain the last step more elaborately?

I'll provide example. If n = 17 and last platform after first step is starting from position 20 and has width 4, then its last position where you could stand is 22, and it much greater than start of virtual platform at 17+1. So you need to align it so last position where you could stand on this platform is 17 (right next to virtual platform). Because it has width 4 then you need to put it at position 14. Now this is new virtual platform. Suppose platform before it is at position 12 and width 7. Then its last position where you could stand is 18. It's greater than 13, so you need to align it so it would end at 13. You move it to position 7.

Great Explantion.

Are you open to mentoring people?

you don't need mentor if you follow this short guide https://codeforces.net/blog/entry/80268#comment-664467

I'm open to answering questions, but only if I have spare time.

← Rev. 2 →

+10

I think there is missing part of editorial for F.

Regarding case when all characters in both strings are distinct. Suppose that there is way to make them equal. It means, that if you apply all operations for first string instead of doing them simultaneously, and then apply all operations on the first string that was supposed for the second string in reverse order, you should get second string. In other words, steps to make the second string from the first string is: operations of first string in normal order plus operations on second string in reverse order. But count operations of same length is even, because each simultaneous operation produce two operation of same length. Thus, you need to change parity even times, which means no parity change is possible.

What I don't understand though, is how you can prove that you always can do that when parity is same. All I did is prove that you can't make it if parity is different.

Spheniscine

If the parity is the same, you can always do a swap twice in the same position in one string (making a no-op), while making two arbitrary swaps in the other.

actually we can run a bubble sort algorithm in the case of distinct characters and count how many swap you needed to do. Let's say swap counts are p and q. if p and q has same parity, then we can perform (p -q) operation extra in the first string(let's say p > q). and we would do every operation twice in an interval to make the sorted string unchanged. if we have same parity, we can do that. else, we can't as we need to perform one last operation only once and that would change the sorted string.

Sorry for my poor english.

Parity of swap count is changing. I didn't got this task during contest only because of that. After contest I've changed swaps count into inversions count and got AC. So, something is tricky there about it.

Every swap changes the number of inversions by one. So they have same parity.

Oh! Thanks, indeed. I found mistake. It was == 64254819 instead of = 64352150. So, I lost AC just because of that :)

inszva

Thank you for sharing~

svkrdj

In problem E, Why the maximum size of a team is 5??

+13

For example，after sort we have a team: a1 a2 a3 a4 a5 a6

if divide them in one team the diff is a6-a1

if we divide them in two team the diff is a3-a1 + a6-a4

as you know,a3<=a4 so the later diff is better.

if team size is 6 then you can split it into two. Thus minimize the ans.

Ohuefmi

it's hard to see when you have 11 correct hacks ( for the first time ) but still no hacking leaderboard vovuh

yashpal07

from the solution of[problem:1256D] problem D can anyone explain what we do if s[i]=='0' but k<cnt?

emrey

We will move the zero to the left as far as possible. Briefly we will swap it with the character to the left k times.

anupamshah_

what does cnt denote ?

Ib-rabbit

For question A, why do we need to do S % n? I mean what would we get by doing this? I know it would be quite basic but still, I didn't get it. Thanks in advance

$$$S\ \%\ n$$$ = the amount of 1-value coins you need to get the exact number. Like, imagine if $$$S = 54$$$ and $$$n = 10$$$, that's like needing to make 54 cents out of 10-cent coins; you can't unless you have at least 4 1-cent coins.

Why shouldn't we must be having atleast s/n coins of type 'n' also a condition?

Because you can always replace one $$$n$$$-value coin with $$$n$$$ one-value coins, so long as you have enough money in the first place.

stealth003

12 days ago, # ^ |

but in solution author is not checking this condition

Anish1712

I can't understand Then let's sort the second string also by swapping adjacent characters but choose the pair of adjacent equal characters in the first string (it always exists because the first string is already sorted). for problem F.

SuperMo

3 months ago, # ^ |

I know this is old, but I'll write this comment in case anyone upsolving F in the future struggles like I did. What the editorial is trying to say is this:

Just sort s by swapping adjacent elements, and while doing so, you can choose any arbitrary operation of the same size in string t. It doesn’t matter if we mess up t right now, because the focus is on sorting s.

Once s is sorted and t is not, you can start sorting t by swapping adjacent elements. While doing this, the operation for string s will always be swapping any two adjacent equal characters, which won’t change anything in s.

Ozymandias

You can solve E with segment tree & DP,but just DP solution is way more easier.

I think Problem B can be solved in $$$O(n)$$$, it's too late at night to code it though

← Rev. 8 →

Here's my code for $$$O(n)$$$: 64340316

Explanation

Mohd.

Here is O(n) solution for problem C: 64232235

Approach

fdironia

$$$O(n)$$$ solution for C: I didn't put the board greedily. I tried to break the gaps between the boards evenly.

My Submission: 64221433

mohanraghug

In problem F, How does one get an idea to consider the parity of inversions ? I mean it is not at all obvious to me . If this is a popular idea , can someone give some problems related to it ?

towrist

Yes, it is a well-known trick. You should definitely learn it.

986B - Petr and Permutations A very nice problem

In problem E , how would we approach if we have to minimise the number of teams as well?

You would combine all consecutive teams into one team where it does not make a difference in the diversity. ie the ones where the score of the highest member of the team is one less than the score of the lowest member of the next team.

qmzzrdjhwhctrl

In problem E. help help me... My code is a little different from the offcial solution, but I think they are roughyly the same. However, it is TLE. Here is the central part of my code.

for(int i = 2; i < min(5, n); i++) { dp[i].first = wd[i].first — wd[0].first; dp[i].second = i + 1; }

asklvd

I got a detailed prove for F. Regarding　case where the characters of both string are distinct. let's consider the pair in string a, a(i) > a(j) and i<j, and there are t characters between them, so it's easy to know that we need 2*t+1 times swap to get a(i) and a(j) swap while keeping others unchanged(t+1 for a(i) to reach j, t times for a(j) to reach i), so the cost is always odd. if we have parity of the number of inversions odd in both string, then we can say both need odd times to get the string sorted, and the difference between two times if even, also we can always do even times adjacent swap and keep string unchanged, finally two strings become the same. and so the even situation.

TouchMe

← Rev. 3 →

for the problem B the first testcase is $$$[5 4 1 3 2]$$$

My approach is:

$$$[5, 4, 1, 3, 2]$$$ $$$[5, 1, 4, 3, 2]$$$ $$$[1, 5, 4, 3, 2]$$$ $$$[1, 5, 3, 4, 2]$$$ $$$[1, 3, 5, 4, 2]$$$

and the answer is [1, 5, 2, 4, 3], but clearly my answer is lexicograhically smaller, so anyone can tell me where is the problem?

singhpriyank

It is mentioned that for a particular index i you can swap only once. For i=2 you can swap (4,1) after that you cannot swap number at position i=2. i.e.(5,3)

Second paragraph of question: " You can perform at most n−1 operations with the given permutation (it is possible that you don't perform any operations at all). The i-th operation allows you to swap elements of the given permutation on positions i and i+1. Each operation can be performed at most once. The operations can be performed in arbitrary order. "

I see，thanks！

HadyKo

a more general solution for E:

sort by skill
let dp[i] = minimum diversity that we can do starting at index i
then dp[i] = min(dp[k+1] + a[k] − a[i]) for all k, such that i + 2 <= k <= n − 4
since a[i] is independent of k, dp[i] = − a[i] + min(dp[k+1] + a[k]) for all k, such that i + 2 <= k <= n − 4

if we want to implement this it would take o(n^2), but we can notice something by looking at dp[i + 1]

dp[i+1] = − a[i + 1] + min(dp[k + 1] + a[k]) for all k such that i + 3 <= k <= n − 4

thus dp[i] = − a[i] + min(a[i + 1] + dp[i + 1], a[i + 2] + dp[i + 3])

the idea is that dp[i+1] would already have the minimum for all k >= i + 3, so we only need to test for k = i + 2 and then compare it with dp[i +1] + a[i + 1]

mth1908

Can someone explain why my solution failed on test case 2? https://codeforces.net/contest/1256/submission/65338281

ahmad_alghadban

In problem B why i can't start by swapping 1 to arrive to the beginning of array then swap 2 to the nearest index can be reached then 3 and so on... Why i have to move the largest element to the end of array starting with (n-1)th (move if i can) and finish with 1st element.

What is the difference between tow processes.

rr459595

How is my naive dp solution of time complexity O(nmd) (approx 10^9 operations) passing all test cases of problem C ? 70828229

helewrer3

Can anyone tell me how is problem B different from problem D? I mean, aren't just we minimizing the given sequence in both of the problems?

For problem B, all I did was to first loop through the array from right to left (from n-2 to 0) swapping all elements where, a[i] > a[i+1], and then, once again from left to right (from 0 to n-2), doing the same operation, but making sure that the "i" was not repeated when going through the loop the second time, this can be done by maintaining a map.

However, this approach for problem D turned out to be wrong when I ran it on my local machine, is it because of the restriction of "k" ?

Sorry for my bad English.

Mani

Problem C is can be done in O(n) and without needing terrible implementation, here is my submission 83591516 , just think about gaps, there are n-(summation of all plank lengths) gaps, and places=m+1 positions to fill them ( each side of a plank), now lets say we are going to place k=gaps/places zeroes contigously, we need to take care of rem gaps%places as well...

_pastor_

in editorial it says dp for E is so standard tho i can't understand it :||

MostafaM.Galal

16 months ago, # |

is there a binary solution for problem E?

vovuh's blog