Thanks for participation!
Update: added alternative solutions/proofs for A,B,D,F
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.
A simpler proof in the comments: consider the number of elements in the set. It increases by at most $$$k-1$$$ each time, and our construction reaches 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).
Observe that the number of 1 never increases in an operation. We can change a continuous segment of zeros into one zero. After that, it suffices to check that the number of occurences of 1 is larger than the number of occurences of 0.
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$$$ and $$$f(k)$$$ is the maximum sequence length. 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)
Note that $$$b_x\le \deg x$$$. By carefully handing the dp transitions, we can achieve a $$$O(\sum \deg_x)=O(n)$$$ solution.
#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)$$$.
We are trying to iterate over $$$i,x,j,y$$$ and do $$$ans_{i+j}\leftarrow f(i,x)g(j,y)h_{x+y}$$$. We can achieve this with two steps: first, iterate over $$$i,x,y$$$ and do $$$v_{i,x}\leftarrow f(i,x)h_{x+y}$$$. Then, iterate over $$$i,j,x$$$ and do $$$ans_{i+j}\leftarrow g(j,y)v_{i,x}$$$.
This runs in $$$O(n^3)$$$, and does not need to calculate inverses, and thus can be carried out on any ring.
#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 << ' ';
}
}
thanks for super fast editorial
Super Fast!!
there is also an O(n) solution for D.
we call the number of turn that a monster gets killed its colour.
we know that someone's colour is at most its degree +1.
if just maintain the two minimum colouring's and its colours for a subtree we can update our answer as follow:
we can fix the root colour from 1 to degre+1 and in each colourthe colouring for its children is the minimum colouring except the ones that its colour are same as the root. so their colouring is the second minimum one.
so we can solve it with a dp in O(n) time.
my code: 270694011
can u tell how?
I tried to explain in my comment. if I it wasn't clear for you, you can read granadierfc comment here with another explanation.
Nice :))
I read that trees are 2 colorable, so I'm thinking if only 2 colors would be sufficient?
No
2 Colors are not sufficient
he tried to say that the maximum value of a color for a certain node would at max be it's degree + 1
So if we declare a dp [ x ] [ t ]
where x is the node and t is the time in which I kill the x the monster
Then maximum number of second state that I would require for a certain node is it's degree + 1
and sum of degree of all nodes is equal to 2 * N
so we can say that overall there will 2 * N dp states.
Could you please point me out what is the mistake in the following logic:
The problem states that "you cannot kill two monsters that are directly connected by an edge"
So if I run a DFS and calculate depths of each node, then all nodes at an even depth are not connected by an edge, so I can kill all of them at once. Similarly, I can kill all monsters at an odd depth.
two color wont work. Try:-
TY!
I am stuck on the thought that b≤3 always holds. Suppose a1,a2,a3,a4,a5 are the nodes connected in a line. In the first round, either {a1, a3, a5}, {a1, a4}, {a2, a4}, or {a2, a5} can be chosen. For the second round, there will be at most 2 nodes in a continuous segment that can be eliminated in the next 2 rounds.
Can you please give a counter-condition?
8
1 1 100 100 10000 10000 10000 10000
1 2
1 3
2 4
1 5
2 6
3 7
4 8
Got it. Thankyou!
Checkout this comment — https://mirror.codeforces.com/blog/entry/131567?#comment-1171033
Consider a full binary tree and you have to eliminate boss bottom-to-up in such cases
What is the dp state for O(N)?
Thanks for your nice solution!
omg fast editorial :-)
I felt A >>> B in terms of difficulty
constraints are very low u can do simple recursion with base cases
the whole process can be simulated it would be complexity of 1e6 but map is needed so we keep frequency but t is 1000 so it will not pass
Possible proof for A: Think of number n as n '1's in a chain, connected with n-1 bonds. Each step could break a maximum of k-1 bonds. Hence the answer.
Wow, this proof is really smart. Thanks for sharing!
Thanks for the interesting (and challenging) problems!
I think this similar to what is in editorial (just in a opposite way)
can you explain the editorial one ?
Really nice observation.
I feel like an idiot after seeing your solution. I was doing it really hard way, which got WA.
Here it is,
Before attempting E: Range Minimum Sum, try these standard and easy version of the problem.
Standard
Easy Variations
Difficult Variations
In the past, I have also created a video on this topic.
Here is an interesting problem that has sum of all subarray maximums as a subproblem. CC LIMITMEX
Alternate for D : Note that a monster $$$v$$$ will die within $$$\leq deg[v]+1$$$ rounds. The problem could be formulated as follows , assign $$$t[v]$$$ (round number in which the monster gets killed) to each vertex $$$v$$$. Then you have to minimize the sum of $$$a[v].t[v]$$$ . For each vertex $$$v$$$ , we can keep a $$$deg[v] + 1$$$ sized vector , where each corresponds to the round number at which it was killed. Now using dfs and suffix / prefix minima , we can evaluate this value is $$$O(N).$$$
Can you elaborate on what
deg
is and how to arrive at this conclusion?Isolate a vertex $$$v$$$ , and look at all it's neighbours (the ones connected by edge to it) . deg or degree means the number of neighbours of a vertex $$$v$$$. At each round , either $$$v$$$ or atleast one of it's neighbours are chosen. If say none of them are chosen then you can simply choose vertex $$$v$$$ and have better answer.
deg
in this context means the degree of a given nodev
, which is the number of adjacent vertices tov
. You can think of this as such: if there are no adjacent nodes ofv
which are being removed on a certain round, then there is no reason not to removev
on that round as it is just a free removal. Therefore to delay the removal ofv
as late as possible, there would be 1 adjacent node ofv
being removed on each round, untilv
is finally alone. Once you realize this, the rest can be followed as explained by the original comment.Could we kill all the monsters in just two rounds? Using bipartite algo, dividing nodes in two sets, then killing all monster of one set in round1 and killing all other monster in round2
That's what i tried, not sure why it was wrong 270739384
Try this case:
4
100 1 2 200
1 2
2 3
3 4
Thanks, that clears it
1 1 1 100 100 100 100 100 100
1 2
2 3
1 7
1 8
1 9
3 4
3 5
3 6
I tried that but it is wrong because you could have two monsters with large attacks in different sets, but the optimal strategy is to eliminate both of them even though it may take extra turns.
Can you elaborate this approach further? How will you find the round number for each vertex such that $$$a[v].t[v]$$$ is minimised?
Can somebody explain what is being done in D. Or at least direct me to relevant resources.
yea the editorial seems to skimp on the details. whats the DP recurrence here?
Let $$$m$$$ be the maximum value of $$$b$$$ for all nodes (as in the editorial). We first root the tree at any node. Then, we perform a DP where $$$dp[i][b_i]$$$ ($$$1\leq b_i \leq m$$$) is equal to the answer to the problem for the subtree rooted at $$$i$$$. If $$$C_i$$$ is the set of children of node $$$i$$$, then the DP transition is
.
Thanks. This is the O(nlog^2n) solution right? Also why is it max, not min, since we want to minimize the damage?
dp[i][bi]=a[i]⋅bi+ min of dp[j][bj] ***
min not max
.
can someone point out my mistake in c i did the same thing as editorial submission of c
n can reach 1e18,32 is not enough.
F this is the second time i fell for it :(
iterate i from 1 to 63, and do (1ll<<i) instead of (1<<i) as you are dealing with long long
yeah tx im noob
The constraints on n is 1 <= n <= 10^18 so in loop you had to use i < 64 but you used i < 32 bits which resulted in wa
These Python codes are really cute.
ty for fast editorial)
Whats the counterexample for solving D by making the tree into a bipartite graph, then removing the side of the graph with the greater attack amount?
Indeed. I attempted that method but got WA.
you can consider the line graph 1-2-3-4, with attack values 100, 1, 1, 100.
ah fuck
Why wouldn't that method work? Isn't it optimal to first get attacked by all monsters (hence a loss of $$$202$$$ health points) and then attack two non-adjacent monsters, to then be attacked by the two remaining ones before they, too, get killed? With a minimum decrement of $$$303$$$ ($$$100+1+1+100+(100+1)$$$)?
In other words, the following: - First round, all monsters attack. $$$202$$$ health points are lost. Two non-adjacent monsters of $$$101$$$ and $$$1$$$ attack points get killed. - Second round, all remaining monsters attack. $$$101$$$ health points are lost. The rest gets killed.
I believe I am missing something obvious here, but I don't see it.
You can choose to kill 1st and last in the first turn. So total damage -> 202 + 2 + 1
In the first round you can kill the monsters with 100 attack power. so now you have 0--1--1--0 then take two more rounds to kill the other two. In this case the total damage will be 202+2+1
4
100 1 1 100
1 2
2 3
3 4
Today first time i have solved 3rd problem
best contest, but in my opinion E is easier than D
I so almost solved D. Nice problems. Thanks for super fast editorial.
How ? Both of us had similar approach for D but its wrong . I think our approach is completely wrong . How is it almost solved ? can you give the bfs solution for D.
No I am not talking about the one I submitted. I thought about dp on levels... But I think it needs further optimisation.
And I think dp on levels will also not work. I thought why just now :(
Can someone give me an example for problem D where $$$b_i$$$ is greater than $$$3$$$ for any node?
I'd like to see an example too. Here is my perhaps wrong proof:
In the first round, you can reduce the whole tree to pairs of two or lone nodes. Because, imagine a line of 3 nodes: just remove the node in the middle and it becomes two lone nodes.
Then, in the second round, remove all the lone nodes and 1 node from each pair of 2.
Then, in the third round, remove all the lone nodes.
ah, thanks for this
Thank you so much!
Is it true that the total rounds in D is $$$ \le 3$$$?
Why I can not solve a with brute force?
I have a different solution for B. Compress adjacent 0s into just one 0 (ex. 0010001 -> 0101). Note that replacing every substring with majority 0 is of the form 0 + 10 * k such that k is an integer, so removing these strings doesn't change the number of 0s and 1s. Thus, just check if there are more 1s in this compressed string than 0s. Here is my submission link. I'm surprised that the intended solution is casework.
The same solution.
same here
i also had the same solution and it felt much easier
A case for Bonus: Find a counterexample for $$$b_i≤18$$$ when $$$n=300000$$$.
Explanation: we delete all leaf nodes at a time. Then the tree becomes the largest subtree of the previous tree.
This structure is also known as binomial heap.
If you've learnt Binomial Heap, you'll find this construction is easy to access, for we're emphasizing the constraint on each node: each node with out-degree $$$i$$$ is directly connected to nodes with out-degree equal to $$$0,1,\dots,i-1$$$ exactly one each. And under this condition, we found a deletion with all nodes total degree $$$i$$$ on $$$i$$$-th round exactly fulfills the constraints of MEX.
Problem B :(Make Majority) Video Editorial YOUTUBE VIDEO LINK (Make Majority) --Click Here
Another solution to B
First, all continuous $$$0$$$ can be transformed into one $$$0$$$ using one operation. Then we can consider the simpler form.
It's obvious that the pattern like $$$101$$$ can be reduced into $$$1$$$, so all $$$0$$$ except the first and the last character. so we can just compare the number of $$$1$$$'s and the number of longest continous $$$0$$$ segment.
what's the expected rating of D?
There's an $$$O(n\log n)$$$ solution to E without using the cartesian tree by calculating the contribution of each $$$a_i$$$
https://mirror.codeforces.com/contest/1988/submission/270728340
i also have some $$$O(n \log n)$$$ solutions with a fenwick tree and a segment tree, but it unfortunately got TLE :/
I found for each element two left and two right minimums with set of indices. Adding contributions to answers are just with prefix sums
C Video Editorial
https://www.youtube.com/watch?v=-asiN-_tqb0
English
There is another solution for problem E. The point is to look at the contribution of each element in the permutation to the answers.
For each element we calculate the first and second element smalller than them to the left and to the right. This can be done in $$$O(n\cdot logn)$$$ using binary search and sparse table.
Then for each element we want to analyse the contribution of subarrays for which the current element is the minimum. We look at the segment of elements until the first smaller one to the right, let's say it has size $$$A$$$ (not including the element itself) and let's call the right one $$$B$$$. To everyone that is in the left segment, the number of subarrays for which the current element is the minimum is $$$A \cdot (B + 1)$$$ and for everyone in the right segment its $$$(A + 1) \cdot B$$$. For the first eleement smaller than the current element to the left, the number of subarrays is $$$(B + 1)\cdot ($$$ size of segment to the left including all elements up until the second element smaller than him $$$)$$$ . Same logic can be used to calcuate contribution of current element to the first ellement smaller to the right. For everyone else, that is everyone left of the first smaller element to the left and everyone right of the first smaller element to the right, the contribution is $$$(A + 1) \cdot (B + 1)$$$. Some edge-cases need to be handled for when there is no element smaller to the left or to the right however this is the gist. The contribution can be added up with lazy segment tree or even with prefix sums.
For details of implementation you can look at my code. code
You can do everything without any data structures btw 270718477
Very cool!
This is the method I used; however, you can use stacks instead of binary search and RMQ and use prefix sums instead of segtree to achieve O(N). 270713592
blazingly fast editorial
In editorial of pD, "taking max part" should be "taking min part"
Did poor in this round, but really nice problems! The other side of getting bad result is finding unseen shortages for improvement :)
nvm
Where the number on vertex means the round it is removed (If you want to think as minimizing damage, replace 1 to 1e9, 2 to 1e7, etc.)
I think for A, a simple proof (or rather intuition) can be : Let's say you do not divide the element into (k-1) 1's and (n-k+1), and lets say you divide it into some number (possibly zero) number of 1's and a bunch of other numbers. Let the minimum number be p, then, to make p into 1 again (which is our goal), you'll need another operation in the future to convert it. Thus, you are needing more than 1 operation to convert a number into 1. Greedily, we should ideally use only 1 operation to convert a number (or part of it) into 1's. Thus, the ideal strategy becomes to convert the numbers into (k-1) 1's and (n-k+1)
The suggested method for B feels unnecessarily complex and invites mistakes by having multiple cases. Instead, another approach is to collapse each continous sequences of 0 into a singular 0, then compare if there's more 1s than 0s.
My (python) code: https://mirror.codeforces.com/contest/1988/submission/270651964
B was a really easy question
For B I thought of splitting string into "101"/ "110" / "011". What is wrong with this solution? 270743982
In D, I used recursive DP[n][20] but still TLE in test case 20. Can somebody explain why?
Solution: https://mirror.codeforces.com/contest/1988/submission/270724498
Check second last line in your DFS function .You are Not storing answer in dp array ,instead you are simply returning.
It is only for the root node i.e when parent==-1. for other nodes I am using dp.
try submitting on cpp20
Another proof for # turns for pD: notice vertices not chosen in a round should connect to at least one chosen vertex, otherwise we can also choose it, then consider CC form by non-chosen vertices, every vertex in same CC would have different adjacent chosen vertices, then if there exist a (non-chosen)CC with size > n / 2, there also have > n / 2 chosen vertices, which means total nodes > n, which leads to a contradiction, so max size of CC form by non-chosen node would halve.
Then to construct the case where $$$O(\lg n)$$$ turns is needed, we can use the idea of above proof:
start with single node with weight $$$2^1$$$, call such tree $$$T_1$$$, then define $$$T_i$$$ ($$$i > 1$$$) as the tree by first use a node with weight $$$2^i$$$ to connect two $$$T_{i - 1}$$$, then for each node haven't connect to a node with weight $$$2^i$$$, create a node with weight $$$2^i$$$ and connect to it, then $$$T_i$$$ would have about $$$2^i$$$ nodes and require $$$i$$$ turns to eliminate.
thanks for this explanation
Hi, how to compute $$$f(n,i,j)$$$ in $$$O(n^3)$$$ in F editorial? I was only able to come up with $$$O(n^4)$$$ or $$$O(n^3 log(n) )$$$ solutions for this subproblem.
.
Disclaimer: I haven't implemented it myself yet, but that seems to be the logic behind jiangly's solution (270732930)
Let's build permutations of length $$$n + 1$$$ by inserting a $$$1$$$ into a permutation of length $$$n$$$ of numbers $$$2, 3, \dots, n + 1$$$, so we have $$$n + 1$$$ positions to insert to. These positions can have one of the $$$4$$$ types:
First position. In this case both the number of ascents and the number of prefix maximums increases by one.
Ascent positions, i.e. we insert a $$$1$$$ between elements $$$p_i$$$ and $$$p_{i+1}$$$, such that $$$p_i < p_{i+1}$$$. In this case both the number of ascents and the number of prefix maximums do not change.
Nonascent positions, i.e. we insert a $$$1$$$ between $$$p_i$$$ and $$$p_{i+1}$$$, but $$$p_i > p_{i+1}$$$. In this case the number of ascents increases by one, but the number of prefix maximums stays the same.
Last position. Nothing changes.
Now we can count the number of positions of each of those types to get the transitions from $$$f(n, i, j)$$$:
Thanks :)
In problem D, Why does the maximum B of a node is deg(x) + 1? I cannot find any comment to prove it.
Because $$$b_u = \operatorname{MEX}_{(u,v)\in E}(b_v) \le deg(u)+1$$$
First, thank for very good contest and fast editorial I am going to share my O(n) solution for D We can notice that in optimal solution, monster in node v can be kill in at mode |v| round (|v| is number of node have the same edge with D, round number from 0) So we can call dp[v][round]: minimum number of health decreases when kill monster in node v after "round" dp[v][round]= ∑_(u ∈chill of v) (min)(dp[u][j]) (j ≠round) (sorry, i don't know how to write beautiful fomular)
we can use pref_min and suf_min to quickly calculate Node that we must update parent value from chill due to tle Here is my code 270747003
I see newbies solving C damn newbies these days are different breed,back when I was a newbie I couldn't even upsolve C by looking at editorial.But how does their submission looks alike?
can anybody write a more intuitive proof for problem D's max of logn sets ?
This might help
where you guys show the range of the output from 1 to n ? not 0 to n? (Problem C)
Or am i missing something?
Positive integers
positive integers
Hi, I am finding it difficult to understand the solution provided to D. Can someone post a simple solution with an explanation or suggest updates in the existing editorial please?
For B I believe we can also "compress" any amount of '0' in a row into a single '0', then simply check if the number of '1's is greater than '0's in the resulting string: 270654643
For A, if we do in the reverse way, I think this is a problem like exchanging a new bottle by K bottle caps.
Like given [1, 1, 1, 1, 1, 1, ..., 1] containing n
1
s, and we are going to combine at most K items once, and finally derive [n]. The process will be like [1, 1, 1, ..., 1] -> [1, 1, 1, 1, ..., K], containing N-K1
s and 1K
. Our target is to combine all numbers into 1 number, so the real number in the array doesn't matter at all, that it, there remains N-K+1 items to combine.The maximum number of bottles that can be exchanged is
floor((N-1)/(K-1))
.I think this is a classis problem, so you may find video explanations online. I elaborate one here: First give 1 bottle cap to your friend, and every time you exchange
K-1
bottle caps with your friend's one, and give the exchanged bottle (cap) back to your friend. You can do this(N-1)/(K-1)
times and you will finally exchangefloor((N-1)/(K-1))
bottle caps and have remaining(N-1) % (K-1)
bottle caps +1
from your friend.The difference between A and bottle exchange problem is that if
(N-1) % (K-1) + 1 > 1
, then you should do the final combine, so the answer is `ceil((N-1)/(K-1)) in this problem.Problem D got accepted in exacly 3 sec
[submission:https://mirror.codeforces.com/contest/1988/problem/D]
Pretty surprise to see cartesian tree in $$$E$$$. Maybe it is the first time I see it in CF as well.
A felt hard. Came up with DP approach for A during the contest . Normal method was just not striking me.
Woah, I also did DP (bottom up) for problem A but mine is much easier:
270647399
Hello! Does my solution of D get RE because of dfs? 270748754
If yes, is there are way to bypass it nicely?
Shouldn't the edi also contain the dp states and transitions atleast instead of just mentioning that you can solve it by dp? (for D)
Another idea for B is that it is only possible iff the number of "0-streaks" is less than the number of ones.
Please someone explain the bi<=19 part of the editorial in more detail.
In fact, problem D has a $$$O(n)$$$ way
Considering that we actually only transfer from the smallest and subsmallest points of each subtree when we transfer, in fact, there are only $$$O(deg)$$$ effective transfer points of a tree point, that is, only the number of selection rounds corresponding to the minimum value of each point, and their mex and mex+1, taking into account this, we only need to maintain the smallest and subsmallest points of each point to implement the $$$O(n)$$$ algorithm.
It comes with an implementation that uses map, which is just for convenience and can be replaced with another $$$O(1)$$$ structure
https://mirror.codeforces.com/contest/1988/submission/270751383
Could someone provide an explanation of the DP used for Problem D?
Thanks!
If monster u is killed at time x , all its adjacent monsters v will be killed in range [1 , x — 1] U [x + 1 , upper bound ] . So dp[i][j] denotes the minimum cost to kill all monsters in subtree rooted at i , where ith monster is killed at at jth second .
upper bound is log(n)
Understood, Thank you !
Why does this code in java 270744757 tle but gives ac in c++ 270751728 :( Edit: I see that the c++ code also barely passes maybe i can do better with the transitions
In fact, problem D has a $$$O(n)$$$ way
Considering that we actually only transfer from the smallest and subsmallest points of each subtree when we transfer, in fact, there are only $$$O(deg)$$$ effective transfer points of a tree point, that is, only the number of selection rounds corresponding to the minimum value of each point, and their mex and mex+1, taking into account this, we only need to maintain the smallest and subsmallest points of each point to implement the $$$O(n)$$$ algorithm.
It comes with an implementation that uses map, which is just for convenience and can be replaced with another $$$O(1)$$$ structure
https://mirror.codeforces.com/contest/1988/submission/270751383
I enjoyed today's problems. Thanks to the setters.
nice
This codechef problem is harder version of B.
I believe my solution for problem E is also
O(n)
, but doesn't require Cartesian tree. It is quite unpleasant to implement and debug though, I couldn't do so during the contest time.thanks for editorial <3
What's wrong with this idea for D?
There are at most $$$O(\log n)$$$ rounds, so for round $$$j$$$, find the maximum weighted independent set, let it be $$$c_j$$$, then set the values of $$$a_{v_i}$$$ to 0 for each $$$v_i$$$ in the max ind set, and keep doing that until we get all zeroes in
a
. For round $$$j$$$, add $$$j \cdot c_j$$$ to the answer.After all rounds, output answer. This fails on test 3 :|
4
5 4 4 5
1 2
2 3
3 4
The optimal solution is 18 + 9 = 27. From what I understood, your idea will output 18 + 8 + 4 = 30.
Thank you!
How does the induction go in the proof of B?
Problem E can be done by looking at the contribution of each values. If an index is removed then the affected contribution will the - - The contribution from the index itself. This we can find by calculating the left and right index smaller than the value at index. - The contribution coming from the other index that uses this index in their contribution. Here the observation this value will only change if we change the value between the left and right minimum of this index. If we remove left and right, then we have to consider second minimum left and second minimum right respectively and add it accordingly. All the value that is between left and right will only reduce the contribution by 1.
For problem D, am I the only one who decided to use
sqrt(n)
instead oflog2(n)
as the bound forb
(for safety because I couldn't prove it in contest), only to find out that there's exactly one singular case wheresqrt(n) < log2(n)
? QAQThis is my approach for problem A, can you tell me what is the flaw in the argument? the picture link is the following, i don't know why it is not uploading: https://photos.app.goo.gl/VLXqFcDU2QHGFHap7
I came up with DP on subtrees solution for D right after the contest but it got WA on 3rd test. It maintains
dp[2][i]
, the maximum sum of monster points on subtreei
we can get in the current round if we skip/kill the root node of that subtree. Can somebody help me understand why that failed?270745002
oh, thanks!
not come up with '0110110' and got an WA on B :(
$$$O(n)$$$ solution in problem E without cartesian tree (although it's long to explain what I'm actually doing): 270758048.
Edit: I miswrote the prev_greater and next_greater, it must be prev_smaller and next_smaller
That was clever to push all the popped elements from 1st stack to 2nd stack.
I found first and second left/right minimum index using Fenwick tree 270751749
I'm not really the one who comes up with the two stacks approach. Last week, I solved a problem in Leetcode , which required to find the second greater element. Firstly I used segment tree for it, but then I know that 2 stacks O(n) approach from a guy.
I did something similar I think, but i did the prev_greater thing with rmq, so it's $$$O(n log n)$$$. Nice code btw
Can someone explain why I have to cast here?
I made a function that converts a binary string to decimal but it breaks at higher numbers. Specifically this statement:
However when casting to long this statement works as intended.
Here is the working submission: 270754810
I don't get this line in A proof
I solved E in $$$O(n log(n))$$$
For each $$$a_i$$$ we find what would be the contribution of $$$a_i$$$ to the result.
Let $$$l_i$$$ be the first smallest element when traversed from index $$$i$$$ to left; $$$a_j > a_i$$$ for all $$$l_i < j < i$$$
Similarly, Let $$$r_i$$$ be the first smallest element when traversed from index $$$i$$$ to right; $$$a_j > a_i$$$ for all $$$i < j < r_i$$$
Contribution of $$$a_i$$$ to the result would be $$$a_i * (i - l_i) * (r_i - i)$$$
Result = $$$\sum_{i=1}^{n}{a_i * (i - l_i) * (r_i - i)}$$$
Tutorial for Next greater element using the same trick you can extend it for finding next smallest element and previous smallest element
How many first left and right minimums do we need to maintain?
How do you efficiently find first 2 left/right minimums?
Let $$$l1_i$$$ be the first smallest element when traversed from index $$$i$$$ to left; $$$a_j > a_i$$$ for all $$$l1_i < j < i$$$
Let $$$l2_i$$$ be the second smallest element when traversed from index $$$i$$$ to left; $$$a_j > a_i$$$ for all $$$l2_i < j < l1_i$$$ and $$$l1_i < j < i$$$
Let $$$r1_i$$$ be the first smallest element when traversed from index $$$i$$$ to right; $$$a_j > a_i$$$ for all $$$i < j < r1_i$$$
Let $$$r2_i$$$ be the second smallest element when traversed from index $$$i$$$ to right; $$$a_j > a_i$$$ for all $$$r1_i < j < r2_i$$$ and $$$i < j < r1_i$$$
Lets find what would be contribution of $$$a_i$$$. We have a total of 5 cases.
From above cases we have a range and a value that needs to be added, this is reduced to range update point query. This can be done in $$$O(n)$$$
There are many ways to solve this but I used Fenwick tree. The idea is to update each node in the Fenwick Tree with the first and second maximum indices for the elements in the array.
My Solution
I am unable to understand the reason for getting the following error in my code for Problem C 1988C][SUBMISSION:270720573 - Increasing Sequence with Fixed OR
wrong answer Integer parameter [name=a[35]] equals to 1000000000000000000, violates the range [1, 999999999999999999] (test case 102)
The question specifies 1<= n <= 10^18, and that a(i) <= n
Here is my code:- ~~~~~
include <bits/stdc++.h>
using namespace std;
int main() { int t; cin >> t; while(t--) { long long n, n2; cin >> n; n2 = n;
} ~~~~~
The logic used here simply keep track of the places where the binary digit is 1 starting from position 0 at the right hand side (least significant bit).
Then I simply place 0 one by one in the in the positions where one are placed. For example: n = 1111, then
1111 1110 1101 1011 0111
Just shifting the 0 from right to left across all the positions that have 1, and keeping the position with zeroes as same.
If I have a n = 11100111, then
11100111 11100110 (0 placed at 0th pos from right) 11100101 (0 placed at 1st pos from right) 11100011 (2nd pos) 11000111 (5th pos) 10100111 (6th pos) 01100111 (7th pos)
I create the number with 0 in 6th pos by doing n — pow(2, 6) Which produces the same effect as placing 0 in the sixth position.
Please help me understand the flaw in my logic/code which is causing this unexpected error.
use brackets every where when writing any bitwise operator
like -> if((n2 & 1) == 1)
Missed B by just 1 more condition -_-
why was this failing but if only I changed
(n^(1<<i))
part to(((ll)n)^((ll)(pow(2,i))))
it workedbecause
(1 << i)
will overflow wheni >= 31
, use1ll << i
Thank you
Can someone please explain what is going wrong in this solution? I tried to subtract the power of bits which were 1 in n from n.270761320
Your code has
1<<v[i]
this will overflow, you should typecast it to long long. Ex:1ll<<v[i]
Thank you
Wow, super fast editorial! Thanks!!
Another approach for B:
Replace every clusters of 0's with a single 0 and leave 1's as it is, as we always want to increase the number of 1's in our string. Now, count the number of 1's and 0's in it. If 1's > 0's, then the answer is "yes" else "no".
in A how it , for n=772,k=295 step=3; by me in first step 772=295,295,185 then these three number can make 1 in 3 step so total step is 4
Finding it hard to understand Problem D Solution can someone point me to a different tutorial maybe video explanation ?
Interesting competition, I believe we needed like 30 min more for better distribution. Right now 7000 people competing solved first 3 proiblems and than only < 800 solved 4th. With bit more time I believe we would have like ~2000 people on 4th and that would give us a lot better distribution of scores.
I am looking for help in problem D, because I had an alternative approach (semi-greedy) and can't find any counterexample.
My algorithm goes as follows:
While vertice count > 0:
1. Find a Maximum Weighted Independent Set (MWIS) in the remaining forest.
2. Remove all vertives belonging to MWIS from the forest.
Maybe there is fundamental error in idea, maybe bug in implementation 270734719. Any help would be appreciated. Thanks.
4
5 4 4 5
1 2
2 3
3 4
Try this one. The answer is 18 + 9 = 27.
Thanks, now it looks very obvious.
Having "big steps" is good, unless number of steps isn't much.
For example you could finish everything in 2 steps, because tree is bipartite. Removing each part on each step. And it isn't obvious why you algo is better than that. That is the problem with your approach.
My logic for C :-
I was trying to Upsolve D. I read the edi and got the DP approach. I coded it up and was constantly getting TLEs. I optimized a lot (converted map<int, vector> to vector<vector> for the adjacency list, included all fastio, used as less space as possible etc).
I was still getting a TLE, so I had a look at my friend's solution who got an AC in the contest. It was literally the same thing. So I copy pasted it and that also got a TLE. What could be the reason for this ?
Submission from my account: 270772292
Submission from friend's account: 270738230
Both the codes are literally the same.
The language is a bit different + your friend's solution is not that fast in the first place so...
i copy pasted your code and got AC 270774740 lol
https://mirror.codeforces.com/contest/1988/submission/270773130
can anyone help what am i doing wrong above?
Another approach For b if we take all the sequences of 000 and combine them to form a single 0 then The resulting string would only have single 0 and other 1's so if we count no. Of 1's here and if they are greater then no. Of 0's then answer is YES else answer is NO.
Can't think of a proof but it passed all test cases
I did it too
I had the same solution. The proof is pretty simple. Notice that after combining all zeros together you have a sequence where each zero is surrounded by ones. Suppose oneCount > zeroCount, by combining two ones with a zero, you decrease the total amount of 1s and 0s by one. If you repeat this over and over a again, you will reach a point where there is one zero and more than one one. Conversely, it is clear that if the number of zeros is more than or equal to the number of ones, the answer is NO.
Edit: I just realized you can just choose the whole array :)
my clarification for log(n) in problem D, I hope this help someone: suppose in the worst case that you have set of monsters with attack point equal to MX (for example 1e12) and these all nodes connected with all vertices in the tree, then the optimal choice for current round is to select these nodes, then number of nodes now is at least n/2, in the second round suppose the same that you have set of monsters with attack point equal for example MX-1 then best choice to select these nodes, and number of nodes now equal (n/2)/2 ... and so on then after the first round you have n/2 node after the second round you have (n/2)/2 node after the third round you have ((n/2)/2)/2 node .... and so on. then in the worst case there is log(n) rounds.
then now easily you can use dp on tree from any node state: dp[u][r] which is you at node u and at round r transaction: move to each child with round equal any number from 1 to log(n) except current r and choose the minimum
that is my code it may help: https://mirror.codeforces.com/contest/1988/submission/270781650
Auto comment: topic has been updated by feecIe6418 (previous revision, new revision, compare).
Auto comment: topic has been updated by feecIe6418 (previous revision, new revision, compare).