Educational Codeforces Round 187 Editorial

#	User	Rating
1	Benq	3792
2	VivaciousAubergine	3647
3	Kevin114514	3603
4	jiangly	3583
5	turmax	3559
6	tourist	3541
7	strapple	3515
8	ksun48	3461
9	dXqwq	3436
10	Otomachi_Una	3413

#	User	Contrib.
1	Qingyu	157
2	adamant	153
3	Um_nik	147
4	Proof_by_QED	146
5	Dominater069	145
6	errorgorn	141
7	cry	139
8	YuukiS	135
9	TheScrasse	134
10	chromate00	133

Tutorial

Solution (BledDest)

t = int(input())
for i in range(t):
    n, m, d = map(int, input().split())
    k = 1 + d // m
    print((n + k - 1) // k)

2203B - Beautiful Numbers

Idea: BledDest

Tutorial

Solution (Neon)

#include <bits/stdc++.h>
 
using namespace std;
 
int main() {
	int t;
	cin >> t;
	while (t--) {
		string s;
		cin >> s;
		int sum = 0;
		vector<int> a;
		for (int i = 0; i < int(s.size()); ++i) {
			int x = s[i] - '0';
			sum += x;
			a.push_back(x - (i == 0));
		}
		sort(a.begin(), a.end());
		int ans = 0;
		while (sum > 9) {
			sum -= a.back();
			a.pop_back();
			++ans;
		}
		cout << ans << '\n';
	}
}

2203C - Test Generator

Idea: FelixArg

Tutorial

Solution (FelixArg)

#include<bits/stdc++.h>
#define int long long
using namespace std;
 
bool get(int x, int a, int lim){
	int f = 0;
	for (int i = 59; i >= 0; i--){
		f <<= 1;
		if (((x >> i) & 1) == 1){
			f++;
		} 
		if (((a >> i) & 1) == 1){
			f -= min(lim, f);
		}
	}
	return (f == 0);
}
 
void solve(){
	int x, a;
	cin >> x >> a;
 
	if (!get(x, a, 1ll << 60)){
		cout << -1 << '\n';
		return;
	}
 
	int l = 0, r = (1ll << 60);
	while(l <= r){
		int m = l + (r - l) / 2;
		if (get(x, a, m)){
			r = m - 1;
		}
		else{
			l = m + 1;
		}
	}
 
	cout << l << '\n';
}
 
signed main()
{
#ifdef FELIX
	auto _clock_start = chrono::high_resolution_clock::now();
#endif
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
 
	int tests = 1;
	cin >> tests;
	for (int test = 0; test < tests; test++){
		solve();
	}
#ifdef FELIX
	cerr << "Executed in " << chrono::duration_cast<chrono::milliseconds>(
		chrono::high_resolution_clock::now()
			- _clock_start).count() << "ms." << endl;
#endif
	return 0;
}

2203D - Divisibility Game

Idea: FelixArg

Tutorial

Solution (FelixArg)

#include <bits/stdc++.h>
 
using namespace std;
 
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	int t;
	cin >> t;
	
	for (int test = 0; test < t; test++){
    	int n, m;
    	cin >> n >> m;
    
    	vector<int> a(n), b(m);
    	for (int i = 0; i < n; i++){
    		cin >> a[i];
    	}
    	for (int i = 0; i < m; i++){
    		cin >> b[i];
    	}
    
    	int max_a = n + m + 1;
    
    	vector<int> cnt_b(max_a, 0), cnt_a(max_a, 0);
    
    	for (int i = 0; i < n; i++){
    		cnt_a[a[i]]++;
    	}
    
    	for (int i = 0; i < m; i++){
    		cnt_b[b[i]]++;
    	}
    
    	vector<int> cnt_del(max_a, 0);
    
    	int f = 0, s = 0, com = 0;
    
    	for (int i = 1; i < max_a; i++){
    		for (int j = i; j < max_a; j += i){
    			cnt_del[j] += cnt_a[i];
    		}
    	}
    
    	for (int i = 1; i < max_a; i++){
    		if (cnt_b[i] == 0){
    			continue;
    		}
    
    		if (cnt_del[i] == 0){
    			s += cnt_b[i];
    		}
    		else if (cnt_del[i] == n){
    			f += cnt_b[i];
    		}
    	}
    
    	com = m - f - s;
    
    	bool turn = 0;
    	string win = "";
    
    	while(1){
    		if (turn == 0){
    			if (com > 0){
    				com--;
    			}
    			else if (f > 0){
    				f--;
    			}
    			else{
    				win = "Bob";
    				break;
    			}
    		}
    		else{
    			if (com > 0){
    				com--;
    			}
    			else if (s > 0){
    				s--;
    			}
    			else{
    				win = "Alice";
    				break;
    			}
    		}
    		turn = !turn;
    	}
    
    	cout << win << '\n';
	}
 
    return 0; 
}

2203E - Probabilistic Card Game

Idea: BledDest

Tutorial

Solution 1 (awoo)

#include <bits/stdc++.h>
#include "ext/pb_ds/assoc_container.hpp"
using namespace __gnu_pbds;
 
#define forn(i, n) for (int i = 0; i < int(n); i++)
 
using namespace std;
 
const int MOD = 998244353;
 
int mul(int a, int b){
	return a * 1ll * b % MOD;
}
 
int binpow(int a, int b){
	int res = 1;
	while (b){
		if (b & 1)
			res = mul(res, a);
		a = mul(a, a);
		b >>= 1;
	}
	return res;
}
 
template <typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
 
int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	int m;
	cin >> m;
	vector<long long> a(m);
	forn(i, m) cin >> a[i];
	auto xs = a;
	sort(xs.begin(), xs.end());
	for (auto& x : a) x = lower_bound(xs.begin(), xs.end(), x) - xs.begin();
 
	vector<long long> f(m);
 
	auto upd = [&](int x, long long val){
		for (int i = x; i < int(f.size()); i |= i + 1)
			f[i] += val;
	};
	auto get = [&](int x){
		long long sum = 0;
		for (int i = x; i >= 0; i = (i & (i + 1)) - 1)
			sum += f[i];
		return sum;
	};
 
	long long sum = 0;
	ordered_set<int> cur;
	for (int x : a){
		cur.insert(x);
		int n = cur.size();
		sum += xs[x];
		upd(x, xs[x]);
 
		if (n < 3) continue;
 
		auto getL = [&](int pos, auto it){
			if (it == cur.begin()) return 0ll;
			return xs[*prev(it)] * 1ll * pos - get(*it - 1);
		};
 
		auto getR = [&](int pos, auto it){
			if (next(it) == cur.end()) return 0ll;
			return (sum - get(*it)) - xs[*next(it)] * 1ll * (n - pos - 1);
		};
 
		int l = 0, r = n - 1;
		int pos = n;
		while (l <= r){
			int m = (l + r) / 2;
			auto it = cur.find_by_order(m);
			if (getL(m, it) >= getR(m, it)){
				pos = m;
				r = m - 1;
			}
			else{
				l = m + 1;
			}
		}
 
		long long ans = 1e18;
		forn(_, 2){
			if (0 <= pos && pos < n){
				auto it = cur.find_by_order(pos);
				ans = min(ans, max(getL(pos, it), getR(pos, it)));
			}
			--pos;
		}
 
		cout << mul(ans % MOD, binpow(n - 2, MOD - 2)) << '\n';
	}
	return 0;
}

Solution 2 (awoo)

#include <bits/stdc++.h>
 
#define forn(i, n) for (int i = 0; i < int(n); i++)
 
using namespace std;
 
const long long INF64 = 1e18;
const int MOD = 998244353;
 
int mul(int a, int b){
	return a * 1ll * b % MOD;
}
 
int binpow(int a, int b){
	int res = 1;
	while (b){
		if (b & 1)
			res = mul(res, a);
		a = mul(a, a);
		b >>= 1;
	}
	return res;
}
 
int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	int m;
	cin >> m;
	vector<long long> a(m);
	int n = m + 2;
	forn(i, m) cin >> a[i];
 
	int p = sqrt(n) + 3;
	auto xs = a;
	xs.push_back(0);
	sort(xs.begin(), xs.end());
	xs.push_back(xs.back() + 1);
	vector<int> cntbl(n), rgh(n, -1);
	rgh[0] = 0;
	rgh[(n - 1) / p] = n - 1;
	vector<long long> sumbl(n);
	vector<int> cll(n, 0), clr(n, n - 1);
 
	set<int> on({0, n - 1});
	int cnt = 0;
	long long sum = 0;
	forn(i, m){
		int x = lower_bound(xs.begin(), xs.end(), a[i]) - xs.begin();
		int bl = x / p;
 
		++cntbl[bl];
		sumbl[bl] += xs[x];
		rgh[bl] = max(rgh[bl], x);
		sum += xs[x];
		++cnt;
 
		auto it = on.lower_bound(x);
		clr[x] = *it;
		cll[x] = *prev(it);
		clr[*prev(it)] = cll[*it] = x;
		on.insert(x);
 
		if (cnt < 3) continue;
 
		int lst = clr[0];
		int cntl = 0;
		long long suml = 0;
 
		auto getL = [&](int x){ return xs[cll[x]] * 1ll * cntl - suml; };
		auto getR = [&](int x){ return (sum - suml - xs[x]) - xs[clr[x]] * 1ll * (cnt - cntl - 1); };
		auto check = [&](int x){
			if (x == 0) return true;
			if (x == n - 1) return false;
			return getL(x) < getR(x);
		};
 
		while (lst < n - 1){
			int bl = lst / p;
			assert(rgh[bl] != -1);
			if (!check(rgh[bl])) break;
			cntl += cntbl[bl];
			suml += sumbl[bl];
			lst = clr[rgh[bl]];
		}
 
		while (lst < n - 1){
			if (!check(lst)) break;
			++cntl;
			suml += xs[lst];
			lst = clr[lst];
		}
 
		x = lst;
		long long ans = 1e18;
		if (x != n - 1)
			ans = min(ans, max(getL(x), getR(x)));
		assert(x != 0);
		x = cll[x];
		if (x != 0){
			--cntl;
			suml -= xs[x];
			ans = min(ans, max(getL(x), getR(x)));
		}
 
		cout << mul(ans % MOD, binpow(cnt - 2, MOD - 2)) << '\n';
	}
	return 0;
}

2203F - Binary Search with One Swap

Idea: BledDest

Tutorial

Solution (BledDest)

#include<bits/stdc++.h>
 
using namespace std;
 
vector<long long> ans;
int n;
vector<int> cnt;
 
void prepare_aux(int l, int r, vector<int>& a)
{
    if(l > r) return;
    int m = (l + r) / 2;
    a[m] = r - l + 1;
    if(l < m) prepare_aux(l, m - 1, a);
    if(m < r) prepare_aux(m + 1, r, a);
}
 
vector<int> prepare(int len)
{
    vector<int> a(len);
    prepare_aux(0, len - 1, a);
    return a;    
}
 
int get_left(int len)
{
    int m = (len - 1) / 2;
    return m;
}
 
int get_right(int len)
{
    int m = (len - 1) / 2;
    return len - m - 1;
}
 
vector<long long> get(int x)
{
    vector<long long> res(x + 1);
    int m = (x - 1) / 2;
    int left = m;
    int right = x - m - 1;
    vector<int> prepared = prepare(x);
    //cout << x << endl;
    // swap m with something to the left
    {
        for(int i = 0; i < m; i++)
        {
            int lost = abs(m - i);
            //cout << i << " " << m << " " << lost << endl;
            res[lost]++;  
        }
    }
    // swap m with something to the right
    {
        for(int i = 0; i < right; i++)
        {
            int lost = i + 1;
            //cout << m << " " << i + m + 1 << " " << lost << endl;
            res[lost]++;
        }
    }
    // swap something to the left with something to the right
    {
        map<int, int> lost_left;
        map<int, int> lost_right;
        for(int i = 0; i < x; i++)
        {
            if(i == m) continue;
            if(i < m)
            {
                int lost = get_right(prepared[i]) + 1;
                lost_left[lost]++; 
            }
            else
            {
                int lost = get_left(prepared[i]) + 1;
                lost_right[lost]++;
            }
        }
        for(auto p : lost_left)
            for(auto p2 : lost_right)
            {
                //cerr << p.first << " " << p.second << endl;
                //cerr << p2.first << " " << p2.second << endl;
                res[p.first + p2.first] += p.second * 1ll * p2.second;
            }
    }
    //cout << x << ":";
    //for(auto y : dp[x]) cout << " " << y;
    //cout << endl;
    return res;
}                    
 
void calc(int l, int r)
{
    if(l > r) return;
    int m = (l + r) / 2;
    if(l < m) calc(l, m - 1);
    if(m < r) calc(m + 1, r);
    int len = r - l + 1;
    cnt[len]++;            
}
 
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;         
    ans.resize(n + 1);
    cnt.resize(n + 1);
    calc(0, n - 1);
    for(int i = 1; i <= n; i++)
        if(cnt[i] != 0)
        {
            auto g = get(i);
            for(int j = 0; j <= i; j++)
                ans[n - j] += cnt[i] * g[j];
        }
    for(auto x : ans) cout << x << " ";
    cout << "\n";
    return 0;
}

Comments (23)

Write comment?

a_frog_named_yossy

2 months ago, hide # |

The time complexity on F is unexpected. Did anyone managed to fit $$$O(n\log(n))$$$?

→ Reply

Papaulo

2 months ago, hide # ^ |

Yes! You may look at my solution right here: https://mirror.codeforces.com/contest/2203/submission/364375556. The code is kinda simple. There are some tricky parts tho, like int s=s1-t;, but the only thing it does is that I traverse the DFS from right to left and left to right, and in one time I want to use < and in the other <=.

I've also done a O(N) version which the code is pretty similar to my N*logN. It's based on the "at most logN different sizes trick" mentioned in the official solution and it's pretty simple. Also, you should note that the sum of different sizes is O(N) and that 2^x*1 + 2^(x-1)*2 + 2^(x-2)*3 + 2^(x-4)*4 = 2^x(1+1/2+1/4+1/8+...)=O(2^x), or in this case O(N). https://mirror.codeforces.com/contest/2203/submission/364547623

awesomeguy856

6 weeks ago, hide # ^ |

You can get O(n) with just using an unordered map

GomerDoGo

← Rev. 2 →

Fun fact: for some reason my solution on D got TL with static arrays and OK with vector… Shouldn’t it be exactly the opposite thing?

The problem was that in your static array version you used maxv=1e6+10, while in your vector code you used n+m+1, which is correct. So I'm guessing you got TL from out of bounds, which already happended to me some time.

with maxv = 2e6+10, I still get TL...

sort(all(backk)); backk.erase(unique(all(backk)), backk.end());

The problem is that you're sorting back, but because of the harmonic sum back's size is O(N*logN), so sorting it is therefore O(N*log²N) which is too heavy for N=10^6 and 2 seconds.

In your vector version, you just check from each number from 1 to n+m, which is way faster.

Also you don't need this back array at all. If you use it only for cleaning it won't cause much damage, bush it will still be a heavy part although I guess not causing TL. I just recommend you cleaning all numbers from 1 to n+m in that case.

7 weeks ago, hide # ^ |

Ohhh, thanks a lot, now I understand where the problem was

Jose_17

It is possible solve E with walking in the segment tree? or i'm hallucinating

Pie_TealCompressorDragon

I thought about this during the contest and I believe it is possible

It is! Look at this O(N*logN) submission: https://mirror.codeforces.com/contest/2203/submission/364393228. I basically replaced the "look for intersection point" logic with ternary search for the minimum point of the maximum value between the two functions, since you can easily proove unimodality. so when I'm at a non-leaf node at function query, I take a look at the value of the rightmost leaf in the left node and the leftmost leaf at the right node. To do this quickly I always store mn, mn2, mx and mx2 which represent the two farthest active leafs to the left and to the right respectively. It was 3x faster than my O(N*log²N) solution. To be honest I didn't expect much better because segment tree recursion is normally heavy, specially in this case with ternary search and a lot of parameters in the query function

dargonburn

Yes

364374302

ankithello20

I appreciate simple explanatory solution of C, Please continue to give the top notch explanation especially for C and D problems in the contest as that's the barrier of most of people. awoo

dpthrough_shits

https://mirror.codeforces.com/contest/2203/submission/364592102

any idea why am I getting TLE on the 41th TC, in problem D

swastiksethi03

Try removing the useless maps and vectors, the constraints are pretty tight.

Dengklek

For problem C editorial, the a0 value is wrong, it should be 49 not 57

terminatorCM

7 weeks ago, hide # |

+11

Fun fact: E can be solved in O(nlogn) because the point the edu is talking about always turns out to be the mean of the elements (because the sum of elements to its right is as close as possible to the sum of elements to its left) we check costl and costr of the element that is less than ceil(mean) (since the mean is not necessarily an integer) and check costl and costr for ceil(mean) https://mirror.codeforces.com/contest/2203/submission/364764786

coordinatebash

D is a very beautiful problem. Thanks to problemsetters for a great contest.

panaceous

For Problem C, as it is mentioned, the final array after moving the set bits to the correct positions, we get

[0,…,0,0,0,4,1,0,0,0,3]

Is it necessary to apply binary search? Cannot we move the bits forward as far as possible, and we will get the maximum ci?

As in the above example, we can move the last position 3 forward, but can move only even bits, so 1 will remainig and instead of 2, we will set 1 at the next position to the left and try to move it to the correct position? Won't this work

I got the solution.

Not sure what is wrong its taking a hell lot of time for a simple s = 13 and m = 5 testcase. I have copied the editorial solution but in java. https://mirror.codeforces.com/contest/2203/submission/365255697

Lol so stupid. I was wrongly incrementing the for loop.

theRealShroomBoy

This C is more complicated than i thought it would be....

awoo's blog