Codeforces Round 1129 (Div. 2)
Starting from this post, I would also try to extract reusable methodologies and insights (proposed “Reflection” section) from problems rather than merely document how to solve.
Table of Contents
1. A. Subset Selecting
1.1. Solution
To obtain MEX \(m\), we need groups whose maximums are \(0,1,\dots,m-1\). Since groups do not require preserving order, so to construct a group that has maximum \(i\), two conditions need to be satisfied.
- There exists \(i\)
- There are some other \(k-1\) elements that \(\le i\), to form a group.
These should hold for all \(0,1,\dots,m-1\). So we can simply do a linear scan.
1.2. Reference Code
#include <bits/stdc++.h>
void work() {
int n, k;
std::cin >> n >> k;
std::vector<int> a(n);
std::vector<int> cnt(n + 1, 0);
for (auto &x : a)
std::cin >> x, cnt[x]++;
int ans = 0, rem = 0;
for (int c = 0; c <= n; c++) {
rem += cnt[c];
if (cnt[c] == 0 or rem < k)
break;
rem -= k;
ans++;
}
std::cout << ans << "\n";
}
int main() {
int n;
std::cin >> n;
while (n--)
work();
}
4. D1. Number Operating (Easy Version)
4.1. Solution
For any \(x\) such that \(2^{k}-1 \le x \lt 2^{k+1}-1\), if \(x = 2^{k}-1\), then \(f(x) = k\). Specially, \(f(0) = 0\).
Then, we can compute \(f(x)\) in \(O(\log n)\) time. To approach \(x\), we have two ways
- First, get \(2^{k+1}-1\), then repeatedly \(x \gets x-1\). This costs \(k+1 + (2^{k+1}-1-n)\) steps.
- First, get \(2^{k}-1\), then reset counter with one \(x \gets x-1\). The problem becomes a subproblem of \(f(x - 2^{k} + 2)\). Therefore, this costs \(k+1+f(n-2^{k}+2)\) steps.
Now prove that, only considering these choices is sufficient. Denote the \(i\)-th consecutive operation 1 sequence of length \(l\) as \(a_{i}\), therefore obtaining \(x\) is equivalent to a sequence of \(a_{1}, a_{2}, \dots, a_{m}\) separated by operation 2. Suppose there are \(q\) operation 2. Therefore
\[ x = \sum_{i=1}^{m} (2^{a_{i}}-1) - q, \qquad q \ge m-1 \]
Then, we observe that:
- \(a_{i} \ge 2\). Because a \(a_{i}=1\) can be cancelled out with an operation 2, reducing the total steps by \(2\).
If there’re \(a_{i}=a_{j}=a\), we can actually merge them together, which is equivalent to one sequence of OP1 of length \(a_{i}+1\) plus an operation 2. The total number of steps decreases by \(2a-a-2=a-2\). As in (1), \(a\ge 2\), this cancellation never degrades.
\[ 2(2^{a}-1)=2^{a+1}-1-1 \]
So far, we proved that uniqueness of \(a_{i}\) and \(a_{i} \ge 2\). If all \(a_{i}\lt k\), then the maximum value of \(x\) we can get is
\[ \sum_{i=2}^{k-1}(2^{i}-1) - (k-3) = 2^{k}+1-2k \lt 2^{k}-1 \le x \]
Therefore, there must be some \(a_{i} \ge k\). And also, there shouldn’t exist \(a_{i} \ge k+2\), for it’ll cost more steps than \(a_{i}=k+1\) as it’ll subtract more ones from \(x\).
Therefore, the largest \(a_{i}\) must be either \(k\) or \(k+1\), resulting in the forementioned two choices respectively.
Now as we can see, \(x-2^{k}+2\) always reduces the size of problem (at least) by half, therefore it’s \(O(\log n)\). Bruteforcing over \([l,r]\) to compute recursively for each number produces a \(O(n\log n)\) solution, which is able to pass D1.
4.2. Reflection
4.3. Reference Code
#include <algorithm>
#include <iostream>
void work() {
long long l, r;
std::cin >> l >> r;
auto calc = [&](auto F, long long n) -> long long {
if (n == 0)
return 0;
int k = 63 - __builtin_clzll(n + 1);
long long p = 1LL << k;
if (n == p - 1)
return k;
long long ans = k + 1 + (p * 2 - 1 - n);
if (k >= 2)
ans = std::min(ans, k + 1 + F(F, n - p + 2));
return ans;
};
const long long mod = 998244353;
long long ans = 0;
for (long long n = l; n <= r; n++)
ans = (ans + calc(calc, n)) % mod;
std::cout << ans << '\n';
}
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int t;
std::cin >> t;
while (t--)
work();
}
5. D2. Number Operating (Hard Version)
5.1. Solution
5.2. Reflection
- Although an operation relies on history, after operating a consecutive sequence of such operations, can we describe its total effect and total cost with (single) parameters?
- Prove an upper or lower bound to reduce the number of states that requires computation.