Thanks for participation!
The official solution of E is $$$O(n)$$$. If your solution of E has a larger complexity, I recommend reading the tutorial.
The optimal sequence of operations is very simple.
The optimal sequence of operations is adding $$$k-1$$$ 1-s into the set each time, at the same time decreasing $$$n$$$ by $$$k-1$$$. This implies that the answer is $$$\lceil \frac{n-1}{k-1}\rceil$$$.
I failed to find a Div2-A level proof. If you have a simpler proof please share it in the comments.
Consider the number of elements that is $$$\equiv 1\pmod{(k-1)}$$$ in the set. The number of such elements increase by at most $$$k-1$$$ in each operation, and the aforementioned sequence of operation achieves the maximum increment.
t = (int)(input())
for _ in range(t):
n, k = map(int, input().split())
print((n - 1 + k - 2) // (k - 1))
"Most sequences" can be transformed into $$$[1]$$$. Conditions for a sequence to be un-transformable is stringent.
Find several simple substrings that make the string transformable.
We list some simple conditions for a string to be transformable:
- If 111 exists somewhere (as a substring) in the string, the string is always transformable.
- If 11 appears at least twice in the string, the string is always transformable.
- If the string both begins and ends with 1, it is always transformable.
- If the string begins or ends with 1 and 11 exists in the string, it is always transformable.
These can be found by simulating the operation for short strings on paper.
Contrarily, if a string does not meet any of the four items, it is always not transformable. This can be proved using induction (as an exercise).
t = (int)(input())
for _ in range(t):
n = (int)(input())
a = input()
ok = 0
if a.count("111") >= 1:
ok = 1
if a.count("11") >= 2:
ok = 1
if a.count("11") >= 1 and (a[0] == "1" or a[-1] == "1"):
ok = 1
if a[0] == "1" and a[-1] == "1":
ok = 1
if ok:
print("Yes")
else:
print("No")
1988C - Increasing Sequence with Fixed OR
The answer is a simple construction.
The maximum length for $$$2^k-1\ (k>1)$$$ is $$$k+1$$$.
It's obvious that the answer only depends on the popcount of $$$n$$$. Below, we assume $$$n=2^k-1$$$. If $$$k=1$$$, it is shown in the samples that the length is $$$1$$$.
Otherwise, the maximum sequence length for $$$2^k-1$$$ is $$$k+1$$$. This can be achived by $$$a_i=n-2^{i-1}\ (1\le i\le k),a_{k+1}=n$$$.
Consider the value of $$$a_1$$$. Note that its $$$k$$$-th bit (indexed from $$$2^0$$$ to $$$2^{k-1}$$$) should be 0, otherwise we would not make use of the largest bit.
Since $$$a_1$$$ and $$$a_2$$$'s OR is $$$n$$$, $$$a_2$$$'s $$$k$$$-th bit should be 1, and thus the construction of $$$a_2\sim a_{k+1}$$$ boils down to the subproblem when $$$n=2^{k-1}-1$$$. This shows that $$$f(k)\le f(k-1)+1$$$ where $$$k$$$ is the popcount of $$$n$$$. We know that $$$f(2)=3$$$, so $$$f(k)\le k+1$$$ for all $$$k\ge 2$$$.
t = (int)(input())
for _ in range(t):
n = (int)(input())
a = []
for i in range(62, -1, -1):
x = 1 << i
if ((x & n) == x) and (x != n):
a.append(n - x)
a.append(n)
print(len(a))
for i in a:
print(i, end=" ")
print("")
1988D - The Omnipotent Monster Killer
Formulate the problem.
Some variables can't be large.
Suppose monster $$$i$$$ is killed in round $$$b_i$$$. Then, the total health decrement is the sum of $$$a_i\times b_i$$$. The "independent set" constraint means that for adjacent vertices, their $$$b$$$-s must be different.
Observation: $$$b_i$$$ does not exceed $$$\lfloor \log_2 n\rfloor+1$$$. In this problem, $$$b_i\le 19$$$ always holds for at least one optimal $$$a_i$$$.
Let the mex of a set be the smallest positive integer that does not appear in it. Note that in an optimal arrangement, $$$b_i=\mathrm{mex}_{(j,i)\in E} b_j$$$.
Consider an vertex with the maximum $$$b$$$, equal to $$$u$$$. Root the tree at this vertex $$$x$$$. The vertices connected with $$$x$$$ should take all $$$b$$$-s from $$$1$$$ to $$$u-1$$$. Denote $$$f(u)$$$ as the minimum number of vertices to make this happen, we have
This ends the proof.
By dp, we can find the answer in $$$O(n\log n)$$$ or $$$O(n\log^2 n)$$$, depending on whether you use prefix/suffix maximums to optimize the taking max part.
Bonus: Find a counterexample for $$$b_i\le 18$$$ when $$$n=300000$$$. (Pretest 2 is one case)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n;
ll a[300005], f[300005][24], smn[30];
vector<int> g[300005];
void dfs(int x, int fa) {
for (int i = 1; i <= 22; i++) f[x][i] = i * a[x];
for (int y : g[x]) {
if (y == fa) continue;
dfs(y, x);
ll tt = 8e18;
smn[23] = 8e18;
for (int i = 22; i >= 1; i--) {
smn[i] = min(smn[i + 1], f[y][i]);
}
for (int i = 1; i <= 22; i++) {
f[x][i] += min(tt, smn[i + 1]);
tt = min(tt, f[y][i]);
}
}
}
void Solve() {
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
for (int i = 1, x, y; i < n; i++) {
cin >> x >> y;
g[x].push_back(y), g[y].push_back(x);
}
dfs(1, 0);
cout << *min_element(f[1] + 1, f[1] + 23) << '\n';
for (int i = 1; i <= n; i++) {
g[i].clear();
memset(f[i], 0, sizeof(f[i]));
}
}
int main() {
ios::sync_with_stdio(0), cin.tie(0);
int t;
cin >> t;
while (t--) Solve();
}
Formulate the problem on a cartesian tree.
Find a clever bruteforce. Calculate the time complexity carefully.
Build the cartesian tree of $$$a$$$. Let $$$lc_x,rc_x$$$ respectively be $$$x$$$'s left and right children.
Consider a vertex $$$x$$$. If we delete it, what would happen to the tree? Vertices that are on the outside of $$$x$$$'s subtree will not be affected. Vertices inside the subtree of $$$x$$$ will "merge". Actually, we can see that, only the right chain of $$$x$$$'s left child ($$$lc_x\to rc_{lc_x}\to rc_{rc_{lc_x}}\to \dots$$$) and the left chain of $$$x$$$'s right child will merge in a way like what we do in mergesort.
Now, if we merge the chains by bruteforce (use sorting or std::merge), the time complexity is $$$O(n)$$$! It's easy to see that each vertex will only be considered $$$O(1)$$$ times.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pr;
int n, a[500005], st[500005], c[500005][2], top, sz[500005];
ll ans[500005], atv[500005], sum;
void dfs1(int x) {
sz[x] = 1;
for (int i = 0; i < 2; i++)
if (c[x][i]) dfs1(c[x][i]), sz[x] += sz[c[x][i]];
sum += (atv[x] = (sz[c[x][0]] + 1ll) * (sz[c[x][1]] + 1ll) * a[x]);
}
void dfs2(int x, ll dlt) {
ll val = sum - dlt - atv[x];
vector<int> lr, rl;
vector<pr> ve;
int y = c[x][0];
while (y) lr.push_back(y), val -= atv[y], y = c[y][1];
y = c[x][1];
while (y) rl.push_back(y), val -= atv[y], y = c[y][0];
{
int i = 0, j = 0;
while (i < lr.size() || j < rl.size()) {
if (j >= rl.size() || (i < lr.size() && j < rl.size() && a[lr[i]] < a[rl[j]])) {
ve.push_back(pr(lr[i], 0));
i++;
} else {
ve.push_back(pr(rl[j], 1));
j++;
}
}
}
// cout << x << ' ' << val << '\n';
int cursz = 0;
for (int i = (int)ve.size() - 1; i >= 0; i--) {
int p = ve[i].first, q = ve[i].second;
// cout << "I:" << i << ' ' << cursz << '\n';
val += (cursz + 1ll) * (sz[c[p][q]] + 1ll) * a[p];
cursz += sz[c[p][q]] + 1;
}
ans[x] = val;
for (int i = 0; i < 2; i++)
if (c[x][i]) dfs2(c[x][i], dlt + 1ll * (sz[c[x][i ^ 1]] + 1) * a[x]);
}
void Solve() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
st[top = 0] = 0;
for (int i = 1; i <= n; i++) {
while (top && a[st[top]] > a[i]) top--;
c[i][0] = c[st[top]][1], c[st[top]][1] = i;
st[++top] = i;
}
int rt = st[1];
sum = 0, dfs1(rt), dfs2(rt, 0);
for (int i = 1; i <= n; i++) cout << ans[i] << ' ';
cout << '\n';
for (int i = 0; i <= n; i++) c[i][0] = c[i][1] = 0;
}
int main() {
int t;
scanf("%d", &t);
while (t--) Solve();
}
We can use dp to calculate the number of permutations of $$$1\sim n$$$ with $$$i$$$ prefix maximums and $$$j$$$ ascents, $$$f(n,i,j)$$$: consider where 1 is inserted, we will have a $$$O(n^3)$$$ dp that finds $$$f(n,i,j)$$$ for all suitable $$$(n,i,j)$$$-s.
For suffix maximums, (the number of permutations of $$$1\sim n$$$ with $$$i$$$ prefix maximums and $$$j$$$ ascents, $$$g(n,i,j)$$$, we can just reverse some dimension of $$$f$$$).
To calculate the answer, consider the position of $$$n$$$. Suppose it's $$$p$$$. The the answer is
Let $$$u(x,y)=\sum_{i}f(x,i,y)a_{i+1}$$$, $$$v(x,y)=\sum_{z}g(x,i,y)b_{i+1}$$$ (both of these are calculated in $$$O(n^3)$$$), then the answer is
By seeing $$$u$$$ and $$$v$$$ as 2D polynomials, this can be calculated with 2D FFT in $$$O(n^2\log n)$$$.
Of course! This problem can also be solved with modulo $$$10^9+7$$$ or on an algebraic structure where FFT is not easy, but interpolation can be successfully carried out.
We still need to consider $$$u(p-1,*)$$$ and $$$v(n-p,*)$$$ as polynomials $$$\sum_{i}u(p-1,i)x^i,\sum_{i}v(n-p,i)x^i$$$. Instead of doing FFT, consider substitute $$$x$$$ with $$$0,1,\dots,n+1$$$, and use interpolation to recover the final coefficients.
Suppose we have a value of $$$x$$$. Then, calculating $$$u(p-1)$$$ and $$$v(n-p)$$$ takes $$$O(n^2)$$$ in total. For fixed $$$x$$$ and $$$n$$$, the answer for $$$n$$$ is (here, note how $$$x$$$ is multiplied)
This also takes $$$O(n^2)$$$ in total. So, for each $$$x$$$, the calculation is $$$O(n^2)$$$.
For each $$$n$$$, the naive implementation of interpolation runs in $$$O(n^2)$$$. After we recover the coefficients, we multiply it with $$$c$$$ and update the answer.
So, the time complexity is $$$O(n^3)$$$.
#include <bits/stdc++.h>
using namespace std;
const int mod = 998244353;
int Power(int x, int y) {
int r = 1;
while (y) {
if (y & 1) r = 1ll * r * x % mod;
x = 1ll * x * x % mod, y >>= 1;
}
return r;
}
namespace Conv_998244353 {
const int g = 3, invg = ((mod + 1) % 3 == 0 ? (mod + 1) / 3 : (2 * mod + 1) / 3);
int wk[1050005], ta[1050005], tb[1050005];
void DFT(int *a, int n) {
for (int i = n >> 1; i; i >>= 1) {
int w = Power(g, (mod - 1) / (i << 1));
wk[0] = 1;
for (int j = 1; j < i; j++) wk[j] = 1ll * wk[j - 1] * w % mod;
for (int j = 0; j < n; j += (i << 1)) {
for (int k = 0; k < i; k++) {
int x = a[j + k], y = a[i + j + k], z = x;
x += y, (x >= mod && (x -= mod)), a[j + k] = x;
z -= y, (z < 0 && (z += mod)), a[i + j + k] = 1ll * z * wk[k] % mod;
}
}
}
}
void IDFT(int *a, int n) {
for (int i = 1; i < n; i <<= 1) {
int w = Power(invg, (mod - 1) / (i << 1));
wk[0] = 1;
for (int j = 1; j < i; j++) wk[j] = 1ll * wk[j - 1] * w % mod;
for (int j = 0; j < n; j += (i << 1)) {
for (int k = 0; k < i; k++) {
int x = a[j + k], y = 1ll * a[i + j + k] * wk[k] % mod, z = x;
x += y, (x >= mod && (x -= mod)), a[j + k] = x;
z -= y, (z < 0 && (z += mod)), a[i + j + k] = z;
}
}
}
for (int i = 0, inv = Power(n, mod - 2); i < n; i++) a[i] = 1ll * a[i] * inv % mod;
}
vector<int> conv(vector<int> A, vector<int> B) {
for (auto &i : A) i %= mod;
for (auto &i : B) i %= mod;
int sa = A.size(), sb = B.size();
vector<int> ret(sa + sb - 1);
int len = 1;
while (len < ret.size()) len <<= 1;
for (int i = 0; i < len; i++) ta[i] = tb[i] = 0;
for (int i = 0; i < sa; i++) ta[i] = A[i];
for (int i = 0; i < sb; i++) tb[i] = B[i];
DFT(ta, len), DFT(tb, len);
for (int i = 0; i < len; i++) ta[i] = 1ll * ta[i] * tb[i] % mod;
IDFT(ta, len);
for (int i = 0; i < ret.size(); i++) ret[i] = ta[i];
return ret;
}
} // namespace Conv_998244353
vector<int> conv(vector<int> A, vector<int> B) {
return Conv_998244353::conv(A, B);
}
int n, a[705], b[705], c[705], f[705][705], u[705][705], v[705][705];
int ny[705], jc[705];
void upd(int &x, int y) { x += y, (x >= mod && (x -= mod)); }
int main() {
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
for (int i = 1; i <= n; i++) cin >> b[i];
for (int i = 0; i < n; i++) cin >> c[i];
f[0][0] = jc[0] = ny[0] = 1;
for (int i = 1; i <= n; i++) {
jc[i] = 1ll * jc[i - 1] * i % mod, ny[i] = Power(jc[i], mod - 2);
}
vector<int> A(500000), B(500000);
for (int i = 0; i <= n; i++) {
for (int j = i; j >= 0; j--) {
for (int k = i; k >= 0; k--) {
if (!f[j][k]) continue;
// cout << i << ' ' << j << ' ' << k << ' ' << f[j][k] << '\n';
upd(u[i][k], 1ll * f[j][k] * a[j + 1] % mod);
upd(v[i][k], 1ll * f[j][k] * b[j + 1] % mod);
upd(f[j + 1][k + (i != 0)], f[j][k]);
upd(f[j][k + 1], 1ll * f[j][k] * (i - (i != 0) - k) % mod);
f[j][k] = 1ll * f[j][k] * (k + (i != 0)) % mod;
}
}
if (i > 0) reverse(v[i], v[i] + i);
for (int j = 0; j <= i; j++) {
if (i) A[703 * i + j] = 1ll * u[i][j] * ny[i] % mod;
B[703 * i + j] = 1ll * v[i][j] * ny[i] % mod;
}
}
A = conv(A, B);
for (int i = 1; i <= n; i++) {
int ans = 0;
for (int y = 0; y <= i - 1; y++) {
ans = (ans + 1ll * u[0][0] * v[i - 1][y] % mod * c[y]) % mod;
}
for (int j = 0; j < i; j++) {
ans = (ans + 1ll * A[703 * (i - 1) + j] * jc[i - 1] % mod * c[j + 1]) % mod;
}
cout << ans << ' ';
}
}
#include <bits/stdc++.h>
using namespace std;
const int mod = 998244353, N = 705;
int n, a[N + 5], b[N + 5], c[N + 5], f[N + 5][N + 5], u[N + 5][N + 5], v[N + 5][N + 5],
C[N + 5][N + 5];
int g[N + 5], h[N + 5], t[N + 5][N + 5], p[N + 5][N + 5], ny[N + 5], o[N + 5];
void upd(int &x, int y) { x += y, (x >= mod && (x -= mod)); }
int main() {
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
for (int i = 1; i <= n; i++) cin >> b[i];
for (int i = 0; i < n; i++) cin >> c[i];
f[0][0] = ny[1] = ny[0] = 1;
for (int i = 0; i <= n; i++) {
C[i][0] = 1;
for (int j = 1; j <= i; j++) C[i][j] = (C[i — 1][j] + C[i — 1][j — 1]) % mod;
}
for (int i = 2; i <= n; i++) ny[i] = 1ll * ny[mod % i] * (mod — mod / i) % mod;
for (int i = 2; i <= n; i++) ny[i] = 1ll * ny[i — 1] * ny[i] % mod;
for (int i = 0; i < n; i++) {
for (int j = i; j >= 0; j--) {
for (int k = i; k >= 0; k--) {
if (!f[j][k]) continue;
// cout << i << ' ' << j << ' ' << k << ' ' << f[j][k] << '\n';
upd(u[i][k], 1ll * f[j][k] * a[j + 1] % mod);
upd(v[i][k], 1ll * f[j][k] * b[j + 1] % mod);
upd(f[j + 1][k + (i != 0)], f[j][k]);
upd(f[j][k + 1], 1ll * f[j][k] * (i — (i != 0) — k) % mod);
f[j][k] = 1ll * f[j][k] * (k + (i != 0)) % mod;
}
}
if (i > 0) reverse(v[i], v[i] + i);
}
for (int x = 1; x <= n; x++) {
for (int i = 0; i < n; i++) {
g[i] = h[i] = 0;
for (int j = i; j >= 0; j--) {
g[i] = (1ll * g[i] * x + u[i][j]) % mod;
h[i] = (1ll * h[i] * x + v[i][j]) % mod;
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= i; j++) {
upd(t[i][x], 1ll * g[j — 1] * h[i — j] % mod * C[i — 1][j — 1] % mod *
(j > 1 ? x : 1) % mod);
}
}
}
p[0][0] = 1;
for (int i = 1; i <= n; i++) {
for (int j = 0; j < i; j++) p[i][j] = p[0][j], o[j] = 0;
for (int j = 0; j <= i; j++) {
if (j != i) {
for (int k = i — 1; k >= 0; k--) {
upd(p[j][k + 1], p[j][k]);
p[j][k] = 1ll * p[j][k] * (mod — i) % mod;
}
}
if (!j) continue;
int s = 1ll * t[i][j] * ny[j — 1] % mod * ny[i — j] % mod;
if ((i — j) & 1) s = mod — s;
for (int k = 0; k < i; k++) {
upd(o[k], 1ll * s * p[j][k] % mod);
}
}
int ans = 0;
for (int k = 0; k < i; k++) {
ans = (ans + 1ll * o[k] * c[k]) % mod;
}
cout << ans << ' ';
}
}
