Squarepoint Challenge (Codeforces Round 1055, Div. 1 + Div. 2) Editorial

#	User	Rating
1	Benq	3792
2	VivaciousAubergine	3647
3	jiangly	3631
4	Kevin114514	3574
5	maroonrk	3521
6	strapple	3515
7	Radewoosh	3461
8	tourist	3428
9	turmax	3378
10	Um_nik	3376

#	User	Contrib.
1	Qingyu	162
2	adamant	148
3	Um_nik	146
4	Dominater069	143
5	errorgorn	140
6	cry	138
7	Proof_by_QED	136
8	YuukiS	135
9	chromate00	134
10	soullless	133

Thank you for your participation!

Problem A, B were authored by djm03178.

Problem C was authored by middle_man.

Problem D was authored by qwerasdfzxcl.

Problem E, F, G, H1, H2 were authored by ko_osaga.

Spoiler

Code

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

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	int t;
	cin >> t;
	while (t--)
	{
		int n;
		cin >> n;
		set<int> s;
		for (int i = 0; i < n; i++)
		{
			int x;
			cin >> x;
			s.insert(x);
		}
		cout << s.size() * 2 - 1 << '\n';
	}
}

2152B - Catching the Krug

Spoiler

Code

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

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);

	int t;
	cin >> t;
	while (t--)
	{
		int n, ra, ca, rb, cb;
		cin >> n >> ra >> ca >> rb >> cb;
		int ans = 0;
		if (rb > ra)
			ans = max(ans, rb);
		else if (rb < ra)
			ans = max(ans, n - rb);
		if (cb > ca)
			ans = max(ans, cb);
		else if (cb < ca)
			ans = max(ans, n - cb);
		cout << ans << '\n';
	}
}

2152C - Triple Removal

Spoiler

Code

/*
* T1 Thanks Round
* Problem triple-removal
* Main Correct Solution
*/

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

const int MAX = 250'010;

int A[MAX];

int diff[MAX];
int diffsum[MAX];

int sum[2][MAX];

void solve() {
	int N, Q;
	cin >> N >> Q;
	int i;
	for (i = 1; i <= N; i++) cin >> A[i];
	for (i = 1; i <= N; i++) {
		sum[0][i] = sum[0][i - 1];
		sum[1][i] = sum[1][i - 1];
		sum[A[i]][i]++;

		diff[i] = A[i] != A[i - 1];
		diffsum[i] = diffsum[i - 1] + diff[i];
	}
	int l, r;
	for (i = 1; i <= Q; i++) {
		cin >> l >> r;

		int z, o;
		z = sum[0][r] - sum[0][l - 1];
		o = sum[1][r] - sum[1][l - 1];
		if (z % 3) {
			cout << -1 << '\n';
			continue;
		}
		if (o % 3) {
			cout << -1 << '\n';
			continue;
		}

		int sum = z / 3 + o / 3;
		if (diffsum[r] - diffsum[l] == (r - l)) sum++;
		cout << sum << '\n';
	}
}

signed main() {
	ios::sync_with_stdio(false), cin.tie(0);
	int t, T;
	cin >> T;
	for (t = 1; t <= T; t++) solve();
}

2152D - Division Versus Addition

Spoiler

Code

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

constexpr int MAXN = 250000;

int a[MAXN + 100];
ll prf[MAXN + 100][4];

void solve(){
    int n, q;
    scanf("%d %d", &n, &q);

    for (int i=1;i<=n;i++) scanf("%d", a+i);
    
    for (int i=1;i<=n;i++){
        for (int j=0;j<3;j++) prf[i][j] = prf[i-1][j];
        
        int typ = 2;
        if (popcount((unsigned)a[i]) == 1) typ = 0;
        else if (popcount((unsigned)a[i]-1) == 1) typ = 1;

        prf[i][typ]++;

        prf[i][3] = prf[i-1][3] + (31 - countl_zero((unsigned)a[i]));
    }

    while(q--){
        int l, r;
        scanf("%d %d", &l, &r);

        ll cnt[3] = {0};
        for (int j=0;j<3;j++) cnt[j] = prf[r][j] - prf[l-1][j];

        ll ans = prf[r][3] - prf[l-1][3] + cnt[2] + cnt[1] / 2;
        printf("%lld\n", ans);
    }
}

int main(){
    int t;
    scanf("%d", &t);

    while(t--) solve();
}

2152E - Monotone Subsequence

Spoiler

Code

#include <bits/stdc++.h>
using namespace std;
using lint = long long;
using pi = array<lint, 2>;
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(), (v).end()
#define cr(v, n) (v).clear(), (v).resize(n);

void solve() {
	int n;
	cin >> n;
	vector<int> ord(n * n + 1);
	iota(all(ord), 0);
	auto query = [&](vector<int> v) {
		cout << "? " << sz(v);
		for (auto &x : v)
			cout << " " << x + 1;
		cout << endl;
		int y;
		cin >> y;
		v.resize(y);
		for (auto &x : v)
			cin >> x, x--;
		return v;
	};
	vector<int> dp(n * n + 1, n);
	for (int i = 0; i < n; i++) {
		auto cur_ord = query(ord);
		if (sz(cur_ord) > n) {
			cout << "!";
			for (int i = 0; i < n+1; i++)
				cout << " " << cur_ord[i] + 1;
			cout << endl;
			return;
		}
		vector<int> new_ord;
		for (auto &x : ord) {
			if (!binary_search(all(cur_ord), x)) {
				new_ord.push_back(x);
			} else dp[x] = i;
		}
		ord = new_ord;
	}
	int cur = n;
	vector<int> ans;
	for (int i = n * n; i >= 0; i--) {
		if (dp[i] == cur) {
			ans.push_back(i);
			cur--;
		}
	}
	if(sz(ans) != n + 1){
	    cerr << cur << endl;
	    for(auto &x : dp) cerr << x << " ";
	    cerr << endl;
	}
	reverse(all(ans));
	assert(sz(ans) == n+1);
	cout << "!";
	for (auto &x : ans)
		cout << " " << x + 1;
	cout << endl;
}

int main() {
	int tc;
	cin >> tc;
	while (tc--)
		solve();
}

2152F - Triple Attack

Spoiler

Code

#include <bits/stdc++.h>
using namespace std;
using lint = long long;
using pi = array<lint, 2>;
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(), (v).end()
#define cr(v, n) (v).clear(), (v).resize(n);
const int MAXN = 500005;

int nxt1[20][MAXN], dep1[MAXN];
pi nxt2[20][MAXN];

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	
	int T;
	cin >> T;
	
	while (T--){
    	int n, t;
    	cin >> n >> t;
    	t++;
    	vector<int> a(n);
    	for (int i = 0; i < n; i++)
    		cin >> a[i];
    	
    	// EDIT: added init statements for globals
    	for (int i = 0; i < n+5; i++){
    	    for (int j = 0; j < 20; j++) nxt1[j][i]=0,nxt2[j][i]={0,0};
    	    dep1[i]=0;
    	}
    		
    	int j = 0;
    	for (int i = 0; i < n; i++) {
    		while (j < n && a[j] < a[i] + t)
    			j++;
    		nxt1[0][i] = j;
    	}
    	nxt1[0][n] = n;
    	for (int i = n - 1; i >= 0; i--)
    		dep1[i] = dep1[nxt1[0][i]] + 1;
    	for (int i = 1; i < 20; i++) {
    		for (int j = 0; j <= n; j++)
    			nxt1[i][j] = nxt1[i - 1][nxt1[i - 1][j]];
    	}
    	auto lca = [&](int u, int v) {
    		if (dep1[u] > dep1[v])
    			swap(u, v);
    		int dx = dep1[v] - dep1[u];
    		for (int i = 0; dx; i++) {
    			if (dx & 1) {
    				v = nxt1[i][v];
    			}
    			dx >>= 1;
    		}
    		if (u == v)
    			return u;
    		for (int i = 19; i >= 0; i--) {
    			if (nxt1[i][u] != nxt1[i][v]) {
    				u = nxt1[i][u];
    				v = nxt1[i][v];
    			}
    		}
    		return nxt1[0][u];
    	};
    	for (int i = 0; i < n; i++) {
    		int z = lca(i, i + 1);
    		nxt2[0][i] = pi{z, dep1[i] + dep1[i + 1] - 2 * dep1[z]};
    	}
    	nxt2[0][n] = pi{n, 0};
    	for (int i = 1; i < 20; i++) {
    		for (int j = 0; j <= n; j++) {
    			auto [n1, d1] = nxt2[i - 1][j];
    			auto [n2, d2] = nxt2[i - 1][n1];
    			nxt2[i][j] = pi{n2, d1 + d2};
    		}
    	}
    	auto gp = [&](int l, int r) {
    		int ans = 0;
    		for (int i = 19; i >= 0; i--) {
    			if (nxt1[i][l] < r) {
    				l = nxt1[i][l];
    				ans += (1 << i);
    			}
    		}
    		return ans + 1;
    	};
    	int q;
    	cin >> q;
    	while (q--) {
    		int l, r;
    		cin >> l >> r;
    		l--;
    		if (r - l <= 2) {
    			cout << r - l << "\n";
    			continue;
    		}
    		int ans = 0;
    		for (int i = 19; i >= 0; i--) {
    			if (nxt2[i][l][0] < r) {
    				ans += nxt2[i][l][1];
    				l = nxt2[i][l][0];
    			}
    		}
    		if (l + 1 <= r)
    			ans += gp(l, r);
    		if (l + 2 <= r)
    			ans += gp(l + 1, r);
    		cout << ans << "\n";
    	}
	}
}

2152G - Query Jungle

Spoiler

Code

#include <bits/stdc++.h>
using namespace std;
using lint = long long;
using pi = array<lint, 2>;
#define sz(a) ((int)(a).size())
#define all(a) (a).begin(), (a).end()
const int MAXN = 250005;
const int MAXT = 1050000;

struct mtrx {
	int nxt[2];
	mtrx() { nxt[0] = nxt[1] = 0; }
	mtrx(int x) {
		nxt[x] = 1;
		nxt[1 ^ x] = 0;
	}
	mtrx operator+(const mtrx &m) const {
		mtrx ret;
		ret.nxt[0] = nxt[0] + m.nxt[nxt[0] % 2];
		ret.nxt[1] = nxt[1] + m.nxt[(1 + nxt[1]) % 2];
		return ret;
	}
};

struct node {
	mtrx M[2];
	int lazy;
	node operator+(const node &nd) const {
		node ret;
		ret.M[0] = M[0] + nd.M[0];
		ret.M[1] = M[1] + nd.M[1];
		ret.lazy = 0;
		return ret;
	}
} tree[MAXT];

void init(int s, int e, int p, vector<pi> &seq) {
	if (s == e) {
		tree[p].M[seq[s][0]] = mtrx(seq[s][1]);
		tree[p].M[1 ^ seq[s][0]] = mtrx();
		return;
	}
	int m = (s + e) / 2;
	init(s, m, 2 * p, seq);
	init(m + 1, e, 2 * p + 1, seq);
	tree[p] = tree[2 * p] + tree[2 * p + 1];
}

void lazydown(int p) {
	if (tree[p].lazy) {
		for (int i = 2 * p; i < 2 * p + 2; i++) {
			tree[i].lazy ^= 1;
			swap(tree[i].M[0], tree[i].M[1]);
		}
		tree[p].lazy = 0;
	}
}

void update(int s, int e, int ps, int pe, int p) {
	if (e < ps || pe < s)
		return;
	if (s <= ps && pe <= e) {
		tree[p].lazy ^= 1;
		swap(tree[p].M[0], tree[p].M[1]);
		return;
	}
	int pm = (ps + pe) / 2;
	lazydown(p);
	update(s, e, ps, pm, 2 * p);
	update(s, e, pm + 1, pe, 2 * p + 1);
	tree[p] = tree[2 * p] + tree[2 * p + 1];
}

int query() { return tree[1].M[1].nxt[0] / 2; }

vector<int> gph[MAXN];
int a[MAXN], din[MAXN], dout[MAXN];
vector<pi> seq;

void dfs(int x, int p = -1) {
	din[x] = sz(seq);
	seq.push_back({a[x], 0});
	for (auto &y : gph[x]) {
		if (y != p)
			dfs(y, x);
	}
	seq.push_back({a[x], 1});
	dout[x] = sz(seq);
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int T; cin >> T;
	while (T--) {
    	int n;
    	cin >> n;
    	for (int i = 0; i < n; i++)
    		cin >> a[i];
    		
    	for (int i = 0; i < n; i++) gph[i].clear();
    	seq.clear();
    	
    	for (int i = 0; i < n - 1; i++) {
    		int u, v;
    		cin >> u >> v;
    		u--;
    		v--;
    		gph[u].push_back(v);
    		gph[v].push_back(u);
    	}
    	dfs(0);
    	init(0, sz(seq) - 1, 1, seq);
    	cout << query() << "\n";
    	int q;
    	cin >> q;
    	while (q--) {
    		int v;
    		cin >> v;
    		v--;
    		update(din[v], dout[v] - 1, 0, sz(seq) - 1, 1);
    		cout << query() << "\n";
    	}
	}
}

2152H1 - Victorious Coloring (Easy Version)

Spoiler

Code

#include <bits/stdc++.h>
using namespace std;
using lint = long long;
using pi = array<lint, 2>;
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(), (v).end()
#define cr(v, n) (v).clear(), (v).resize(n);

vector<int> pa;

int find(int x) { return pa[x] = (pa[x] == x ? x : find(pa[x])); }

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int T; cin>>T;
	while (T--){
		int n;
		cin >> n;
		vector<array<lint, 3>> edges;
		for (int i = 0; i < n - 1; i++) {
			lint u, v, w;
			cin >> u >> v >> w;
			u--;
			v--;
			edges.push_back({w, u, v});
		}
		sort(all(edges));
		reverse(all(edges));
		cr(pa, 2 * n - 1);
		vector<lint> cost(2 * n - 1);
		vector<pi> ch(2 * n - 1);
		iota(all(pa), 0);
		for (int i = 0; i < n - 1; i++) {
			int u = find(edges[i][1]);
			int v = find(edges[i][2]);
			pa[u] = i + n;
			pa[v] = i + n;
			ch[i + n] = {u, v};
			cost[edges[i][1]] += edges[i][0];
			cost[edges[i][2]] += edges[i][0];
			cost[i + n] -= edges[i][0] * 2;
		}
		for (int i = n; i < 2 * n - 1; i++) {
			cost[i] += cost[ch[i][0]] + cost[ch[i][1]];
		}
		int q;
		cin >> q;
		while (q--) {
			lint x;
			cin >> x;
			vector<lint> dp(2 * n - 1);
			lint dap = 0;
			for (int i = 0; i < 2 * n - 1; i++) {
				if (i >= n) {
					dp[i] += dp[ch[i][0]] + dp[ch[i][1]];
				}
				if (dp[i] + cost[i] < x) {
					dap += x - cost[i] - dp[i];
					dp[i] = x - cost[i];
				}
			}
			cout << dap << "\n";
		}
	}
}

2152H2 - Victorious Coloring (Hard Version)

Spoiler

Code

#include <bits/stdc++.h>
using namespace std;
using lint = long long;
using pi = array<lint, 2>;
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(), (v).end()
#define cr(v, n) (v).clear(), (v).resize(n);

vector<int> pa;

int find(int x) { return pa[x] = (pa[x] == x ? x : find(pa[x])); }

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int T; cin>>T;
	while (T--){
		int n;
		cin >> n;
		vector<array<lint, 3>> edges;
		for (int i = 0; i < n - 1; i++) {
			lint u, v, w;
			cin >> u >> v >> w;
			u--;
			v--;
			edges.push_back({w, u, v});
		}
		sort(all(edges));
		reverse(all(edges));
		cr(pa, 2 * n - 1);
		vector<lint> cost(2 * n - 1);
		vector<pi> ch(2 * n - 1);
		iota(all(pa), 0);
		for (int i = 0; i < n - 1; i++) {
			int u = find(edges[i][1]);
			int v = find(edges[i][2]);
			pa[u] = i + n;
			pa[v] = i + n;
			ch[i + n] = {u, v};
			cost[edges[i][1]] += edges[i][0];
			cost[edges[i][2]] += edges[i][0];
			cost[i + n] -= edges[i][0] * 2;
		}
		for (int i = n; i < 2 * n - 1; i++) {
			cost[i] += cost[ch[i][0]] + cost[ch[i][1]];
		}
		// (point, slope increase)
		vector<priority_queue<pi, vector<pi>, greater<pi>>> pq(n);
		vector<int> idx(2 * n - 1);
		iota(all(idx), 0);
		for (int i = 0; i < 2 * n - 1; i++) {
			if (i < n) {
				pq[i].push({cost[i], 1});
				continue;
			}
			if (sz(pq[idx[ch[i][0]]]) < sz(pq[idx[ch[i][1]]]))
				swap(ch[i][0], ch[i][1]);
			idx[i] = idx[ch[i][0]];
			while (sz(pq[idx[ch[i][1]]])) {
				auto tp = pq[idx[ch[i][1]]].top();
				pq[idx[ch[i][1]]].pop();
				pq[idx[i]].push(tp);
			}
			if (cost[i] >= pq[idx[i]].top()[0])
				continue;
			if (cost[i] >= lint(2e9))
				continue;
			lint A = 0, B = 0;
			lint pv = -1;
			while (sz(pq[idx[i]])) {
				auto [point, slope] = pq[idx[i]].top();
				pq[idx[i]].pop();
				B += A * (point - pv);
				pv = point;
				A += slope;
				// A x - A * pv + B = x - cost[i]
				// (A - 1) x = A * pv - B - cost[i]
				lint U = A * pv - B - cost[i];
				lint L = A - 1;
				// point <= U / L, so no need to dedup
				if (L > 0) {
					assert(point * L <= U);
					if ((sz(pq[idx[i]]) == 0 || U < pq[idx[i]].top()[0] * L)) {
						lint f1 = U / L - cost[i];
						lint f2 = (U / L + 1 - pv) * A + B;
						// (cost[i], 0) -> (U / L, f1) -> (U / L + 1, f2) -> increase w/ speed A
						pq[idx[i]].push({cost[i], 1});
						pq[idx[i]].push({U / L, f2 - f1 - 1});
						pq[idx[i]].push({U / L + 1, A - (f2 - f1)});
						break;
					}
				} else if (sz(pq[idx[i]]) == 0) {
					pq[idx[i]].push({cost[i], 1});
					break;
				}
			}
		}
		int q;
		cin >> q;
		vector<pi> queries(q);
		for (int i = 0; i < q; i++) {
			cin >> queries[i][0];
			queries[i][1] = i;
		}
		sort(all(queries));
		vector<lint> ans(q);
		lint A = 0, B = 0, pv = -1;
		auto T = idx[2 * n - 2];
		for (auto &[x, i] : queries) {
			while (sz(pq[T]) && pq[T].top()[0] <= x) {
				auto [point, slope] = pq[T].top();
				pq[T].pop();
				B += A * (point - pv);
				pv = point;
				A += slope;
			}
			ans[i] = (x - pv) * A + B;
		}
		for (auto &v : ans)
			cout << v << "\n";
	}
}

/* Coded by harshcooljn */ #include <bits/stdc++.h> using namespace std; typedef long long int ll; #define vll vector<ll> #define fr(i,a,n) for(ll i=a;i<n;i++) #define fastIO ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0) class Segtree { public: typedef struct node { ll cnt0, cnt1; ll min1, min0; ll f0, l0, f1, l1; node(ll cnt0 = 0, ll cnt1 = 0, ll min1 = 1e18, ll min0 = 1e18, ll f0 = -1, ll l0 = -1, ll f1 = -1, ll l1 = -1) { this->cnt0 = cnt0; this->cnt1 = cnt1; this->min0 = min0; this->min1 = min1; this->f0 = f0; this->f1 = f1; this->l0 = l0; this->l1 = l1; } } node; node merge(node& l, node& r) { node p; p.cnt0 = l.cnt0 + r.cnt0; p.cnt1 = l.cnt1 + r.cnt1; p.f0 = l.f0; if (p.f0 == -1) { p.f0 = r.f0; } p.l0 = r.l0; if (p.l0 == -1) { p.l0 = l.l0; } p.f1 = l.f1; if (p.f1 == -1) { p.f1 = r.f1; } p.l1 = r.l1; if (p.l1 == -1) { p.l1 = l.l1; } p.min0 = min(l.min0, r.min0); if (r.f0 != -1 && l.l0 != -1) { p.min0 = min(p.min0, r.f0 - l.l0); } p.min1 = min(l.min1, r.min1); if (r.f1 != -1 && l.l1 != -1) { p.min1 = min(p.min1, r.f1 - l.l1); } return p; } vector<node> t; Segtree(ll n) { t.assign(4 * n + 4, node()); } void build(ll i, ll l, ll r, vll& a) { if (l == r) { if (a[l] == 0) { t[i] = node(1, 0, 1e18, 1e18, l, l, -1, -1); } else { t[i] = node(0, 1, 1e18, 1e18, -1, -1, l, l); } return; } ll mid = (l + r) >> 1; build(i << 1, l, mid, a); build(i << 1 | 1, mid + 1, r, a); t[i] = merge(t[i << 1], t[i << 1 | 1]); } node query(ll i, ll l, ll r, ll lq, ll rq) { if (l > rq || r < lq) { return node(); } if (lq <= l && r <= rq) { return t[i]; } ll mid = (l + r) >> 1; node left = query(i << 1, l, mid, lq, rq); node right = query(i << 1 | 1, mid + 1, r, lq, rq); return merge(left, right); } void update(ll i, ll l, ll r, ll x, ll val) { if (l > x || r < x) return; if (l == r) { if (val == 0) { t[i] = node(1, 0, 1e18, 1e18, l, l, -1, -1); } else { t[i] = node(0, 1, 1e18, 1e18, -1, -1, l, l); } return; } ll mid = (l + r) >> 1; update(i << 1, l, mid, x, val); update(i << 1 | 1, mid + 1, r, x, val); t[i] = merge(t[i << 1], t[i << 1 | 1]); } }; void Solve(ll t10) { ll n, q; cin >> n >> q; vll a(n); fr(i, 0, n) { cin >> a[i]; } Segtree t(n); t.build(1, 0, n - 1, a); while (q--) { ll type; cin >> type; if (type == 2) { ll i; cin >> i; i--; a[i] = a[i] ^ 1; t.update(1, 0, n - 1, i, a[i]); } else { ll l, r; cin >> l >> r; l--;r--; auto p = t.query(1, 0, n - 1, l, r); if (p.cnt0 % 3 != 0 || p.cnt1 % 3 != 0) { cout << -1 << endl; } else { ll total = p.cnt1 / 3 + p.cnt0 / 3; total--; ll ans = min(p.min0, p.min1) + total; cout << ans << endl; } } } } int main() { fastIO; ll t;cin >> t;fr(c, 1, t + 1) Solve(c); return 0; }

#include <bits/stdc++.h> using namespace std; #include <ext/pb_ds/assoc_container.hpp> using namespace __gnu_pbds; template<class T> class ordered_set : public tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update> { public: int count(const T& x) const { return this->find(x) != this->end(); } }; ordered_set<int> add_updates, del_updates; struct PRFX0 { int n; vector<int> a, prfx0; PRFX0(vector<int> aa) : n(aa.size()), a(aa), prfx0(aa.size()+1) { add_updates.clear(); del_updates.clear(); for(int i = 0; i < n; i++) prfx0[i+1] = prfx0[i] + (a[i] == 0); } int get(int i) const { return prfx0[i] + add_updates.order_of_key(i) - del_updates.order_of_key(i); } void upd(int i) { if( add_updates.count(i) ) add_updates.erase(i); else if( del_updates.count(i) ) del_updates.erase(i); else (a[i] == 1 ? add_updates : del_updates ).insert(i); } }; void solve() { int n, q; cin >> n >> q; vector<int> a(n); for(auto& e : a) cin >> e; PRFX0 counter0(a); // maintain "alternating segments" [l_i, r_i] (like 1010... or 0101...) map<int, int> dead; // <key=l_i, value=r_i> for(int i = 0, j; i < n; i = j) { bool which = a[i]; for(j = i; j < n && a[j] == which; j++) which = !which; dead[i] = j-1; } while( q-- ) { int type = 1, l; // cin >> type; // UNCOMMENT for "Point Update" version cin >> l; l--; auto pcurr = dead.upper_bound(l); pcurr--; const auto [A, B] = *pcurr; if( type == 1 ) { // Find minimum cost for the array [al,...,ar] int r; cin >> r; r--; int cnt0 = counter0.get(r+1) - counter0.get(l); int cnt1 = (r-l+1) - cnt0; if( cnt0%3 || cnt1%3 ) { cout << "-1\n"; continue; } int ans = cnt0/3 + cnt1/3; if( r <= B ) ans++; cout << ans << "\n"; continue; } // Flip the bit at index i int indx = l; counter0.upd(indx); if( A < indx && indx < B ) { dead[A] = indx-1; dead[indx] = indx; dead[indx+1] = B; continue; } int updA = A, updB = B; if( indx == A && pcurr != dead.begin() ) { pcurr = --dead.erase(pcurr); // erase - return Iterator following the last removed element. updA = pcurr -> first; } if( indx == B && (++pcurr) != dead.end() ) { updB = pcurr -> second; dead.erase(pcurr); } if( A == indx && indx == B ) { dead[updA] = updB; } else if( indx == A ) { dead[updA] = A; dead[A+1] = B; } else { // indx == B dead[A] = B-1; dead[B] = updB; } } } int main() { ios::sync_with_stdio(0); cin.tie(0); int t; cin >> t; while( t-- ) solve(); }

Comments (74)

Write comment?

ko_osaga

8 months ago, hide # |

Auto comment: topic has been updated by ko_osaga (previous revision, new revision, compare).

→ Reply

discontinuous

+10

Thanks for the fast editorial and the amazing contest :)

David_Vivek

+13

Except for B>C, it was a beautiful contest...

baldy

8 months ago, hide # ^ |

← Rev. 2 →

-13

C was easy than B.

Nukumizu-Anna

Yes,and it can be determined whether 01 is interleaved just by using the prefix sum!

Nobita_Nobi01

bro how u check that there is a pair of same 0 or same 1 or not in a subarray

Ayush_Baghel

node of segment tree will contain two variables (left and right) -> on merging check if either of the two subpart already have the adjacent element(i.e two consecutive 1's or 0's) or their left subarray's(right) and right subarray's(left) can make it.

pawsitive

if we find the subarray to be alternating 0 and 1 or not, we can answer your question. Construct a dp which says for each index maximum length till which the sequence is alternating from that index.Then checking if index + dp[index]-1>=r or determines answer to your question, (subarray is [index,r])

rakeshpittala736

5 months ago, hide # ^ |

Use a set s for all indices 1<=i<n for which a(i)==a(i+1); then for some given l and r we can use s.lower_bound(l); This returns the pointer to an idx>=l => if this is not end pointer and value at this pointer is < r => you have a adjacent pair from l to r

KinaRight

Really?

KurtHasan

+79

B is my nightmare

wangzhilin

Agree lol.

djm03178

+23

Thank you all for participating! For fun, here are one-liner (except for inputs) python solutions for 2152A - Increase or Smash and 2152B - Catching the Krug. Although problem B turned out to be harder than my intention (but I'm glad that $$$1500$$$ points worked!), I hope you still enjoyed the problems!

A. Increase or Smash

for t in range(int(input())):
    n = int(input())
    print(len(set(map(int, input().split()))) * 2 - 1)

B. Catching the Krug

for t in range(int(input())):
    n, a, b, c, d = map(int, input().split())
    print(max(c if a<c else n-c if a>c else 0, d if b<d else n-d if b>d else 0))

+21

Every unsolved problem teaches us.

Feynman5210

Yes

literalchild

+65

If you want to be a try-hard at codegolfing, you can technically solve them in 1 line (including input reading).

The main idea is to use "\n".join(array) to solve all input instances at once.

print("\n".join([input()*0+str(2*len(set(input().split()))-1) for _ in range(int(input()))]))

We can use a lambda that takes in the input (as a list of 5 numbers) and outputs the correct answer.

print("\n".join([str((lambda inp: max(inp[3] if inp[1]<inp[3] else inp[0]-inp[3] if inp[1]>inp[3] else 0, inp[4] if inp[2]<inp[4] else inp[0]-inp[4] if inp[2]>inp[4] else 0))(list(map(int,input().split())))) for _ in range(int(input()))]))

Now, we need several lambdas, one to do precomputation and another to answer all our queries. Unfortunately, my solution needs to use itertools, making it 2 lines.

import itertools
print("\n".join([(lambda q: ((lambda q, psum: "\n".join([str((lambda lr: (-1 if (lr[1] - lr[0] + 1) % 3 or (psum[0][lr[1]] - psum[0][lr[0]-1]) % 3 else (lr[1] - lr[0] + 4) // 3 if psum[1][lr[0]-1] == psum[1][lr[1]-1] else (lr[1] - lr[0] + 1) // 3))(list(map(int,input().split())))) for _ in range(q)]))(q, (lambda a: (list(itertools.accumulate(a,initial=0)), list(itertools.accumulate([1 if a[i]==a[i-1] else 0 for i in range(1,len(a))],initial=0))))(list(map(int,input().split()))))))(int(input().split()[1])) for _ in range(int(input()))]))

If you were to unpack the lambdas, it would look like this (note that singlequery leads to RTE(1) as psum is not defined in its scope):

import itertools
singlequery = lambda lr: (-1 if (lr[1] - lr[0] + 1) % 3 or (psum[0][lr[1]] - psum[0][lr[0]-1]) % 3 else (lr[1] - lr[0] + 4) // 3 if psum[1][lr[0]-1] == psum[1][lr[1]-1] else (lr[1] - lr[0] + 1) // 3)
allquery = lambda q, psum: "\n".join([str(singlequery(list(map(int,input().split())))) for _ in range(q)])
precomp = lambda a: (list(itertools.accumulate(a,initial=0)), list(itertools.accumulate([1 if a[i]==a[i-1] else 0 for i in range(1,len(a))],initial=0)))
solve = lambda q: allquery(q, precomp(list(map(int,input().split()))))
print("\n".join([solve(int(input().split()[1])) for _ in range(int(input()))]))

Here, singlequery outputs the answer to the query. allquery processes all queries into a string. precomp generates two prefix sum arrays necessary for solving queries, and solve solves a testcase.

_LeMur_

+11

Great problems!

RustamT

First time tried D before C for more points and I hate myself. Waiting for intuition of D... Was sure it was about log2

OtterZ

Such contest might make me drop a lot,go and learn binary search

Trumpsunderwear

For problem-B, Is it true that Doran always catches Krug in atmost 'n' moves even for worst possible case?

h_maano

← Rev. 4 →

yes., its more like it catches in max n-1 move. max survival time will be n

Aayush.exe

4 months ago, hide # ^ |

yes

JeanBombeur

+145

F be like

Great problem by the way !

H_R_K

Thanks for the great contest :)

mzhao

For problem D, could someone explain why Poby and Rekkles are always able to find fresh "B"'s in their strategies? What if the array is (8, 8, 9), then one of them touches 9, then the other two elements are type A...

sorter_

I think it happens only when possible ( If Poby just first-touched a fresh B, Rekkles first-touches another fresh B when possible). And B's will have priority as they are the inflection points.

Cappybara

Type A have no problem, because Rekkles has to make a number 2^n into 2^n + 2 to be able to increase the number of moves by 1. But as soon as he increases it by 1, Poby will be making it again of the form 2^m by dividing by 2 and Rekkles has to increase it again by 2.

but if it is of the form 2^n + 1 in the start, then Poby can save atmost half of them, because if he saves 1 by dividing by 2, Rekkles makes another one of the form 2^n + 2.

any other number will be atleast of the form 2^n + 2 .... which will be eventually reduced to 2^m + 1, Rekkles will make it again atleast of the form 2^m + 2. So Poby cant save any of these numbers from Rekkles.

Why Rekkles want the number to be of the form 2^n + 2?

because when it will be reduced to 2^m + 1(m=n-1), Rekkles will again make it 2^m + 2

and so on until it reaches 3(2^1 + 1), and Rekkles will make it 4. so it increases the move count by 1.

RuchitJagodara

UPD: Found the issue, Thanks to djm03178

+25

You returned the function after printing $$$-1$$$, so you get inputs in a wrong way afterwards when soln() is called again.

+14

Oh, right, Thank you for pointing out. And apologize for the mistake.

Senku

My Solution for E using DAG 341753535

Would be great if someone could prove why it works

Basically, I tried to build a DAG using the queries where each index is a node and edges point from index with smaller value to index with greater value. Then find a path of length n + 1 such that indices on that path are monotonically increasing or decreasing. I'm not sure why a path of length n + 1 always exists in this DAG.

Noobish_Monk

As far as I understand that's what the editorial does, transitions in $$$dp$$$ can be viewed as a path in a DAG, though I might be mistaken.

This graph is literally all relations between elemenets which you can get with queries, so it will cover some construction which always appears. That construction is as follows:

there will be 1 element left. Then look at the records from queries in reverse order, and at each step pick the record closest to current element which is to its left. The DAG contains this path.

What do u mean by “there will be 1 element left”?

The one which isn't a record in any of the queries (since there are $$$n^2 + 1$$$ and each query covers at most $$$n$$$)

Ohh right. If some query returns more than n indices then that would be the answer, and if not, then your construction would be present.

Awesome proof, thanks :)

marseille

My solution for F 341757812
Brute forced the possible states. Start with all {i, i+1} and add state {i+1, pos}, where {i, i+1, pos} is the most optimal pair. Could not find a bound on the number of states but somehow it works!

AeeE5x

People who are not good at game theory:

A: 495 0:04

B: 1236 01:06

C: 1176 01:21

D: -2

OrangeEye

Why no stronger samples TAT

ashish1729

Would someone like to share how they came up with the intuition for problem D? Thanks.

kr25161

← Rev. 9 →

+19

first understand that once a element becomes a power of 2, it cannot contribute anymore to increase in no of poby operations. it gives us a base that max answer could be

$$$\sum_{i=l}^{r} \left\lfloor \log_{2} a_i \right\rfloor + (r-l+1).$$$

lets assume rekless wont add +1 to the same element twice, making it +2. it just becomes complex.
ignore the power of two elements they are of no use
now the main strategy that helps is, what happens if rekkless adds a +1 to the same element poby floor divided. will that strategy ensure that we can get maximum answer ?
happens that there are two types of elements, type1 where if rekkless keeps adding a +1 "after" the floor division, it can provide a +1 to the answer. so type1 elements always contribute to answer with "+1", as rekkless can simply add +1 to any element poby floor divides. poby can do nothing about it and its pre determined.
type2 where rekkless has to keep add a "+1" before poby floor divides it. if the first operation on such elements is floor division, they become useless, instead if its a "+1" operation they convert into type1 elements.
so the initial strategy for poby is to get rid of as many type2 elements by floor divinding them once and making them useless for further, and so for rekkless is to do +1 to as many elements type2 and converting them into type1 elements.
so rekkless can force the game to always achieve

$$$\sum_{i=l}^{r} \left\lfloor \log_{2} a_i \right\rfloor + \text{type1 in } [l,r] + \left\lfloor \frac{\text{type2 in } [l,r]}{2} \right\rfloor

$$$

we can see that "+2" case is not needed in a optimal sequence of moves.

ok, thanks for writing this.. I will spend some time understanding this.

its_vk

Great explanation. Thank you.

LXL4510

B is unexpectedly difficult. but i finally solve it. E is expectedly difficult. but i don't solve it untill end. ;(

Can anyone share how to think of solution of E ?

_Kee

Take a look at my editorial for problem E.

(Initially I wrote it as a comment here, but Codeforces blocked me from posting it, saying "The comment contains source code without markup." So I put it in my blog...)

shiny_shine

Reached Master with this contest, thanks for the amazing A-E and brute-force-able F :)

If the time limit is 2s

_ThanhDat_

congratulations! I wish someday could reach Master just like you did that day

dream7

Why does my code works? Can anyone explain? code:problem D

I basically divided initial v[i]s based on who act first on that element. I calculated #ops it takes to make it 1, by starting from v[i] (first op made by player A) and by starting at v[i]+1 (first op made by player B). This way, I calculated what all v[i] take +1 extra operation when player B act first on it.

Then result of [l,r] is = orignal #ops + cnt/2, where cnt is total number of v[i]s where you have chance to increase operation by +1 if player B starts first.

Girgit01

7 months ago, hide # ^ |

why cnt/2 shouldn't it be cnt — 1 as for all the v[i] B will act first and increase value by 1 except in the starting case as A has to make the first move

harshcooljn

New Problem Suggestion as C2 : Triple Removal (Hard Version)

In this version of the problem there will be 2 kinds of queries

1 l r : To find minimum cost for the array [al,...,ar]
2 i : Flip the bit at index i (i.e set a[i] = a[i]^1) (Point update)

I got this idea while solving C using segment tree

My solution for C : https://mirror.codeforces.com/contest/2152/submission/341788525

Inspired solution for the new version of the problem —

Node Structure

Solution

Please let me know if there exists an easier solution for this

Badri41

I think such complicated node structure is not required simple version of fenwick tree works here

define index $$$BIT[i]$$$ = 1 if $$$s[i] == s[i - 1]$$$ else $$$0$$$ Find segment sum and check if its positive for checking alternating in a segment and then we can do point updates by carefully update the value at $$$i$$$, and $$$i + 1$$$ indices after flipping $$$i$$$.

remyawka

For checking is subarray alternating (with flip bit update), we can use only std::map<int, int>.

But problem with counting $$$0$$$ and $$$1$$$ in range — btw it possible to solve with ordered_set.

All array is covered by disjoint alternating segments. For example: 010|0|0|0101|10

Let maintain this $$$[l_i, r_i]$$$ alternating segments in $$$map[l_i] = r_i$$$. So we can answering is subarray contained in some alternating segments in $$$\log$$$.

Flipping the bit affect only $$$3$$$ segments (in situation ..01|1|10..), so updating cost $$$3 \cdot \log$$$ at worst case. (but it so painful to accurate realisation)

To deal with remain part, we essentially need to provide $$$prfx\text{_}sum$$$ with just $$$\text{a}[i] = \text{a}[i] \pm 1$$$ updates. (pls, I don't want to learn cheater data structure like BIT or segment tree ＞﹏＜)

Let create ordered_multiset plus_pos and minus_pos: for evry $$$\text{a}[i] = \text{a}[i] + 1$$$ operation we insert $$$i$$$ in plus_pos and similarly with minus_pos. (!!! bad O(Q) space).

Thank to order_of_key(i) (which return the number of items that are strictly smaller than $$$i$$$), we can corrective: $$$prfx\text{_}sum[i] = prfx\text{_}sum_0[i] + \text{plus_pos.order_of_key}(i) - \text{minus_pos.order_of_key}(i)$$$.

But structure of this task provides that plus_pos.count(i) at most 1, so ordered_set enough. (,,,finaly)

To check, before each [L, R] query I twice flipping a[L]: 342144368

code

useless info

subtomyonlycodes

I hate that i dont get problem D. how do people even solve it?

IUA_Hasin

Problems like B shouldn't be given in a contest.

ywjylx

The scores of H1 and H2 should be swapped.

Celebrate

Naturally come up with a link-cut-tree solution for G.

DSG213

+16

There is in alternative solution for F.

I used a similar method to the one listed in the tutorial using jump pointers but with a different transition states. Each state is a pair (a,b) where b is the current most right index, and a is the previous index. There is a special case with a==-1, which means that we are free to find the next index. (a,b) transitions to (b,c) where c is the first element with x[a] + z < x[c]. This can be found using binary search. We start by computing all transitions for (-1,i), and transitions from states that follow. I don't have a proof for it but we should visit O(n) states in total. The we do jump pointers and for each query move from (-1,l)

Example solution https://mirror.codeforces.com/contest/2152/submission/341761304

polosatic

Bro, you're not alone! I also came up with a very similar idea. Here's the formal proof for its complexity and an argument for why this approach is arguably more elegant than the editorial's.

My implementation is slightly different: I start from pairs $$$(i, i+1)$$$ (using 0-based indexing) and a sequence terminates when it generates an invalid pair like $$$(i, n)$$$. You can see my submission here: 342191794

The proof of $$$O(n)$$$ states

The key claim is that the total number of unique pairs $$$(i, j)$$$ generated is bounded by $$$\sim 4n$$$. My solution gets RE with a buffer of $$$3N$$$ for the states, but gets AC with $$$4N$$$. Let's formalize the model. Let $$$f(i)$$$ be the function from the editorial: $$$f(i) = \min {(j | j \gt i, x[j] \gt x[i] + z})$$$. Our state transition function is $$$g((i, j)) = (j, max(j + 1, f(i)))$$$. The entire solution explores a functional graph where states are pairs $$$(i, j)$$$ and edges are defined by $$$g$$$. To prove the linear bound, we can split the array $$$x$$$ into blocks, where a block ends at index $$$k$$$ if $$$x[k+1] - x[k] \gt z$$$.

Counting "boundary crossing" pairs ($$$\sim 1n$$$ states)

When a transition crosses from block $$$B_k$$$ to $$$B_{k+1}$$$, the new pair is always $$$(L, R)$$$ where $$$R$$$ is the first element of $$$B_{k+1}$$$, and $$$L$$$ is some element from $$$B_k$$$. The number of such pairs is at most the sum of sizes of all blocks except the last one: $$$n - |B_{last}|$$$. Also I use invalid $$$(i, n)$$$ pairs in my implementation. Note that the index $$$i$$$ here must be taken from $$$B_{last}$$$. The number of these pairs is at most $$$|B_{last}|$$$. Summing these two gives $$$(n - |B_{last}|) + |B_{last}| = n$$$. So, all "boundary crossing" transitions generate at most $$$n$$$ unique states in total.

Counting "in-block" pairs ($$$\sim 3n$$$ states)

Consider the chain $$$(i, i+1) \to (i+1, f(i)) \to (f(i), f(i+1)) \dots$$$ Note that the chain is correct because $$$f(i) \gt i + 1$$$, because $$$x_{f(i)} \gt x_i + z$$$ by definition, and $$$x_{i+1} \le x_i + z$$$ because $$$i$$$ & $$$i + 1$$$ are in the same block, and $$$x$$$ is monotonous.

Let's now split all the pairs into $$$3$$$ groups and count them.

Type 1: Base pairs $$$(k, k+1)$$$. There are $$$n-1$$$ of them.

Type 2: First-jump pairs $$$(k+1, f(k))$$$. Each base pair generates one of these. $$$\sim n$$$ states.

Type 3: Synchronized-jump pairs $$$(f(k), f(k+1))$$$. Their number is also $$$\sim n$$$, because we have them for $$$k = 1 \dots n-1$$$

Together, these account for $$$\sim 3n$$$ states within the blocks.

Summing up the boundary states ($$$\sim 1n$$$) and in-block states ($$$\sim 3n$$$), we get the total bound of $$$4n$$$ states.

Why this approach is more unified than the editorial's

The editorial's solution feels a bit hacky. Our solution is more elegant because it's unified. There is only one mode of operation: We precompute a single graph of states $$$(i, j)$$$. The logic of path merging (the LCA part) is implicitly baked into our graph structure — the transition to $$$(LCA, LCA + 1)$$$ in author's solution is the transition from one block to another in our solution: Let's see: $$$[\dots i \dots j \dots] \;\;\; [x \; y]$$$, where $$$i$$$ and $$$j$$$ — some elements of the left block, $$$x$$$ & $$$y$$$ — the first 2 elements of the right block (for simplification, we consider only $$$|B_{right}| \ge 2$$$). The equation $$$f(x) = f(y)$$$ (going to LCA) is equivalent to the transition $$$(i, j) \to (j, x) \to (x, y)$$$.

flight

How does this work? We can compute the chain one step further, giving $$$(k, k+1) \to (k+1, f(k)) \to (f(k), f(k+1)) \to (f(k+1), f(f(k))).$$$ It's not obvious to me why $$$(f(k+1), f(f(k)))$$$ is in one of the three categories you proposed, and I'm pretty confident I can find a counterexample.

snowysecret

Check out my explanation to problem F!

shinchankosen

H1 is able to solved by in O(nq) time using tree DP.

DNR

Alternate sqrt solution for F:

Define $$$\text{nxt}(i)$$$ to be the smallest $$$j \gt i$$$ such that $$$a_i + z \lt a_j$$$.
Notice that greedily building the subsequence from left to right is optimal for every query (ie. start with $$$S = [l, l + 1]$$$, then at every step, let $$$x$$$ and $$$y$$$ be the second last/last elements in $$$S$$$, and we add $$$\max(\text{nxt}(x), y + 1)$$$ to $$$S$$$. We do this until the index to be added remains $$$\leq r$$$).
Divide the array into blocks of size $$$B$$$.
For every pair of indices $$$i, j$$$ $$$(i \lt j)$$$ belonging to the same block $$$b$$$, precompute (a) the state it ends up at upon first exiting this block if we enter with state $$$(x = i, y = j)$$$ (b) the number of jumps required to do so. All of this can be done in $$$O(B^2)$$$ per block, and thus takes $$$O((n/B) \cdot B^2)$$$ time in total.
For every query $$$l, r$$$, start with $$$x = l, y = l + 1$$$, and until $$$y \leq r$$$: (a) if $$$x$$$ and $$$y$$$ lie in the same block and $$$r$$$ doesn't lie in the same block, use the precomputed info to jump out of this block in $$$O(1)$$$ (b) otherwise manually make $$$x$$$ jump to $$$\max(\text{nxt}(x), y + 1)$$$ in $$$O(1)$$$. We can prove that this process terminates within $$$O(n/B)$$$ iterations, so we answer each query in $$$O(n/B)$$$ time.

A poor implementation of this idea can be found here. Unfortunately, accessing the precomputed information is horribly cache-unfriendly to the point where I don't think this can be made to pass.

Asim020202

I was a pupil in this test.

Alternate linear solution for H1:

Let's try to solve the problem for a single query with value $$$l$$$. We root the tree at node $$$1$$$.

Observation 1: Any optimal selection of red nodes forms a connected component.

Proof

Observation 2: For any leaf $$$u$$$, it's optimal to assign it a weight of $$$\max(0, l - y)$$$, where $$$y$$$ is the weight of the edge from $$$u$$$ to its parent.

Let's extend this idea further. We'll assign weights to vertices in a bottom-up manner (so when assigning $$$w_u$$$, $$$w_v$$$ for all children $$$v$$$ of $$$u$$$ would already have been assigned).

Some definitions:

$$$S(u, v)$$$ — a set of red nodes with the minimum cost which contains $$$u$$$ but not $$$v$$$
$$$C(u, v)$$$ — the cost of $$$S(u, v)$$$.
$$$p_u$$$ — the parent of u.
$$$g(u, v)$$$ — the weight of the edge $$$(u, v)$$$.

For every $$$u$$$, we will compute $$$C(u, p_u)$$$, where $$$p_u$$$ is the parent of $$$u$$$. It's not difficult to see that:

$$$C(u, p_u) = g(u, p_u) + w_u + \sum_{v \in \text{children}(u)} (\min(g(v, p_v), C(v, p_v) - g(v, p_v)))$$$

(for every child $v$, we choose to either take the cost of the optimal component from below, or that of just the edge)

Observation 3: It's optimal to assign node $$$u$$$ a weight of $$$\max(0, l - g(u, p_u) - \sum_{v \in \text{children}(u)} (\min(g(v, p_v), C(v, p_v) - g(v, p_v))))$$$ (define $$$g(1, p_1)$$$ to be $$$0$$$).

This works in $$$O(n)$$$ per query and ends up being very easy to implement.

JMK-vineetarora

cool, i thought the same but was convinced i was missing something, cause how can a 2900 collapse that easily

rJ_YsenM2

I’m really sorry to post this here, but I need some help. In this contest, my main account rJ_ysenM was banned immediately after my first “skip”. I believe it’s a mistake because I did not cheat or engage in any suspicious behavior. In fact, I even ran the problems through several AI language models and got totally different solutions from mine.

I understand that skipping some easy problems and go solve harder problems right away can look suspicious, but if you review my contest history, you’ll see I only do that in topics I’m deeply familiar with (primarily graphs and combinatorics).

I realize you may have strict anti-cheat measures in place, which is why I’m reaching out directly now. I’ve already contacted Mike but haven’t heard back, so a friend suggested I try here or reach out to KAN (which i also did but i know both of them are busy)

I was so close to reaching Master and I’d really appreciate any help restoring my account. Thank you for your time, and sorry again for any inconvenience.

zltzlt

7 months ago, hide # |

I have an alternative solution for H1:

First, it is clear that the red points form a connected component. We can write the following linear program (let $$$C$$$ denote a connected component):

$$$ \begin{aligned} \text{minimize}\quad & \sum\limits_{i = 1}^n x_i \\ \text{s.t.}\quad & \forall C, \sum\limits_{(u, v) \in E, u \in C, v \notin C} d_{(u, v)} + \sum\limits_{u \in C} x_u \ge l \\ & x_i \ge 0 \end{aligned} $$$

Taking the dual, we have:

$$$ \begin{aligned} \text{maximize}\quad & \sum\limits_C y_C \left(l - \sum\limits_{(u, v) \in E, u \in C, v \notin C} d_{(u, v)}\right) \\ \text{s.t.}\quad & \forall u, \sum\limits_{u \in C} y_C \le 1 \\ & y_C \ge 0 \end{aligned} $$$

If we assume that $$$y_C$$$ takes integer values, the problem becomes equivalent to selecting several connected components such that each vertex is contained in at most one component, and each selected component $$$C$$$ has a value of $$$l - \sum\limits_{(u, v) \in E, u \in C, v \notin C} d_{(u, v)}$$$. The goal is to maximize the total value of the selected components.

Consider a tree DP. Let $$$f_{u, 0/1}$$$ denote the maximum total value of connected components within the subtree of $$$u$$$, with $$$u$$$ either being included in or excluded from a connected component. The transition is straightforward.

Time complexity: $$$O(nq)$$$

Implementation

#include <bits/stdc++.h>
#define pb emplace_back

using namespace std;
typedef long long ll;
typedef pair<ll, ll> pii;

const int maxn = 250100;

ll n, m, q, f[maxn][2];
vector<pii> G[maxn];

void dfs(int u, int fa) {
	f[u][0] = f[u][1] = 0;
	for (auto [v, d] : G[u]) {
		if (v == fa) {
			continue;
		}
		dfs(v, u);
		f[u][0] += max(f[v][0], f[v][1] + m - d);
		f[u][1] += max({f[v][0] - d, f[v][1], f[v][1] + m - d * 2});
	}
}

void solve() {
	scanf("%lld", &n);
	for (int i = 1; i <= n; ++i) {
		vector<pii>().swap(G[i]);
	}
	for (int i = 1, u, v, d; i < n; ++i) {
		scanf("%d%d%d", &u, &v, &d);
		G[u].pb(v, d);
		G[v].pb(u, d);
	}
	scanf("%lld", &q);
	while (q--) {
		scanf("%lld", &m);
		dfs(1, -1);
		printf("%lld\n", max(f[1][0], f[1][1] + m));
	}
}

int main() {
	int T = 1;
	scanf("%d", &T);
	while (T--) {
		solve();
	}
	return 0;
}

geruome

I bet the question setter is a T1 fan

ritchie_s

-8

even the first problem felt difficult to me....

Tadas

6 months ago, hide # |

Is C proof complete?

This part seems not to be strict or detailed enough. "Suppose that there are two indices i,j such that $$$c_j\geq2,0 \lt i \lt 3k,0\leq j\leq 3k$$$ , and $$$i \ne j$$$ . Then it is possible to perform the operations of cost 1 to remove every 0 s between $$$i$$$ -th 1 and $$$(i+1)$$$ -th 1 . "

How can we be sure that it won't lead to this situation? "Otherwise, $$$c_1=c_2=...=c_{3k-1}=1$$$ and $$$c_0,c_{3k}\leq1$$$ . In this case, every pair of adjacent elements in $$$[a_l,a_{l+1},...,a_r]$$$ is different."

Is it because we can remove 0s between i-th 1 and i+1th 1, ending up with reversed situation (now 11 are adjacent which can be used to produce another 00 pair (after removing that 11)?)

RulesOut

5 months ago, hide # |

I think any1 who played chess knows the problem B,it is quite similar as the single rook checkmate

4 months ago, hide # |

← Rev. 5 →

I'm struggling to understand D explanation. I suppose Poby's (P) strategy first move is to start with B type element and respond to Rekkles (R) as described. I agree that strategy concerning B is optimal. But why is it optimal for both sides to apply operation for the most recently selected index? For one element, it's clear, but when players have more options, can't it be more beneficial for them to choose other numbers? I don't think the proof provided is strict. I understand that R has to react when number is 2^k+1 as it's the moment, when it can make the answer worse for P, but it's not every turn that x is of shape 2^k+1 (unless he will run out of good moves and will be forced to +1 earlier). I checked empirically that R moves doesn't make a difference for P in other cases.

To add up to editorial, worse one-time jump $$$\lfloor\frac{x+2}{2}\rfloor$$$ doesn't increase the initial answer (we can treat floor f(x) transformed to f(x+1) because of idleness and notice that the answer changes when transitioning from 2^k (=k) to 2^k+1 (=k+1), but when x is of B type, it should be 2^l+1=2^k, which is possible only for l=0). This as well means that P could not worry about R increasing index until it reaches from 2^{k} + 2 (=k+1 moves) to 2^{k+1} + 1(/=2 leads to k+1 total), so for R it could be counter-productive to raise this index any further, it's better to ignore it and focus on others. Also it was strange to see lemma for (+1, /2) operations at first, not vice-versa (reversed actions), but later it was clear why it's needed.

dejunchen

Problem B is great!

ko_osaga's blog