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
Tutorial is loading...
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';
}
}
Spoiler
Tutorial is loading...
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';
}
}
Spoiler
Tutorial is loading...
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
Tutorial is loading...
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();
}
Spoiler
Tutorial is loading...
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();
}
Spoiler
Tutorial is loading...
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";
}
}
}
Spoiler
Tutorial is loading...
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
Tutorial is loading...
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
Tutorial is loading...
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";
}
}
Auto comment: topic has been updated by ko_osaga (previous revision, new revision, compare).
Thanks for the fast editorial and the amazing contest :)
Except for B>C, it was a beautiful contest...
C was easy than B.
Yes,and it can be determined whether 01 is interleaved just by using the prefix sum!
bro how u check that there is a pair of same 0 or same 1 or not in a subarray
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.
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])
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
Really?
B is my nightmare
Agree lol.
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!
Every unsolved problem teaches us.
Yes
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.We can use a lambda that takes in the input (as a list of 5 numbers) and outputs the correct answer.
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.If you were to unpack the lambdas, it would look like this (note that
singlequeryleads to RTE(1) as psum is not defined in its scope):Here,
singlequeryoutputs the answer to the query.allqueryprocesses all queries into a string.precompgenerates two prefix sum arrays necessary for solving queries, andsolvesolves a testcase.Great problems!
First time tried D before C for more points and I hate myself. Waiting for intuition of D... Was sure it was about log2
Such contest might make me drop a lot,go and learn binary search
For problem-B, Is it true that Doran always catches Krug in atmost 'n' moves even for worst possible case?
yes., its more like it catches in max n-1 move. max survival time will be n
yes
F be like
Great problem by the way !
Thanks for the great contest :)
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...
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.
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.
UPD: Found the issue, Thanks to djm03178
You returned the function after printing $$$-1$$$, so you get inputs in a wrong way afterwards when
soln()is called again.Oh, right, Thank you for pointing out. And apologize for the mistake.
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.
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 :)
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!
People who are not good at game theory:
A: 495 0:04
B: 1236 01:06
C: 1176 01:21
D: -2
Why no stronger samples TAT
Would someone like to share how they came up with the intuition for problem D? Thanks.
$$$
ok, thanks for writing this.. I will spend some time understanding this.
Great explanation. Thank you.
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 ?
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...)
Reached Master with this contest, thanks for the amazing A-E and brute-force-able F :)
If the time limit is 2s
congratulations! I wish someday could reach Master just like you did that day
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.
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
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 for segment tree : (in the following definitions "range" refers to the range that the segment tree node is responsible for)
cnt0 = frequency of 0 in the range
cnt1 = frequency of 1 in the range
min0 = minimum distance between 2 zeros in the range
min1 = minimum distance between 2 ones in the range
f0 = index of first occurrence of 0 in the range
l0 = index of last occurrence of 0 in the range
f1 = index of first occurrence of 1 in the range
l1 = index of last occurrence of 1 in the range
Please let me know if there exists an easier solution for this
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$$$.
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
... I spent on this 5+ hours ((((
I hate that i dont get problem D. how do people even solve it?
Problems like B shouldn't be given in a contest.
The scores of H1 and H2 should be swapped.
Naturally come up with a link-cut-tree solution for G.
code
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)wherebis the current most right index, andais the previous index. There is a special case witha==-1, which means that we are free to find the next index.(a,b)transitions to(b,c)wherecis the first element withx[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
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)$$$.
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.
Check out my explanation to problem F!
H1 is able to solved by in O(nq) time using tree DP.
Alternate sqrt solution for F:
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.
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.
If the set of red nodes form two connected components, then you can delete one and that will strictly improve the answer since the contribution of the remaining component isn't affected and that of the deleted one becomes $$$0$$$.
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.
Fix any optimal assignment of weights $$$w$$$.
Then in this assignment, the minimum cost coloring where $$$u$$$ is colored red is one of the following:
So in both situations, the necessary lowerbound on $$$w_u$$$ is $$$l - y$$$, and we assign $$$u$$$ the lowest possible weight, which is $$$\max(0, l - y)$$$ (since all weights must be non-negative).
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:
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:
(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$$$).
Exercise for the reader. The outline is the same as the case for leaves, you just have to consider the fact that we now have some children and we know for certain the choice we're going to make between choosing the edge going to a child or some component including the child (since these choices are independent from the rest of the assignment).
This works in $$$O(n)$$$ per query and ends up being very easy to implement.
cool, i thought the same but was convinced i was missing something, cause how can a 2900 collapse that easily
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.
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):
Taking the dual, we have:
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)$$$
I bet the question setter is a T1 fan
even the first problem felt difficult to me....
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)?)
I think any1 who played chess knows the problem B,it is quite similar as the single rook checkmate
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.
Problem B is great!