Teza Round 1 (Codeforces Round 1015, Div. 1 + Div. 2) Editorial

#	User	Rating
1	Benq	3857
2	jiangly	3810
3	maroonrk	3534
4	tourist	3528
5	Kevin114514	3510
6	turmax	3411
7	Um_nik	3387
8	Radewoosh	3367
9	heuristica	3322
10	strapple	3317

#	User	Contrib.
1	Qingyu	157
2	maspy	150
3	Um_nik	145
4	Errichto	139
5	adamant	136
6	maroonrk	134
7	DNR	133
7	nik_exists	133
9	AmShZ	130
10	Dominater069	129

Thanks for participation!

2084A - Max and Mod

Hint 1

Solution

Implementation

#include <bits/stdc++.h>
using namespace std;

int main() {
	int T, n;
	cin >> T;
	while (T--) {
		cin >> n;
		if (n & 1) {
			cout << n << ' ';
			for (int i = 1; i < n; ++i) {
				cout << i << " \n"[i == n - 1];
			}
		} else {
			cout << "-1\n";
		}
	}
	return 0;
}

2084B - MIN = GCD

Idea: zltzlt

Hint 1

Hint 2

Solution

Implementation

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int T, n;
	cin >> T;
	while (T--) {
		cin >> n;
		vector<ll> a(n);
		for (ll &x : a) {
			cin >> x;
		}
		int p = min_element(a.begin(), a.end()) - a.begin();
		ll g = 0;
		for (int i = 0; i < n; ++i) {
			if (i != p && a[i] % a[p] == 0) {
				g = __gcd(g, a[i]);
			}
		}
		cout << (g == a[p] ? "Yes\n" : "No\n");
	}
	return 0;
}

2084C - You Soared Afar With Grace

Idea: CharlieV

Hint 1

Hint 2

Solution

Implementation

#include <bits/stdc++.h>
using namespace std;

const int maxn = 200100;

int n, a[maxn], b[maxn], m, p[maxn], ans[maxn][2];

inline void work(int x, int y) {
	if (x == y) {
		return;
	}
	ans[++m][0] = x;
	ans[m][1] = y;
	swap(a[x], a[y]);
	swap(p[a[x]], p[a[y]]);
	swap(b[x], b[y]);
}

void solve() {
	cin >> n;
	for (int i = 1; i <= n; ++i) {
		cin >> a[i];
		p[a[i]] = i;
	}
	for (int i = 1; i <= n; ++i) {
		cin >> b[i];
	}
	m = 0;
	int x = 0;
	for (int i = 1; i <= n; ++i) {
		if (a[i] == b[i]) {
			if (n % 2 == 0 || x) {
				cout << "-1\n";
				return;
			}
			x = i;
		} else if (b[p[b[i]]] != a[i]) {
			cout << "-1\n";
			return;
		}
	}
	if (n & 1) {
		work(x, (n + 1) / 2);
	}
	for (int i = 1; i <= n / 2; ++i) {
		work(p[b[i]], n - i + 1);
	}
	cout << m << '\n';
	for (int i = 1; i <= m; ++i) {
		cout << ans[i][0] << ' ' << ans[i][1] << '\n';
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int T;
	cin >> T;
	while (T--) {
		solve();
	}
	return 0;
}

2084D - Arcology On Permafrost

Idea: zltzlt

Hint 1

Hint 2

Hint 3

Solution

Implementation

#include <bits/stdc++.h>
using namespace std;

int main() {
	int T;
	cin >> T;
	while (T--) {
		int n, m, k;
		cin >> n >> m >> k;
		for (int i = 0; i < n; ++i) {
			cout << i % (n < (m + 1) * k ? k : n / (m + 1)) << " \n"[i == n - 1];
		}
	}
	return 0;
}

2084E - Blossom

Idea: zltzlt

Hint 1

Hint 2

Solution

Implementation

#include <bits/stdc++.h>
using namespace std;

const int maxn = 5050;
const int mod = 1000000007;

int n, a[maxn], fac[maxn], C[maxn][maxn], b[maxn], d[maxn][maxn];
bool vis[maxn];

void solve() {
	cin >> n;
	for (int i = 0; i <= n; ++i) {
		vis[i] = 0;
		for (int j = 0; j <= n; ++j) {
			d[i][j] = 0;
		}
	}
	fac[0] = 1;
	for (int i = 1; i <= n; ++i) {
		cin >> a[i];
		fac[i] = 1LL * fac[i - 1] * i % mod;
		b[i] = b[i - 1] + (a[i] == -1);
		if (a[i] != -1) {
			vis[a[i]] = 1;
		}
	}
	for (int i = 0; i <= n; ++i) {
		C[i][0] = C[i][i] = 1;
		for (int j = 1; j < i; ++j) {
			C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % mod;
		}
	}
	int mn1 = n;
	for (int i = 1; i <= n; ++i) {
		int mn2 = n;
		for (int j = n; j >= i; --j) {
			int x = b[j] - b[i - 1], y = min(mn1, mn2);
			++d[x][0];
			--d[x][y];
			if (a[j] != -1) {
				mn2 = min(mn2, a[j]);
			}
		}
		if (a[i] != -1) {
			mn1 = min(mn1, a[i]);
		}
	}
	for (int i = 0; i <= b[n]; ++i) {
		for (int j = 1; j <= n; ++j) {
			d[i][j] += d[i][j - 1];
		}
	}
	int ans = 0, cnt = 0;
	for (int i = 0; i < n; ++i) {
		cnt += (!vis[i]);
		for (int j = cnt; j <= b[n]; ++j) {
			ans = (ans + 1LL * C[j][cnt] * fac[cnt] % mod * fac[b[n] - cnt] % mod * d[j][i]) % mod;
		}
	}
	cout << ans << '\n';
}

int main() {
	int T;
	cin >> T;
	while (T--) {
		solve();
	}
	return 0;
}

2084F - Skyscape

Idea: zltzlt
Developer: 244mhq

Hint 1

Hint 2

Solution

Implementation

#include <bits/stdc++.h>
using namespace std;

const int maxn = 500100;

int n, a[maxn], b[maxn], c[maxn], p[maxn], q[maxn];

struct node {
	int r, x;
	node(int a = 0, int b = 0) : r(a), x(b) {}
};

inline bool operator < (const node &a, const node &b) {
	return a.r > b.r || (a.r == b.r && a.x > b.x);
}

vector<node> vc[maxn];

struct DS1 {
	int c[maxn];
	
	inline void init() {
		for (int i = 0; i <= n; ++i) {
			c[i] = 0;
		}
	}
	
	inline void update(int x, int d) {
		for (int i = x; i <= n; i += (i & (-i))) {
			c[i] = max(c[i], d);
		}
	}
	
	inline int query(int x) {
		int res = 0;
		for (int i = x; i; i -= (i & (-i))) {
			res = max(res, c[i]);
		}
		return res;
	}
} T1;

struct DS2 {
	int c[maxn];
	
	inline void init() {
		for (int i = 0; i <= n; ++i) {
			c[i] = n + 1;
		}
	}
	
	inline void update(int x, int d) {
		for (int i = x; i; i -= (i & (-i))) {
			c[i] = min(c[i], d);
		}
	}
	
	inline int query(int x) {
		int res = n + 1;
		for (int i = x; i <= n; i += (i & (-i))) {
			res = min(res, c[i]);
		}
		return res;
	}
} T2;

void solve() {
	cin >> n;
	for (int i = 1; i <= n; ++i) {
		cin >> a[i];
		p[a[i]] = i;
		q[i] = 0;
		vector<node>().swap(vc[i]);
	}
	for (int i = 1; i <= n; ++i) {
		cin >> b[i];
		if (b[i]) {
			q[b[i]] = i;
		}
	}
	T1.init();
	for (int i = 1; i <= n; ++i) {
		if (q[i]) {
			if (T1.query(p[i]) > q[i]) {
				cout << "-1\n";
				return;
			}
			T1.update(p[i], q[i]);
		}
	}
	T1.init();
	T2.init();
	for (int i = 1; i <= n; ++i) {
		if (q[a[i]]) {
			T1.update(a[i], q[a[i]]);
		} else {
			c[i] = T1.query(a[i]) + 1;
		}
	}
	for (int i = n; i; --i) {
		if (q[a[i]]) {
			T2.update(a[i], q[a[i]]);
		} else {
			int r = T2.query(a[i]) - 1;
			if (c[i] > r) {
				cout << "-1\n";
				return;
			}
			vc[c[i]].emplace_back(r, a[i]);
		}
	}
	priority_queue<node> pq;
	for (int i = 1; i <= n; ++i) {
		for (node u : vc[i]) {
			pq.push(u);
		}
		if (!b[i]) {
			if (pq.empty() || pq.top().r < i) {
				cout << "-1\n";
				return;
			}
			b[i] = pq.top().x;
			pq.pop();
		}
	}
	for (int i = 1; i <= n; ++i) {
		cout << b[i] << " \n"[i == n];
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int T;
	cin >> T;
	while (T--) {
		solve();
	}
	return 0;
}

2084G1 - Wish Upon a Satellite (Easy Version)

Idea: zltzlt

Hint 1

Hint 2

Solution

Implementation

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

void solve() {
	int n;
	cin >> n;
	vector<int> a(n + 1, -1);
	vector< vector<ll> > f(n + 1, vector<ll>(n + 1, 1e18));
	for (int i = 1, x; i <= n; ++i) {
		cin >> x;
		if (x) {
			a[x] = i & 1;
		}
	}
	if (a[1] != 1) {
		f[1][0] = 0;
	}
	if (a[1] != 0) {
		f[1][1] = 0;
	}
	for (int i = 1; i < n; ++i) {
		for (int j = 0; j <= i; ++j) {
			f[i][j] += j * (n / 2 - (i - j)) + (i - j) * ((n + 1) / 2 - j);
			if (a[i + 1] != 1) {
				f[i + 1][j] = min(f[i + 1][j], f[i][j]);
			}
			if (a[i + 1] != 0) {
				f[i + 1][j + 1] = min(f[i + 1][j + 1], f[i][j]);
			}
		}
	}
	ll ans = -f[n][(n + 1) / 2];
	for (int i = 1; i <= n; ++i) {
		ans += i * i;
	}
	cout << ans << '\n';
}

int main() {
	int T;
	cin >> T;
	while (T--) {
		solve();
	}
	return 0;
}

2084G2 - Wish Upon a Satellite (Hard Version)

Idea: zltzlt

Hint 1

Solution

Implementation

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int maxn = 500100;

int n, a[maxn];
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());

int p[maxn], nt, ls[maxn], rs[maxn], sz[maxn];
bool vis[maxn];

struct vec {
	ll a0, a1, a2;
	vec(ll a = 0, ll b = 0, ll c = 0) : a0(a), a1(b), a2(c) {}
} val[maxn];

struct mat {
	ll a00, a01, a02, a10, a11, a12, a20, a21, a22;
	mat(ll a = 0, ll b = 0, ll c = 0, ll d = 0, ll e = 0, ll f = 0, ll g = 0, ll h = 0, ll i = 0) : a00(a), a01(b), a02(c), a10(d), a11(e), a12(f), a20(g), a21(h), a22(i) {}
} I, tag[maxn];

inline vec operator * (const vec &a, const mat &b) {
	vec res;
	res.a0 = a.a0 * b.a00 + a.a1 * b.a10 + a.a2 * b.a20;
	res.a1 = a.a0 * b.a01 + a.a1 * b.a11 + a.a2 * b.a21;
	res.a2 = a.a0 * b.a02 + a.a1 * b.a12 + a.a2 * b.a22;
	return res;
}

inline mat operator * (const mat &a, const mat &b) {
	mat res;
	res.a00 = a.a00 * b.a00 + a.a01 * b.a10 + a.a02 * b.a20;
	res.a01 = a.a00 * b.a01 + a.a01 * b.a11 + a.a02 * b.a21;
	res.a02 = a.a00 * b.a02 + a.a01 * b.a12 + a.a02 * b.a22;
	res.a10 = a.a10 * b.a00 + a.a11 * b.a10 + a.a12 * b.a20;
	res.a11 = a.a10 * b.a01 + a.a11 * b.a11 + a.a12 * b.a21;
	res.a12 = a.a10 * b.a02 + a.a11 * b.a12 + a.a12 * b.a22;
	res.a20 = a.a20 * b.a00 + a.a21 * b.a10 + a.a22 * b.a20;
	res.a21 = a.a20 * b.a01 + a.a21 * b.a11 + a.a22 * b.a21;
	res.a22 = a.a20 * b.a02 + a.a21 * b.a12 + a.a22 * b.a22;
	return res;
}

inline void init() {
	for (int i = 0; i <= nt; ++i) {
		p[i] = ls[i] = rs[i] = sz[i] = 0;
		val[i] = vec();
		tag[i] = I;
		vis[i] = 0;
	}
	nt = 0;
}

inline int newnode(ll x, ll y) {
	int u = ++nt;
	p[u] = rnd();
	ls[u] = rs[u] = 0;
	sz[u] = 1;
	val[u] = vec(x, y, 1);
	tag[u] = I;
	vis[u] = 0;
	return u;
}

inline void pushup(int x) {
	sz[x] = sz[ls[x]] + sz[rs[x]] + 1;
}

inline void pushtag(int x, const mat &y) {
	if (!x) {
		return;
	}
	val[x] = val[x] * y;
	tag[x] = tag[x] * y;
	vis[x] = 1;
}

inline void pushdown(int x) {
	if (!vis[x]) {
		return;
	}
	pushtag(ls[x], tag[x]);
	pushtag(rs[x], tag[x]);
	vis[x] = 0;
	tag[x] = I;
}

void split(int u, int &x, int &y) {
	if (!u) {
		x = y = 0;
		return;
	}
	pushdown(u);
	if (val[u].a0 < 0) {
		x = u;
		split(rs[u], rs[u], y);
	} else {
		y = u;
		split(ls[u], x, ls[u]);
	}
	pushup(u);
}

int merge(int x, int y) {
	if (!x || !y) {
		return x | y;
	}
	pushdown(x);
	pushdown(y);
	if (p[x] < p[y]) {
		rs[x] = merge(rs[x], y);
		pushup(x);
		return x;
	} else {
		ls[y] = merge(x, ls[y]);
		pushup(y);
		return y;
	}
}

ll f[maxn], tot;

void dfs(int u) {
	if (!u) {
		return;
	}
	pushdown(u);
	dfs(ls[u]);
	f[++tot] = val[u].a0;
	dfs(rs[u]);
}

void solve() {
	cin >> n;
	for (int i = 1; i <= n; ++i) {
		a[i] = -1;
	}
	for (int i = 1, x; i <= n; ++i) {
		cin >> x;
		if (x) {
			a[x] = (i & 1);
		}
	}
	init();
	int rt = 0;
	ll l = 0, r = 0, x = 0;
	if (a[1] == 1) {
		l = r = 1;
	} else if (a[1] == -1) {
		rt = newnode(0, 1);
		r = 1;
	}
	for (ll i = 1; i < n; ++i) {
		x += l * l * 2 + (-i - i - (n & 1)) * l + i * ((n + 1) / 2);
		pushtag(rt, mat(1, 0, 0, 4, 1, 0, -i - i - (n & 1) - 2, 0, 1));
		if (a[i + 1] == 1) {
			pushtag(rt, mat(1, 0, 0, 0, 1, 0, 0, 1, 1));
			++l;
			++r;
		} else if (a[i + 1] == -1) {
			int u, v;
			split(rt, u, v);
			pushtag(v, mat(1, 0, 0, 0, 1, 0, 0, 1, 1));
			rt = merge(merge(u, newnode(0, l + 1 + sz[u])), v);
			++r;
		}
	}
	tot = 0;
	dfs(rt);
	ll ans = -x;
	for (int i = 1; i <= (n + 1) / 2 - l; ++i) {
		ans -= f[i];
	}
	for (ll i = 1; i <= n; ++i) {
		ans += i * i;
	}
	cout << ans << '\n';
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	I.a00 = I.a11 = I.a22 = 1;
	int T;
	cin >> T;
	while (T--) {
		solve();
	}
	return 0;
}

2084H - Turtle and Nediam 2

Idea: zltzlt
Developer: StarSilk

Hint 1

Hint 2

Hint 3

Solution

Implementation 1

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int maxn = 2000100;
const ll mod = 1000000007;

int n, a[maxn], m, nxt[maxn], stk[maxn], top;
ll f[maxn], d[maxn];
char s[maxn];

inline ll calc() {
	top = 0;
	for (int i = m; i >= 1; i -= 2) {
		while (top && a[stk[top]] - stk[top] / 2 < a[i] - i / 2) {
			--top;
		}
		nxt[i] = stk[top];
		stk[++top] = i;
	}
	top = 0;
	for (int i = m - 1; i >= 1; i -= 2) {
		while (top && a[stk[top]] - stk[top] / 2 < a[i] - i / 2) {
			--top;
		}
		nxt[i] = stk[top];
		stk[++top] = i;
	}
	for (int i = 1; i < m; ++i) {
		f[i] = d[i] = 0;
	}
	f[1] = a[1];
	for (int i = 3; i < m; i += 2) {
		f[i] = 1;
	}
	ll ans = 0;
	for (int i = 1; i < m; ++i) {
		if (i >= 3) {
			d[i] = (d[i] + d[i - 2]) % mod;
		}
		f[i] = (f[i] + d[i]) % mod;
		int j = i + 1, x = 0;
		while (j < m) {
			int k = (nxt[j] ? nxt[j] : m);
			f[j] = (f[j] + f[i] * (a[j] - x)) % mod;
			x = a[j] + (k - j) / 2 - 1;
			d[j + 2] = (d[j + 2] + f[i]) % mod;
			d[k] = (d[k] - f[i] + mod) % mod;
			j = k;
		}
		if ((m - i) & 1) {
			ans = (ans + f[i]) % mod;
		}
	}
	return ans * a[m] % mod;
}

void solve() {
	cin >> n >> s;
	m = 0;
	for (int i = 0, j = 0; i < n; i = (++j)) {
		while (j + 1 < n && s[j + 1] == s[i]) {
			++j;
		}
		a[++m] = j - i + 1;
	}
	if (m == 1) {
		cout << n - 1 << '\n';
		return;
	}
	if (m == 2) {
		cout << 1LL * a[1] * a[2] % mod << '\n';
		return;
	}
	ll ans = calc();
	--m;
	for (int i = 1; i <= m; ++i) {
		a[i] = a[i + 1];
	}
	a[1] = 1;
	ans = (ans + calc()) % mod;
	cout << ans << '\n';
}
 
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int T;
	cin >> T;
	while (T--) {
		solve();
	}
	return 0;
}

Implementation 2

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int maxn = 2000100;
const ll mod = 1000000007;

int n, a[maxn], m, nxt[maxn], stk[maxn], top;
ll f[maxn], g[maxn], d[maxn];
char s[maxn];

inline ll calc() {
	top = 0;
	for (int i = m; i >= 1; i -= 2) {
		while (top && a[stk[top]] - stk[top] / 2 < a[i] - i / 2) {
			--top;
		}
		nxt[i] = stk[top];
		stk[++top] = i;
	}
	top = 0;
	for (int i = m - 1; i >= 1; i -= 2) {
		while (top && a[stk[top]] - stk[top] / 2 < a[i] - i / 2) {
			--top;
		}
		nxt[i] = stk[top];
		stk[++top] = i;
	}
	for (int i = 1; i < m; ++i) {
		f[i] = g[i] = d[i] = 0;
	}
	f[1] = a[1];
	for (int i = 3; i < m; i += 2) {
		f[i] = 1;
	}
	ll ans = 0;
	for (int i = 1; i < m; ++i) {
		if (i >= 3) {
			d[i] = (d[i] + d[i - 2]) % mod;
		}
		f[i] = (f[i] + d[i]) % mod;
		g[i + 1] = (g[i + 1] + f[i]) % mod;
		f[i + 1] = (f[i + 1] + f[i] * a[i + 1]) % mod;
		d[i + 2] = (d[i + 2] + g[i]) % mod;
		if (nxt[i]) {
			g[nxt[i]] = (g[nxt[i]] + g[i]) % mod;
			f[nxt[i]] = (f[nxt[i]] + g[i] * (a[nxt[i]] - a[i] - (nxt[i] - i) / 2 + 1)) % mod;
			d[nxt[i]] = (d[nxt[i]] - g[i] + mod) % mod;
		}
		if ((m - i) & 1) {
			ans = (ans + f[i]) % mod;
		}
	}
	return ans * a[m] % mod;
}

void solve() {
	cin >> n >> s;
	m = 0;
	for (int i = 0, j = 0; i < n; i = (++j)) {
		while (j + 1 < n && s[j + 1] == s[i]) {
			++j;
		}
		a[++m] = j - i + 1;
	}
	if (m == 1) {
		cout << n - 1 << '\n';
		return;
	}
	if (m == 2) {
		cout << 1LL * a[1] * a[2] % mod << '\n';
		return;
	}
	ll ans = calc();
	--m;
	for (int i = 1; i <= m; ++i) {
		a[i] = a[i + 1];
	}
	a[1] = 1;
	ans = (ans + calc()) % mod;
	cout << ans << '\n';
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int T;
	cin >> T;
	while (T--) {
		solve();
	}
	return 0;
}

void solve() { int n, m, k; cin >> n >> m >> k; int l = n / (m + 1); int deletions_per_op = (k + l - 1) / l; // ceil(k/l) int T1 = n / ((m + 1) * deletions_per_op); // at least k int T2 = k; int T = max({T1, T2, 1ll}); // 至少为1 For(i, n) { cout << i % T << ' '; } cout << '\n'; }

Comments (77)

Show archived | Write comment?

wasif2397

17 months ago, hide # |

for C I created a graph for the target positions of each index and then ran a dfs. There will be a cycles and we need size — 1 steps to reach out target and graph building got me a WA :(((

→ Reply

ycperson

17 months ago, hide # ^ |

you don't need to put the pairs such that a[i] = i in the end. You just need to ensure in the end that if some pair (a[i], b[i]) exists, that (a[j], b[j]) = (b[i], a[i]) exists for some other j as well. You can place them at ANY symmetric positions about the middle.

akane646

for C I swap and pray, after swapping I check one last time if all match -> YES/NO.

And it works like a charm.

dhano.krishna123

$$$O(n^2)$$$

solution by swapping each? Or did you do additional check first whether it's possible or not?

my sol is at most n//2 operations, overall is O(n).

I marked the number position then swap it... idk how you can do O(n^2)?

cxlian

a piece of advice: Think more deeply and plan thoroughly before you start writing.

khba

so quick tho

dhiva21112004

The Penalties got us fr , could've avoided so much of penalty this contest!!

Kefrov

+34

The checker message Jury has the better answer: jans = 2, pans = 0 helped me figure out that I need to find $$$f(a)$$$ to solve D lmao

Yousef.Fadl

+28

The Permutation Contest

fbrunodr

+70

Difficulty gap from D to E is ridiculous

+14

As a specialist, all I do after ABCD is stair at the ceiling after done reading the problems.

TiwoeeM

As a specialist I have never read E in div2 contest within contest

gamer247

As a specialist, I was not able to do D itself :(

DonutMaster

but, you aren't a specialist

FrostBlaze

As a specialist, i have rarely done D in div2

H_a_r_M_i_t

As an Expert : I saw only $$$250$$$ AC in $$$(Div$$$ $$$1+2)$$$, Took that as a sign from the universe to brew a cup of coffee :D

StelIawinD

+63

As a International Grandmaster, I solve ABCD within 30 mins and then stuck in E for almost 2 hours.

stable_shoes

As a pupil,I almost died when implementing E before dawn.

YSlow

C messed up the whole contest, but D was saver

Nxxlt

D messed up the whole contest, but E was saver

ProofByContradiction_

← Rev. 2 →

can you explain your solution for problem E.

Update: Thank You for the well explained solution.

+12

Firstly, you need to do some transformations of the statement.

Define $$$mex(a)$$$ as the number of $$$k$$$'s such that every number in the range $$$[0, k]$$$ is present in $$$a$$$. This number actually equals to $$$mex$$$, because by the definition, all numbers from $$$0$$$ to $$$mex - 1$$$ are present and $$$mex$$$ is not present.

Also, let's count the contribution of each subarray independently. Now, you can sum up the contributions of each $$$k$$$ separately. For this purpose, you can brute force the value of $$$k$$$. It is possible to make all integers from $$$0$$$ to $$$k$$$ appear in the subarray if the subarray contains all the fixed positions where $$$a_i \le k$$$, because if this doesn't satisfy, i.e. there's a value $$$\le k$$$ in the whole array, but not in the subarray, then you should repeat that value $$$2$$$ times to make this value appear in the subarray.

Now, let's keep track of the minimum/maximum position of a fixed element that is $$$\le k$$$, let's denote them as $$$[lx, rx]$$$ correspondingly. Then, for the subarray $$$[l, r]$$$ to have a positive contribution, it should contain the segment $$$[lx, rx]$$$.

To calculate the contribution of segment $$$[l, r]$$$, let's denote $$$cnt$$$ as the number of elements that are $$$-1$$$ in the current segment, and let's denote $$$miss$$$ as the number of elements in the array that are $$$-1$$$, and let's denote $$$x$$$ as the number of elements that are $$$\le k$$$ that aren't present in the array. The contribution becomes $$$P(cnt, x) * (miss - x)!$$$ . This is because you must insert those $$$x$$$ missing elements $$$\le k$$$ in the subarray to make all of them appear, and you can insert them in any order and in any position that is $$$-1$$$ in the subarray, so the number of such arrangements is $$$C(cnt, x) * x!$$$, or $$$P(cnt, x)$$$. And all other $$$miss - x$$$ elements can be inserted arbitarily into $$$-1$$$ positions, so the number of those arrangements is $$$(miss - x)!$$$ . Together, the number of ways equals to $$$P(cnt, x) * (miss - x)!$$$ .

To calculate this value fast, you need to fix the $$$cnt$$$, because $$$miss$$$ and $$$x$$$ are the same for all the subarrays. For each $$$cnt$$$, you should save the number of segments that contain $$$[lx, rx]$$$ and have the number of missing elements equal to $$$cnt$$$. Now you can notice that the number of $$$[lx, rx]$$$s for which the answer should be calculated equal to $$$n$$$, $$$k$$$ can take the maximum value of $$$n - 1$$$, so you can fix $$$cnt$$$ for each of those segments independently.

Let's iterate $$$rx$$$-s in decreasing order and add segments which have $$$r \ge rx$$$ and take a fenwick tree for each $$$cnt$$$. For each of those segments $$$[l, r]$$$, you need to add $$$1$$$ to the $$$l$$$-th position of the $$$cnt$$$'th fenwick tree. Now, the number of segments that contain $$$[lx, rx]$$$ and have the number of missing elements equal to $$$cnt$$$ is given by the $$$sum(1, lx)$$$ in the $$$cnt$$$-th fenwick tree. Basically, among segments with $$$r \ge rx$$$, you calculate the number of those with $$$l \le lx$$$. For more implementation details, you can look at my code.

Nogaybica

+17

Problem C is really interesting. Thanks for the round and very fast editorial

RDDCCD

A little typo: in problem B, time complexity for finding the gcd of $$$n$$$ numbers is $$$\Theta(n+\log a)$$$ instead of $$$\Theta (n\log a)$$$.

Benq

+36

To be fair, the complexity could depend on which gcd implementation you use.

Example: https://codeforces.me/blog/entry/137056

meetsarvan

+20

Literally there is no graph , dp , binary search , greedy , etc... in A-D problems.

it is only based on mex and permutation .

like why now a days , the contest are going bad and bad ?

psyduck06

D is greedy and C feels as well , the thing is that on lower level(or my level) questions they have started giving constructive or less — pattern based more to avoid AI based cheating

C is graphs and cycle. Check my submission

Also, I politely disagree with you. This is one of the best rounds recently on codeforces. The problem quality was amazing

gyan_xyz

can anyone help me with this doubt with problem B..can anyone explain why if i iterate over all the elements in the vector divisible by minimum element given to find a pair if its gcd is equal to minimum element if i find then i just print yes....then it should not give wrong answer in o(n^2) time complexity..it would have given tle ...but it gave wrong answer....if i take gcd of all elements divisible by minimum element it shows accepted how?? i mean let g = gcd(b,c,d....z),where a|b,c,d,...z; so g should be equal to either of (gcd(b,c...z),gcd(c,d....z),gcd(d,e....z),...gcd(y,z)) right?

Let $$$G = \gcd(a_1, a_2, \dots, a_n)$$$.

For any pair $$$(a_i, a_j)$$$, we have: $$$G \mid a_i$$$ $$$\text{and}$$$ $$$G \mid a_j$$$ $$$\Rightarrow G \mid \gcd(a_i, a_j)$$$ $$$\Rightarrow$$$ Thus, $$$\gcd(a_i, a_j) \geq G$$$

Let the array be: [2, 12, 20, 30]

min = 2
gcd(12, 20, 30) = 2 = min

So we can split as:
Prefix = [2], Suffix = [12, 20, 30] → min = gcd = 2 → YES

But pairwise GCDs are:

gcd(12, 20) = 4
gcd(12, 30) = 6
gcd(20, 30) = 10

None equal to 2, hence pairwise checking fails. Must take gcd of all divisible-by-min elements.

thank you very much!!got it..

livingstone

THANKS!

accelerate_nju

← Rev. 3 →

nice C and nice D. but E is too hard for me :)

B's complexity is $$$O(n + \log mn)$$$ I guess, since $$$\gcd$$$ reduces $$$\log$$$ times, or it does not change. After $$$\gcd$$$ becomes $$$mn$$$, $$$\gcd$$$ function is calculated in $$$O(1)$$$.

BlueGlaucus1

Kind of a dumb question, but for problems like C, do we always need to assume that we need to output the minimum number of operations needed? I got that problem wrong because of that :( ...

fisher199

Generally, I maintain a rule of thumb that it's good to highlight keywords such as minimize, maximize, etc. I have had an unpleasant amount of WAs because I'd just skim over those words and forget about them when modeling the solution.

If you highlight those keywords, you can then determine whether or not you should minimize/maximize or whatever it is you have to do.

On a separate note, sometimes it's easier to make a strategy that always minimizes the number of operations and sometimes it is not. If it's easy to make such a strategy (and you can more or less prove that it's always optimal), then you should use it. Otherwise, such as in the case of problem C (I personally just avoided that line of thought as I figured it would waste more time), it's easier to come up with a strategy that just works and doesn't minimize the number of operations + the statement didn't have any of those keywords, because of which we aren't restricted.

yeah what happened was that I didn't consider the case where if n was odd and if the index where the numbers were the same on a and b (ex: n = 5, and a[3] = 4 and b[3] = 4), then I wouldn't need to do a swap to the middle. I just swapped the element that has the same values to the middle always without considering this case, figuring it wasn't important as the solution didn't require you to minimize the swaps.

VirtualTree

Can anyone please share their approach for problem E? I didn't quite understand any part from the editorial for E.

Ragnar21

← Rev. 10 →

Formula Calculation :
Missing = array of all the numbers that do not appear in the original array

For a range [l,r], spotted = number of -1's present in the range
total = number of -1's in the original array
non-spotted = total — spotted = number of -1's present outside the range
idx = index of the maximum number in Missing that can contribute to MEX of the range
Eg. Permutation: [-1, 0, -1, -1, 3, -1]
=> Missing = [1,2,4,5]
In range [1, 4], spotted = 3 and idx = 2
(Note that the maximum MEX for the range is 3, but it is not present in the Missing Array)

Claim: Every element in Missing having index <= idx can be made the MEX of range [l,r]
Proof: Let's say we want Missing[i] $$$(i \lt =idx)$$$ as the MEX of the range,
Choose i-1 positions from the spotted -1's, insert all the elements with index<=i
and 1 position from non-spotted -1's and insert Missing[i].

So we reduce down to calculating the number of ways in which $$$Missing[i]$$$ become MEX for a range.
=> Number of ways = C(spotted, i-1) * (total — spotted) * (i-1)! * (total — i)!
=> Contribution of i = Number of ways * Missing[i].

Now we can simply precompute the Contribution for all possible pairs of (spotted, i) in O(N^2).

An another number which can contribute as a MEX for a range is the MEX we generate by putting all the missing elements ideally.
For eg. Permutation: [-1, 0, -1, 3, -1]
=> Missing = [1,2,4]
In range 1 to 3, if we put 1 at index 1 and 2 at index 3, the MEX of [1,3] is 3.
Let this number be Ideal MEX.
We can compute the contribution due to Ideal MEX for a range by:
=> C(spotted,idx) * idx! * (total-idx)! * Ideal MEX.

For O(N^3), we can iterate over all possible range and calculate the contribution for each i.
This can be optimised to O(N^2)
For a given range, sum of the value of all possible valid permutations(answer) = summation of contribution due to Missing[1] + Missing[2] + .. Missing[idx] which can be precalculated using prefix sum.

Refer to my submission for implementation:
https://codeforces.me/contest/2084/submission/314305426

iska_terminator

-12

IDK but D feels like 1300, C was more difficult than D I guess

ibrm

+49

Can you please write proper editorial for problem E? Especially optimization part

ItsNotMeItsYou

+47

This is my solution:

Firstly, we can calculate the expected MEX values for all ranges independently. Let's assume we are calculating for a specific range $$$[L, R]$$$. Let $$$emp$$$ be the number of $$$-1$$$'s in the range $$$[L, R]$$$, and let $$$all$$$ be the total number of $$$-1$$$'s in the entire array.

Instead of summing the expected MEX values as $$$\sum_{\text{mex}} (\text{how many permutations have MEX equal to } \text{mex}) \times \text{mex}$$$, we will instead sum as $$$\sum_{\text{mex}} (\text{how many permutations have MEX} \geq \text{mex})$$$, without multiplying by the MEX.

Suppose we want to compute the number of permutations where $$$\text{mex} = m$$$. Then, every integer $$$i \lt m$$$ must appear in the range $$$[L, R]$$$. If any such $$$i$$$ does not appear, then there are no valid permutations with MEX $$$\geq m$$$.

Let $$$bon$$$ be the number of integers $$$i \lt m$$$ that do not appear in the range. Then the number of permutations with MEX $$$\geq m$$$ is $$$\frac{emp! \times (all - bon)!}{(emp - bon)!}$$$.

This works because we choose $$$bon$$$ positions among the $$$emp$$$ empty slots to assign the missing values $$$i \lt m$$$, and the remaining $$$emp - bon$$$ slots can be filled with the remaining $$$-1$$$'s, while adjusting for the total permutations using the factorials.

It's clear that this can be computed for all MEX values in $$$O(N^3)$$$ time: 314148419.

We can optimize this using prefix sums: precompute values for all possible $$$emp$$$ and MEX values, and for each query, just check whether all integers $$$i \lt m$$$ are present in the range. My current implementation runs in $$$O(N^2 \log N)$$$, but I believe it can be optimized to $$$O(N^2)$$$: 314152700.

Caylex

You're right, and removing the log is actually quite simple. You can refer to my implementations during and after the contest: 314135087 and 314183843. The main idea is that the maximum possible MEX will never decrease as R increases, so you can just maintain it with two pointers.

MaheshDA

-9

Problem C Never mentioned to output minimum number of operations.

It clearly says, "If it is possible, output any valid sequence of operations. Otherwise, output −1 ".

I could not solve this problem during contest because of this and so many others would have faced the same problem. This needs to be addressed...!!!

Yeah I had the same issue too lol, I assume that they would usually say print the minimum number of operations, right?

hihitherethere

+16

You don't need to output the minimum number of operations thou...

You can check my two submissions and that is what got me WA

No your code is wrong check the judge result it says p[1] = q[1], not too many operations used or something

-8

It said the same for me, yet when I changed my code to correct one specific case where if the middle element had the same indices, then I wouldn't need to do a swap (I did a swap which used an extra operation unneccesarily), it was AC.

reirugan

+11

From the statement:

You can perform the following operation at most $$$n$$$ times: Choose two indices $$$i$$$ and $$$j$$$ ($$$1 \leq i, j \leq n$$$, $$$i \neq j$$$)...

Note that it says $$$i\neq j$$$. Both yours and MaheshDA's submissions output an operation on 2 2 for the test case:

3
1 2 3
3 2 1

which clearly violates this condition.

Oh ok, that makes a lot of sense. Thank you so much.

Sul_A.

In E's solution:

There are exactly $$$k$$$ -1s

I believe it's supposed to $$$c_1$$$ not $$$k$$$. zltzlt

zltzlt

Fixed. Thank you.

lucky1426shrma

Anyone ~ why this is giving WA , 314126993 , on PreT 3 ?

1
4
2 30 42 70

should output YES because $$$\gcd{(30, 42, 70)} = 2$$$ but your submission outputs NO.

Mr_Bald

For problem C, does anybody know why the following strategy of doing the swaps fails?

Store the indices of symmetric pairs in a map. Say a[i] = b[j] = x, and b[i] = a[j] = y, for some 1 <= i, j <= n, then we have mp[{min(x, y), max(x, y)}] = {i, j}.
Keep a counter (initially 0) and loop through each pair p:
If p is the pivot for odd n (i.e. p.first == p.second), ignore it.
Otherwise, swap the two pairs at indices (p.first, p.second) with the pairs at (counter, n - counter - 1) respectively.

Here is the submission: 314141297

Xellos

+30

Look, it's nice that there's hints in editorials these days, but those hints need to match difficulty of the problem. Take hint 1 of F, for example: it's offering 0 new information, instead it's (rephrasing) just "read and comprehend the problem statement". Here's an example of a much better hint:

Spoiler

Perhaps extremely basic handholding hints that point people to look for the obvious, to "speak math language" in general, are useful for early problems, but they won't help anyone who can actually solve a harder problem with hints without looking at a solution. That should be the criterion: can we reasonably expect anyone to be good enough to solve a problem just looking at hints up to K, but unable to figure out hint K on his own?

abcsumits

Solution for d:https://youtu.be/Ts0a4loZEP4

xiuer233

I think there might be a minor error in the Problem E solution—shouldn't it be $$$c_1 = i, k = j$$$?

OrinLoong

This C makes me very annoyed because it's extremely difficult to debug.

Whitecarrot

I'd like to know how to write the checker for problem D,does there exist a solution of complexity O(n)?

uditsh03

Can anyone pls tell me why this fail problem C:

code...

szcQAQ

Although E is difficult（I think the difficulty is 2400），E is an excellent problem！

karan_garg_12

Can anyone just explain the approch in layman terms for problem E, Everyone is focusing on the implimentation, but I just want to know how it got there.

Let's say the permutation is filled. How many intervals have MEX > 0? Add that to the answer. How many have MEX > 1? How many have > 2? Etc. At the end, every interval is added to the answer as many times as its MEX.

When the permutation is unfilled, at each of these steps where we're counting MEX > $$$m$$$, the cost of each interval isn't 1 but the number of permutations we can make such that this interval has MEX > $$$m$$$, i.e. it contains everything in $$$[0, m]$$$. That's the formula with factorials.

For a given $$$m$$$, the formula only depends on the number of unfilled positions $$$f$$$ in a given interval; the number of intervals can be large, but $$$f \in [0, N]$$$ so we want to count how many intervals have a given $$$f$$$; answer is (sum of cost * count over $$$f$$$) over $$$m$$$.

Last thing to deal with is that as $$$m$$$ increases, some intervals become impossible — we're only counting those that contain all the values in $$$[0, m]$$$ that are filled at the start, so they're superintervals of $$$I$$$ = [min position, max position of those filled values]. As $$$m$$$ increases, this interval $$$I$$$ increases too, so we can just remove those intervals from the counting above, each will only be removed once.

Ohh, I think I got it, I'll have to give it some time of my own to fully understand. Thanks a lot

lce4113

The editorial for E says $$$d_{x,0},d_{x,1},\dots,d_{x,y-1}$$$, but shouldn't it be $$$d_{0,x},d_{1,x},\dots,d_{y-1,x}$$$ based off of the definition of $$$d_{i,j}$$$?

jai_hanumant

I think definition of dp[i][j] should be the number of intervals satisfying these conditions for c1 = i and k = j? Then rest makes sense a little bit.

loom

Sorry. Now it's fixed.

peltorator

I have a slightly different implementation of H. I think it is a bit simpler: 314754662.

erogame

16 months ago, hide # |

For problem G2, I have a solution whose correctness I don't know how to prove. You can see it here:the link. The intrinsic interpretation is that the positrons and the electrons must be distributed as uniformly as possible, thus we only need to consider the states where the number of positrons and the number of electrons near each other.

Pandora1139

15 months ago, hide # |

My submission for E (Blossom) gets TLE on test-7 despite being O(n^2). Could someone help me figure out the issue?

Submission ID: 323239191

HuTao

13 months ago, hide # |

solving D in O(1)

difficult_saurabh

11 months ago, hide # |

For B, why are we putting all the numbers that are

divisible by min(a) and
not equal to a

on the right (GCD) side? For example, the numbers in the array could be p*min(a) and p*q*min(a) — these two are divisible by min(a), but their GCD is p*min(a), not min(a). Why not put p*min(a) in the left (MIN) side instead?

zltzlt's blog