Educational Codeforces Round 51 Editorial

#	User	Rating
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

#	User	Contrib.
1	cry	167
2	Um_nik	163
3	maomao90	162
3	atcoder_official	162
5	adamant	159
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	Dominater069	153
9	nor	153

Tutorial

Solution (Ajosteen)


#include <bits/stdc++.h>

using namespace std;

string s;

bool ok(string t){
    int msk = 0;
    
    for(int i = 0; i < int(t.size()); ++i){
	    if(isupper(t[i])) msk |= 1;
	    if(islower(t[i])) msk |= 2;
	    if(isdigit(t[i])) msk |= 4;
	}
	
	return msk == 7;
}

int main() {
	//freopen("input.txt", "r", stdin);
	int t;
	cin >> t;
	for(int i = 0; i < t; ++i){
    	cin >> s;
    	if(ok(s)){
    	    cout << s << endl;
    	    continue;
    	}
    	bool fnd = false;
        for(int i = 0; i < int(s.size()); ++i){
            string t = s;
            
            t[i] = '1';
            if(ok(t)){
    	        cout << t << endl;
    	        fnd = true;
    	        break;
    	    }
            t[i] = 'a';
            if(ok(t)){
    	        cout << t << endl;
    	        fnd = true;
    	        break;
    	    }
    	    t[i] = 'A';
            if(ok(t)){
    	        cout << t << endl;
    	        fnd = true;
    	        break;
    	    }
        }
    	
    	if(fnd) continue;
    	
    	if(isupper(s[2])){
    	    s[0] = 'a';
    	    s[1] = '1';
    	    cout << s << endl;
    	    continue;
    	}
    	if(islower(s[2])){
    	    s[0] = 'A';
    	    s[1] = '1';
    	    cout << s << endl;
    	    continue;
    	}
    	if(isdigit(s[2])){
    	    s[0] = 'a';
    	    s[1] = 'A';
    	    cout << s << endl;
    	    continue;
    	}
	}
	return  0;
}

1051B - Relatively Prime Pairs

Tutorial

Solution (PikMike)

#include <bits/stdc++.h>

using namespace std;

#define forn(i, n) for(int i = 0; i < int(n); i++) 

int main() {
	long long l, r;
	scanf("%lld%lld", &l, &r);
	puts("YES");
	forn(i, (r - l) / 2 + 1)
		printf("%lld %lld\n", l + i * 2, l + i * 2 + 1);
}

1051C - Vasya and Multisets

Tutorial

Solution (Ajosteen)


#include <bits/stdc++.h>

using namespace std;

const int N = 109;

int n;
int a[N];
map<int, int> m;
set <int> s[2];

int main() {
	int n;
	cin >> n;
	for(int i = 0; i < n; ++i){
		cin >> a[i];
		m[a[i]]++;
	}

	int pos = 0;
	for(auto p : m)
		if(p.second == 1){
			s[pos].insert(p.first);
			pos = 1 - pos;
		}
		
	if(s[0].size() == s[1].size()){
		string res(n, 'A');
		for(int i = 0; i < n; ++i)
			if(s[1].count(a[i]))
				res[i] = 'B';
		
		cout << "YES" << endl;
		for(auto c : res) cout << c;
		cout << endl;
		return 0;
	}
	else{
		assert(int(s[0].size()) - 1 == int(s[1].size()));
		string res(n, 'A');
		for(int i = 0; i < n; ++i)
			if(s[1].count(a[i]))
				res[i] = 'B';
		
		int id = -1;
		for(auto p : m)
			if(p.second >= 3){
				id = p.first;
				break;
			}
			
		if(id == -1){
			cout << "NO" << endl;
			return 0;
		}
		
		bool flag = false;
		for(int i = 0; i < n; ++i){
			if(a[i] == id)
				if(!flag){
					flag = true;
					res[i] = 'B';
				}
		}
		
		cout << "YES" << endl;
		for(auto c : res) cout << c;
		cout << endl;
		return 0;
	}
	return 0;
}

1051D - Bicolorings

Tutorial

Solution (PikMike)


#include <bits/stdc++.h>

using namespace std;

#define forn(i, n) for(int i = 0; i < int(n); i++) 

const int N = 1000 + 7;
const int MOD = 998244353;

int dp[N][2 * N][4];

int add(int a, int b){
	return (a + b) % MOD;
}

bool full(int mask){
	return (mask == 0 || mask == 3);
}

int get(int mask, int nmask){
	int cnt = __builtin_popcount(mask ^ nmask);
	if (cnt == 0) return 0;
	if (cnt == 2) return (full(mask) ? 1 : 2);
	return (full(mask) ? 0 : 1);
}

int main() {
	int n, k;
	scanf("%d%d", &n, &k);
	forn(i, 4)
		dp[1][0][i] = 1;
	
	for (int i = 1; i < n; ++i){
		forn(j, k + 1){
			forn(mask, 4){
				forn(nmask, 4){
					dp[i + 1][j + get(mask, nmask)][nmask] = add(dp[i + 1][j + get(mask, nmask)][nmask], dp[i][j][mask]);
				}
			}
		}
	}
	
	int ans = 0;
	forn(mask, 4){
		int nw = get(mask, mask ^ 3);
		if (k >= nw)
			ans = add(ans, dp[n][k - nw][mask]);
	}
	
	printf("%d\n", ans);
}

1051E - Vasya and Big Integers

Tutorial

Solution (Ajosteen)

#include<bits/stdc++.h>

using namespace std;

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

const int N = int(1e6) + 9;
const int MOD = 998244353;

int n;
string s, l, r;
int dp[N];
int sumDP[N];

int sum(int a, int b){
	a += b;
	if(a >= MOD) a -= MOD;
	return a;
}

vector <int> z_function(string s){
	int n = sz(s);
	vector <int> z(n);
	for(int i = 1, l = 0, r = 0; i < n; ++i){
		if(i <= r)
			z[i] = min(r - i + 1, z[i - l]);
		while(i + z[i] < n && s[z[i]] == s[i + z[i]])
			++z[i];
		if(i + z[i] - 1 > r)
			l = i,  r = i + z[i] - 1;
	}
	return z;
}

//s[pos..] ? t
char cmp(vector <int> &zf, string &t, int pos){
	int len = sz(t);
	assert(pos + len + 1 < sz(zf));
	if(sz(s) - pos < len) return '<';
	
	int x = zf[len + 1 + pos];
	assert(x <= len);
	if(x == len) return '=';
	assert(pos + x < sz(s));
	assert(s[pos + x] != t[x]);
	if(s[pos + x] < t[x]) return '<';
	return '>';
}

int main() {
	//freopen("input.txt", "r", stdin);
	
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
	cin >> s >> l >> r;
	n = int(s.size());
	vector <int> zl = z_function(l + "#" + s);
	vector <int> zr = z_function(r + "#" + s);
	
	sumDP[n] = dp[n] = 1;
	for(int i = n - 1; i >= 0; --i){
		if(s[i] == '0'){
			if(l == "0") dp[i] = dp[i + 1];		
			else dp[i] = 0;
			sumDP[i] = sum(dp[i], sumDP[i + 1]);
			continue;
		}
		
		int L = sz(l) + i;
		char cl = cmp(zl, l, i);
		if(cl == '<') ++L;
		
		int R = sz(r) + i;
		char cr = cmp(zr, r, i);
		if(cr == '>') --R;

	 	int cur = 0;
	 	if(L <= R && L <= n){
	 		R = min(R, n);
	 		cur = sumDP[L];
	 		if(R != n) cur = sum(cur, MOD - sumDP[R + 1]);
	 	}
	 	dp[i] = cur;
	 	sumDP[i] = sum(dp[i], sumDP[i + 1]);
	}
	
	cout << dp[0] << endl;
	return 0;
}

1051F - The Shortest Statement

Tutorial

Solution (Ajosteen)

#include <bits/stdc++.h>

using namespace std;

const int N = 300 * 1000 + 9;
const int LOGN = 19;
const int M = 21;
const long long INF64 = 1e18;

int n, m, q;
vector <pair<int, int> > g[N];
int p[LOGN][N];
int tin[N], tout[N], T;
long long h[N];
set <pair<int, int> > badEdges;
long long d[M + M][N];
bool u[N];

void dfs(int v, int pr){
	tin[v] = T++;
	p[0][v] = pr;
	u[v] = true;
	for(int i = 1; i < LOGN; ++i)
		p[i][v] = p[i - 1][ p[i - 1][v] ];
		
	for(auto e : g[v]){
		int to = e.first, len = e.second;
		if(!u[to]){
			h[to] = h[v] + len;
			dfs(to, v);
			
			if(v < to)
				badEdges.erase(make_pair(v, to));
			else
				badEdges.erase(make_pair(to, v));			
		}
	}	
		
	tout[v] = T;
}

bool isAncestor(int a, int b){
	return tin[a] <= tin[b] && tout[a] >= tout[b];
}

int getLCA(int a, int b){
	if(isAncestor(a, b)) return a;
	if(isAncestor(b, a)) return b;
	
	for(int i = LOGN - 1; i >= 0; --i)
		if(!isAncestor(p[i][a], b))
			a = p[i][a];
	
	return p[0][a];
}

void dij(int st, long long d[N]){
	set<pair<long long, int> > q;
	for(int i = 0; i < n; ++i) d[i] = INF64;
	d[st] = 0;
	q.insert(make_pair(d[st], st));
	
	while(!q.empty()){
		int v = q.begin()->second;
		q.erase(q.begin());
		
		for(auto e : g[v]){
			int to = e.first, len = e.second;
			if(d[to] > d[v] + len){
				q.erase(make_pair(d[to], to));
				d[to] = d[v] + len;
				q.insert(make_pair(d[to], to));
			}
		}
	}
}

int main() {
	//freopen("input.txt", "r", stdin);
	
	scanf("%d %d", &n, &m);
    for(int i = 0; i < m; ++i){
    	int u, v, w;
    	scanf("%d %d %d", &u, &v, &w);
    	--u, --v;
    	g[u].push_back(make_pair(v, w));
       	g[v].push_back(make_pair(u, w));
    }
	
    for(int v = 0; v < n; ++v)
    	for(auto e : g[v])
    		if(v < e.first)
    			badEdges.insert(make_pair(v, e.first));

    dfs(0, 0);

    int cpos = 0;
    for(auto e : badEdges)
    	dij(e.first, d[cpos++]);
    scanf("%d", &q);
    for(int tc = 0; tc < q; ++tc){
    	int u, v;
    	scanf("%d %d", &u, &v);
    	--u, --v;
    	int lca = getLCA(u, v);
    	long long ans = h[u] + h[v] - 2 * h[lca];
    	for(int i = 0; i < badEdges.size(); ++i)
    		ans = min(ans, d[i][u] + d[i][v]);
    		
    	printf("%lld\n", ans);
    }	
    return 0;
}

1051G - Distinctification

Tutorial

Solution (BledDest)

#include <bits/stdc++.h>

using namespace std;

#define x first
#define y second

typedef long long li;

mt19937 rnd(time(NULL));

struct node
{
	int x;
	int y;
	li sum;
	int siz;
	node* l;
	node* r;
	node() {};
	node(int x, int y, li sum, int siz, node* l, node* r) : x(x), y(y), sum(sum), siz(siz), l(l), r(r) {};
};

typedef node* treap;
typedef pair<treap, treap> ptt;

int getSiz(treap t)
{
	return (t ? t->siz : 0);
}

li getSum(treap t)
{
	return (t ? t->sum : 0);
}

treap fix(treap t)
{
	if(!t) return t;
	t->sum = getSum(t->l) + t->x + getSum(t->r);
	t->siz = getSiz(t->l) + 1 + getSiz(t->r);
	return t;
}

ptt split(treap t, int l)
{
	t = fix(t);
	if(!t) return make_pair(t, t);
	if(t->x < l)
	{
		auto z = split(t->r, l);
		t->r = z.x;
		return make_pair(fix(t), z.y);
	}
	else
	{
		auto z = split(t->l, l);
		t->l = z.y;
		return make_pair(z.x, fix(t));
	}
}

treap merge(treap a, treap b)
{
	a = fix(a);
	b = fix(b);
	if(!a) return b;
	if(!b) return a;
	if(a->y > b->y)
	{
		a->r = merge(a->r, b);
		return fix(a);
	}
	else
	{
		b->l = merge(a, b->l);
		return fix(b);
	}
}

struct comp
{
	li cur_sum;
	int beg;
	li treap_sum;
	treap t;
	
	void upd()
	{
		cur_sum = treap_sum + beg * 1ll * getSum(t);
	}
	
	void insert(int bi)
	{
		ptt p = split(t, bi);
		treap_sum += getSum(p.x) + getSiz(p.y) * 1ll * bi;
		t = merge(p.x, merge(new node(bi, rnd(), bi, 1, NULL, NULL), p.y));
		upd();
	}
	
	void fill_treap(treap t)
	{
		if(!t) return;
		insert(t->x);
		fill_treap(t->l);
		fill_treap(t->r);
	}
};

comp merge(comp a, comp b)
{
	if(getSiz(a.t) < getSiz(b.t))
		swap(a, b);
	a.beg = min(a.beg, b.beg);
	a.fill_treap(b.t);
	delete b.t;
	a.upd();
	return a;
}

set<int> free_pos;

const int N = 400043;

int p[N];
int siz[N];
comp cc[N];

li start_sum = 0;
li end_sum = 0;

int get(int x)
{
	return (p[x] == x ? x : (p[x] = get(p[x])));
}

void merge(int x, int y)
{
	x = get(x);
	y = get(y);
	if(x == y) return;
	if(siz[x] < siz[y]) swap(x, y);
	end_sum -= cc[x].cur_sum;
	end_sum -= cc[y].cur_sum;
	p[y] = x;
	siz[x] += siz[y];
	cc[x] = merge(cc[x], cc[y]);
	end_sum += cc[x].cur_sum;
}

void process(int ai, int bi)
{
	start_sum += ai * 1ll * bi;
	int pos = *free_pos.lower_bound(ai);
	free_pos.erase(pos);
	siz[pos] = 1;
	p[pos] = pos;
	cc[pos].beg = pos;
	cc[pos].insert(bi);
	end_sum += cc[pos].cur_sum;
	if(!free_pos.count(pos - 1))
		merge(pos, pos - 1);
	if(!free_pos.count(pos + 1))
		merge(pos, pos + 1);
	printf("%lld\n", end_sum - start_sum);
}

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif
    int n;
    scanf("%d", &n);
  	for(int i = 0; i < N; i++)
  		free_pos.insert(i);
	for(int i = 0; i < n; i++)
	{
		int a, b;
		scanf("%d %d", &a, &b);
		process(a, b);
    }
    return 0;
}

int get(int mask, int nmask){ int cnt = __builtin_popcount(mask ^ nmask); if (cnt == 0) return 0; if (cnt == 2) return (full(mask) ? 1 : 2); // Please explain this return statementt, based on your code, it should //be: return (full(mask) ? 1 : 0); return (full(mask) ? 0 : 1); }

import java.util.*; public class Main{ public static void main(String args[]){ Scanner sc=new Scanner(System.in); int mod=998244353; int n=sc.nextInt(),k=sc.nextInt(); long ans[][][]=new long[n][4][k+5]; //one number condition ans[0][0][1]=1; ans[0][1][2]=1; ans[0][2][2]=1; ans[0][3][1]=1; //then multiple number condition for(int i=1;i<n;i++){ for(int j=1;j<=k;j++){ ans[i][0][j]=(ans[i-1][0][j]+ans[i-1][1][j]+ans[i-1][2][j]+ans[i-1][3][j-1])%mod; ans[i][1][j]=(ans[i-1][0][j-1]+ans[i-1][1][j]+ans[i-1][3][j-1]+(j>1?ans[i-1][2][j-2]:0))%mod; ans[i][2][j]=(ans[i-1][0][j-1]+ans[i-1][3][j-1]+ans[i-1][2][j]+(j>1?ans[i-1][1][j-2]:0))%mod; ans[i][3][j]=(ans[i-1][3][j]+ans[i-1][1][j]+ans[i-1][2][j]+ans[i-1][0][j-1])%mod; } } System.out.print((ans[n-1][0][k]+ans[n-1][1][k]+ans[n-1][2][k]+ans[n-1][3][k])%mod); } }

Comments (40)

Show archived | Write comment?

quid_ditch

6 years ago, # |

It should be "If k is odd" in editorial of problem C

→ Reply

BledDest

6 years ago, # ^ |

It will be fixed in a few minutes. Thank you!

mkmkl93

In solution for E it should be a_x + 1

BRCode

Why does my C WA?

http://codeforces.net/contest/1051/submission/43144963

axe98

Same. http://codeforces.net/contest/1051/submission/43262138 In even case, I just print A or B, changing them when 'nice' number found. I get WA. I can't understand why it happens. Please explain someone.

adityaaaaaaaaaaaaaaa

← Rev. 3 →

Can anyone explain why the last coloumn won't contain the answer and how are we calculating final answer(why are we xoring with 3)?

ghoshsai5000

Hi there,

I think you are talking about problem D.

Well, the explanation skipped a step.

BB — 00 BW — 01 WB — 10 WW — 11

This is what the numbers mean.

The number of new components can be easier to understand in my code here. Let me know if you have any doubts or require further explanation. :)

9aminul

please , would you like to explain with 1 ,2,3 test case

NilakshiRocks thanks a lot ! I"m glad I could help :)

9aminul Please read my explanation here and let me know if you have any doubts. :)

shivam_jain

thanks a lot

Gods_Own

8 months ago, # ^ |

[user:ghoshsai5000]Can you please why for this case you are returning 1

W B W B

And for below case returning 0 W W W W

Oom

5 years ago, # ^ |

Hi ghoshsai5000, Thanks for simplifyinh things.could you help me with one doubt on author's editorial:

If you can explainn this by any example, that would be great. Thanks :)

Hi,

Being honest, I didn't understand the editorial code completely. That's why I clearly elaborated all 16 cases in my code with understandable variable names to make the logic extremely clear :)

professor_kumar

3 months ago, # ^ |

← Rev. 2 →

yes you are correct it would be :

return (full(mask) ? 1 : 0);

eg: 
i i+1
1 1
0 0

advitiyabrijesh

Proof of complexity of F?

roll_no_1

Assume M = O(N), since M <= N + 21. Then, the complexity will be something like O((21*N*lg N + Q * (lg N + 21)). Since the preprocessing part for LCA takes O(N lg N) time and no more than O(N) edges will be erased from the set. We run dijkstra (O(N lg N)) from no more than 21 vertices = O(21*N lg(N)) and for every query we find the lca in O(lg N) and then iterate over all atmost 21 bad vertices to compute each distance in a O(1) time.

barni120400

Here's my code for problem F, I'm not sure why I get WA on test 3 everything seems ok to me. can someone please explain my mistake? 43225756

found it, thank's anyway

15520512

In problem C, i found test case 6 1 1 1 2 2 2 that your solution print A A A A A A, can you recheck it ?

RayPatterson

It's the correct output though?

Hacheylight

Why didn't CodeForces evaluate the code? What's wrong?

tmwilliamlin168

+22

We can use a type of mergeable segment tree to solve problem G, with O(nlogn) nodes created overall, so the time complexity is O(nlogn).

http://codeforces.net/contest/1051/submission/43232839

oToToT

Are there any material to learn mergeable segment tree?

soul_voyage

http://codeforces.net/blog/entry/49446

+13

This is an example (with some extra functions): https://codeforces.net/blog/entry/49446

This problem also uses it: https://www.hackerearth.com/practice/data-structures/advanced-data-structures/segment-trees/practice-problems/algorithm/replace-27c5286c/

Jety

Can someone explain the Question D. Thanks!

AZ01

Hard to understand Problem D. Can anyone Suggest me some good Editorial.

SJ151

In problem D like the editorial says dp[i][j][mask] be the number of beautiful bicolorings of the first i columns such that j components are already created and can't be modified and the colors of the i-th column are determined by mask. I didn't understand what does mask mean, like what does dp[2][4][0] mean. I wanted to know that ,like dp[2][4][0] mean number of beautiful bicolorings of the first 2 coulmns such that 4 components are already visited , now what does 0 mean here. Someone please explain.

jrarias

Set dp[n][k][mask] as the number of ways with n columns, k components, ending with mask in the n-th column. You can end up in 4 ways: white-white, white-black, black-white, black-black (that's the meaning of the mask having the values 00, 01, 10, 11). After this, try to figure it out the dp transitions by yourself. Good luck

Thanks a lot

code_report

Video solution with explanation: https://youtu.be/lSyQQ1T6iQ8

Dee_code

hey can someone tell me what's the wrong with this code for problem C ? link — http://codeforces.net/contest/1051/submission/43270735 thanks in advance.....

silxi

Can someone help me out with what is test 67 on problem E or why my code is going wrong?

43274362

Sorry, after thinking I realized I was just running into anti-hash tests. I was lazy and chose 998244353 as my hashing prime, and the same code AC with 1e9+9.

I advise you to use double MODs because if this submission was in a contest anyone can hack you.

dahao

My submission in "E — Vasya and Big Integers" was TLE, can anyone help me?

http://codeforces.net/contest/1051/submission/43280760

bestin_1

Well, without the O(n) strlen calls everywhere its only WA on Test 36.

https://codeforces.net/contest/1051/submission/43414241

Thank you! I realize that strlen calls are waste of time.

ArthurQ

5 years ago, # |

+10

There's an even faster solution for problem D.

Let $$$ww[i][j]$$$ denote the number of $$$2 \times i$$$ grids that end with a column of (two) white squares and have $$$j$$$ components. Define $$$wb[i][j]$$$, $$$bw[i][j]$$$ and $$$bb[i][j]$$$ analogously.

Now, suppose we have a random $$$2 \times (i-1)$$$ grid and we want to find out the value of $$$ww[i][j]$$$. Consider the possible arrangements of the $$$i-1$$$-th column in the random grids:

1) The $$$i-1$$$-th column contains two white squares. In this case, we add $$$ww[i-1][j]$$$ to $$$ww[i][j]$$$. We do this because every possible grid that ends with two white squares and has $$$j$$$ components generates another possible grid (which has one more column and keeps the same amount of components) by adding a column of white squares.

2) The $$$i-1$$$-th column contains two black squares. In this case, we add $$$bb[i-1][j-1]$$$ to $$$ww[i][j]$$$ (notice that we add one column and one component to the grid when we add a column of white squares).

3) The $$$i-1$$$-th column contains distinct squares. In this case, we add $$$wb[i-1][j]$$$ and $$$bw[i-1][j]$$$ to $$$ww[i][j]$$$. This happens because when we add a column of white squares, the number of components doesn't change (the white part of the $$$i-1$$$-th column touches the new column) and, obviously, the number of columns increases by 1.

This means that

$$$ww[i][j] = wb[i-1][j] + bw[i-1][j] + ww[i-1][j] + bb[i-1][j-1] $$$

The other recurrences are left as an exercise to the reader $\dots$

Obs.: Notice that $$$ww[i][j] = bb[i][j]$$$ and $$$wb[i][j] = bw[j][i]$$$ because of symmetry. I only used four distinct arrays in this comment because my reasoning can be expressed more clearly this way.

Therefore, you just need to run a double for loop to update the DP arrays. This can be achieved in $$$O(n \cdot k)$$$ time.

v7fgg

2 years ago, # |

Question D java solution

BledDest's blog