Разбор Educational Codeforces Round 187

№	Пользователь	Рейтинг
1	Benq	3676
2	Kevin114514	3659
3	jiangly	3640
4	turmax	3450
5	tourist	3382
6	strapple	3360
7	Um_nik	3354
8	squareOf105	3348
9	maroonrk	3312
10	idontwannadothis…e	3191

№	Пользователь	Вклад
1	Qingyu	155
2	nik_exists	151
3	maspy	149
4	AmShZ	145
5	Um_nik	143
6	Errichto	139
7	BledDest	136
8	adamant	134
9	maroonrk	132
10	cry	130

Разбор

Решение (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 - Красивые числа

Идея: BledDest

Разбор

Решение (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 - Генератор тестов

Идея: FelixArg

Разбор

Решение (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 - Игра в делимость

Идея: FelixArg

Разбор

Решение (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 - Вероятностная карточная игра

Идея: BledDest

Разбор

Решение 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;
}

Решение 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 - Бинарный поиск с одним обменом

Идея: BledDest

Разбор

Решение (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;
}

Комментарии (27)

Написать комментарий?

a_frog_named_yossy

8 месяцев назад, скрыть # |

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

→ Ответить

Papaulo

8 месяцев назад, скрыть # ^ |

Yes! You may look at my solution right here: https://codeforces.me/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://codeforces.me/contest/2203/submission/364547623

awesomeguy856

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.

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://codeforces.me/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

adityacf02017

For E sqrt dec it is written Overall complexity: sqrt(m). Is it typo?

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://codeforces.me/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

+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://codeforces.me/contest/2203/submission/364764786

loveisblind

Quite interesting C: when do binary search, we only know the fact that if we can satisfy with n, then n + 1 is also satisfied. But given fixed n, I think of how we ensure that follow the algorithm (go from most significant bit to least significant bit) will ensure a valid solution. Suppose n satisfied with a valid distributions of bit position where m set. Then if then we can always try to transfer lower bit to larger bit as much as when can and the valid state is not changed, this is exactly the same with the algorithm. ~~~~~ bool check(ll cnt, ll s, ll m) { for (int i = BIT — 1; i >= 0; i--) if ((m>>i) & 1) { s -= min(cnt, s / (1ll << i)) * (1ll << i); } return s == 0; } ~~~~~

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.

Aditya_itmo

For Problem D, in solution it is mentioned that when alice is selecting value y from array b, then array a should be of its divisor only. but according to problem statment, least count of divisor should be one. am I not getting problem statement correctly?

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://codeforces.me/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....

SNR2009

3 недели назад, скрыть # |

The given solution for C is amazing! Thank you for the tutorials!

Блог пользователя awoo