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.
The optimal sequence of operations is very simple.
"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).
The optimal sequence of operations is very simple.
1988C - Increasing Sequence with Fixed OR
The answer is a simple construction.
The maximum length for $$$2^k-1\ (k>1)$$$ is $$$k+1$$$.
TODO
The optimal sequence of operations is very simple.
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 << ' '; } }
