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,y}\leftarrow f(i,x)h_{x+y}$$$. Then, iterate over $$$i,j,y$$$ and do $$$ans_{i+j}\leftarrow g(j,y)v_{i,y}$$$.
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.
I tried this initially. This approach is the fastest way to kill all the monsters, but it does not guarantee minimum damage taken. For instance, take the following tree as a counterexample:
The best first move would be to kill the root node and the lowest node. This would eventually take 3 total moves to kill all monsters, but it would result in less damage taken than going even rows and then odd rows (or vice versa).
two color wont work. Try:-
TY!
ohhhh... i was also stuck there, i thought of two coloring but then i thought if it is two coloring then this should be very easy. Btw Thank you now I understood why this have so less submission
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!
Deleted
hi
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
lol... this is basically a O(N) solution
same here
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 ?
Your text to link here...
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,
For D: The Omnipotent Monster Killer I created a video editorial
I also created a practice contest for you to submit and verify your cubic and quadratic solutions. https://mirror.codeforces.com/group/7Dn3ObOpau/contest/536755
For E: Range Minimum Sum also I created a video editorial and a practice contest which you can find here
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
yes vro it is same as array collapse
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
degis 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.
degin 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 ofvwhich are being removed on a certain round, then there is no reason not to removevon that round as it is just a free removal. Therefore to delay the removal ofvas late as possible, there would be 1 adjacent node ofvbeing removed on each round, untilvis 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 you please elaborate your solution?
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
.
Hi. I have tried to explain the logical steps thats needed to understand the editorial in this comment.
Could you please go through it and let me know if it looks correct.
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
can anyone explain for question c why ans is not 5 for 14 n =14 5 6 8 10 12 14
5|6 != 14
yes , I got same problem according to question ans should be :
just greedily flip the last set set bit that you didnt flip earlier and the next time you must flip a set bit greater then this bit otherwise the decreasing/increasing condition wont be satisfied
here why increasing decreasing condition is not satisfied?
8|10=10 not 14
To ensure or is 14 you must set the bit you unset last time
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!
Thanks for your gragh.It is really clear!
Can you please help me understand, why greedy fails?
1) My solution was, travel through entire tree.
2) Initially I will have all monsters alive. Doing greedy, I will get answer, which monsters MUST BE KILLED in this round, by finding maximum sum of independent set.
3) I will kill these monsters. In fact, we can say, we are removing these nodes from the tree, and splitting it into multiple trees ( forest ) .
4) I will continue this process, until I have killed all the monsters.
The test case that you have proposed InternetPerson10, works perfectly fine with my greedy approach. I just can't figure out, why greedy approach fails :(
Consider this test case:
I think your solution will print 160 (it takes 3 rounds), while there is a way to do 150 — choose a 3 and a 2 to kill in the first round.
Is it true that the total rounds in D is $$$ \le 3$$$?
I also thought so, but I guess, that's not true.
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
The solution of calculating the contribution can be optimized into $$$O(n)$$$ by using prefix sum and differce array.
https://mirror.codeforces.com/contest/1988/submission/270863077
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!
someone add this in tutorial. It is super cool solution.
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
can you tell how you find out the second smaller element than the current element using stacks ?
When a item is popped from the stack for the first time, place it back again and you can find that the monotoniciy of the stack still maintains.
Hence when the item is popped for the second time, that's where the second smaller element is.
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
still TLE on test case 20. Very strange all test cases are large but failing only at 20
Its working in 1.6 seconds after changing the order of w and childs. https://mirror.codeforces.com/contest/1988/submission/270893195
Can you explain why this is so? TC remains the same. Why it only fails at test case 20 while other passed testcases are large too?
i think maybe it is related to depth of tree , also you can optimize it to n*20 from n*20*20 by using prefix and suffixmax.
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
Very helpful. Thanks for the comment..
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$$$
Hi. I have tried to explain this in Part 2 of my comment.
Could you please give that a read and let me know if it looks alright.
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
Hi. This is my understanding of the editorial.
Please give this a read and let me know if I can rectify/improve anything.
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?
Hi. Have just posted this comment to explain my understanding of the editorial.
Let me know if you find anything wrong
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
1s, 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-K1s 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-1bottle 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 +1from 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.
Hi. I have tried to explain this in Part 2 of my comment.
Please give that a read and let me know if you find any issue in my explanation.
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
Can you please explain this approach in detail?
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)? QAQfor what n?
This 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 subtreeiwe 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
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.
Can you explain how you are using the Fenwick Tree to update the contribution?
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;
vector<long long> a; vector<int> pos; int size = 0; while(n2>0) { if(n2 & 1 == 1) pos.push_back(size); n2 = n2 >> 1; size++; } a.push_back(n); for(int i=0; i<pos.size(); i++) { long long x = n; x = n - pow(2, pos[i]); if(x!=0) a.push_back(x); } cout << a.size() << endl; for(int i=a.size()-1; i>=0; i--) cout << a[i] << " "; cout << endl; }} ~~~~~
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)Made the changes. Still getting the same error. Here is the updated code
bro it's test case 102 with $$$ n = 10^{18} - 1 $$$ and your code outputs:
Thank you so much for your help. I understand the issue now.
It is due to the precision of the floating point number returned by pow(2, pos[i])
Thanks a lot once again
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 << iThank 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 ?
Hi. Please give my comment a read.
Let me know if you see any issue in the logic.
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.
here is a better idea, try proving your solutions instead of asking for counter cases :)
I got the same idea as https://mirror.codeforces.com/blog/entry/131567?#comment-1171248. Can you please help me with proving whether the solution is right or wrong without sample cases? Maybe taking the Maximal Weighted Independent Set every iteration is wrong, and sometimes a sub-optimal set currently can lead to a more optimal solution 1 or 2 iterations afterward. I can say these in words, but never visualize or prove.
My logic for C :-
int right = 0; while(n!=0) { int rm = n & -n; n ^= rm; int x = n|right; if(x) v.push_back(x); right |= rm; }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).
The description of Jiangly's solution in problem F has somthing wrong, we can't do $$$ans_{i+j}\leftarrow g(j,y)v_{i,x}$$$ without iterating $$$y$$$, and I guess that the translation shoulb be $$$v_{i,y}\leftarrow f(i,x)h_{x+y}$$$ and $$$ans_{i+j}\leftarrow g(j,y)v_{i,y}$$$.
You're right, fixed
Auto comment: topic has been updated by feecIe6418 (previous revision, new revision, compare).
https://mirror.codeforces.com/contest/1988/submission/270807781 where am i doing wrong cananyone please help me
Here's a counter example for your code:
i got it thank you
guys in the proof of problem D, it is mentioned that:
f(u) ≥ 1 + ∑ [1≤i<u] f(i)
I don't understand this. it is assumed that u is the greatest possible colour in the whole tree. But the same condition might not hold for the direct children of the root. (for their respective subtrees). so why is the recursion formula true?
If I have understood your question correctly you are asking why the direct children can't have the number of days it takes them to be killed = u. Sorry if I have misinterpreted your question.
Answer: If $$$u$$$ is being defined as the maximum number of days it takes to kill a monster then a node with value $$$u$$$ has to have at least one neighbour ($$$v_j$$$) where the number of days it takes for a node $$$v_j$$$ to die is equal to $$$i$$$ for $$$1 \le i < u$$$. The reason for the range being $$$1 \le i < u$$$ is because if there was a neighbour $$$v_j$$$ with value equal to $$$i$$$ for $$$1 \le i \le u$$$ then node $$$x$$$ wouldn't be allowed to have the value of $$$u$$$, because it is adjacent to a node $$$v_j$$$ which already has value $$$u$$$, which means that $$$x$$$ would have to take the value of $$$u + 1$$$ which contradicts the claim which states that $$$u$$$ is the largest value.
Sorry again if I misunderstood your question.
Hi. I feel that there are certain logical steps in between before we finally plunge into the recurrence relation. I have tried my best to explain this in this comment.
Please give this a read and let me know if you see any problem in the explanation.
for the problem B, the second solution is intuitive
Can someone say in general where to use min(a,b) instead of fmin(a,b).
.
my
Hello, guys. Could you help me with my problem? I don't understand why my solution throws an error (memory overrun).
my code:270830415
270730886 This was my code for D problem. The time complexity is O(nlogn) in my opinion but it is giving TLE in test case 20. Can anyone identify the issue in my code?
So node having value i will be destroyed in round i.
And way I have assigned values to nodes in such a way that you can make a conclusion that you there is a way to destroy node in more than 3 or 4 rounds.
You will destroy node having assigned value i after node having j value where i>j .
for D
this comment
size trend => n or 2*a, a or 2*b, b or 2*c, c or 2*d ......
or 2^i ,2^i-1, 2^i-2 .... 2^0
here 'i' is the first round
2^i=n
i=log(n)
why there is no option for feedback below each question? Some questions realllllly sucked.
Hello , can anybody explain why bi does not exceed log2(n)+1 . I tried to understand the proof of the editorial but I am having difficulty visualizing it. Any help would be appreciated . Thank you
Hi. I also had a very hard time understanding the editorial. I feel I finally have a perspective that explains everything that's written in the editorial. Have tried to put them in this comment. Please refer Part 2.
Let me know if you see any issue in my explanation.
Edit : The following proof is wrong!
I have a different proof for maximum rounds in problem D.
Consider a tree $$$T$$$ with $$$n$$$ nodes. We need to show that it can be processed in at most $$$\log_2 n + 1$$$ rounds.
We can always remove at least one vertex. Let us assume it is the centroid of the tree. The tree then breaks into different components of at most $$$\frac{n}{2}$$$ size. We can apply operations on the each component simultaneously and independently.
If $$$f(n)$$$ is the number of rounds for a tree with $$$n$$$ nodes, then we can say: $$$ f(n) \leq f\left(\frac{n}{2}\right) + 1 $$$
By applying this recursively, we get: $$$ f(n) \leq \log_2 n + 1 $$$
Thus, the number of rounds is at most $$$\log_2 n + 1$$$.
Any feedback is appreciated!
Thanks for the explanation.
I don't think your proof is correct. You are just demonstrating one way to finish the rounds in $$$Log(N)$$$ steps, by choosing centroid at each stage. But how do you ensure that the damage inflicted by other monsters is minimized? What if the centroid inflicts zero damage while other vertices inflict a lot of damage?
In fact, using your same reasoning, I can show that $$$f(n) \leq 2$$$. In the first round, we remove all the odd levels, and in the second round we remove all even levels. Since I have a way to finish the game in 2 rounds, it doesn't mean that it's optimal.
Oh yes, you are right. I had a feeling that i was wrong and thus made a comment so someone could provide feedback. Thank You! Also I love the content you create, keep going :)
can someone please tell why Greedy don't work for Problem D? -> as in the given tree we can eliminate any number of monsters, with a condition that they should not be adjacent to each other. so in the first turn all monsters will attack and decrement health by total sum of attack power of all monsters but in this move we try to kill all those non-adjacent monsters whose attack sum is maximum and as tree do not contain any cycle therefore there is only two possible scenarios. i used BFS to calculate sum of attack power for both cases and return (total attack power + min of above two cases). -> can anyone please help me to figure out my logical error or what part i am missing, any reply would be appreciated. here's my code link :270855931
i tried same bro, but WA
Please elaborate on the problem A. share a video link if possible.
Could someone point out what's wrong in this construction for E?
My output for TC1:
Context — $$$l[i]$$$ stores the closest (to $$$a[i]$$$) smaller element to the left of i. $$$dl[i]$$$ stores the closest smaller element to the left of $$$l[i]$$$. Similar for right.
thanks
what's the cf difficulty level of C problem? was it that easy for soo many 'people'?
Please someone point mistake in my solution of problem D. It is failing on 2nd test case https://mirror.codeforces.com/contest/1988/submission/270941262
hi everyone, I wanted to ask about 3rd Problem. I try to do and of n with ~(1 << i) such that i can off each set bit in n without affecting the other bit so that I can generate seq. of numbers whose or should be n but I am getting the wrong answer in test2. can someone please tell me what I am thinking wrong?
here is code
I just wanted to ask something..
Isn't the tree like structure inherit a hierarchy wrt to its root node?? So isn' it always possible that the maximum rounds of killing we would need is two?? Since if we choose to kill from currently selected root node then in first round, we could kill all the monsters positioned at odd levels including the root node itself , and in second round we could all the even level monsters, and now there would be no monsters left to kill. Similarly if we choose to kill from one level below the root node, i.e. from 2nd level then we could kill all the even level monsters in 1st round, and in 2nd round all the odd level monsters could be killed.
So from any selected root node, we would always have exactly two ways to kill and in each way it would take exactly two round to kill all of them. And we would have n such ways to select the root node.
So isn't our dp should really be: dp[v][0/1], where 0 represent choosing the root node 'v' in the first round, and 1 represents choosing it in the second round. I think this is all the possible ways of killing we could have.
can someone verify this approach ?? Thanks.
For A, we can solve it like this : Merge n 1s into n and we can merge at most k 1s per time.
So :
f(n) = f(n — k) + 1, if n >= k
f(n) = 1, if n < k.
It's a $$$O(\frac n k)$$$ solution, I don't know how to convert this expression to an $$$O(1)$$$ expression.
bruv i spent 1 hour to solve the A problem but 15 minutes to come up with an answer for B (and an extra 30 minutes cuz i have skill issues)
Can anyone explain why the maximum number of rounds will be logN + 1 in problem D?
Hi. I have tried my best to explain my interpretation of the editorial in Part 2 of my comment.
Please let me know if you understand it, or there's any issue in my explanation.
include<bits/stdc++.h>
define int long long
using namespace std; const int N=3e5+10; int t,n,v[N],a[N],f[N][2],up,x[N],y[N],sum; vector<vector> vec; void dfs(int p) { f[p][1]=v[p]; int len=vec[p].size(); for(int i=0; i<len; i++) { int son=vec[p][i]; dfs(son); f[p][1]+=f[son][0]; f[p][0]+=max(f[son][0],f[son][1]); } } signed main() { cin>>t; while(t--) { sum=0; cin>>n; for(int i=1; i<=n; i++) { a[i]=0; for(int j=0; j<2; j++) { f[i][j]=0; } } vec.resize(N); for(int i=1; i<=n; i++) { cin>>v[i]; sum+=v[i]; } for(int i=1; i<=n-1; i++) { cin>>x[i]>>y[i]; a[y[i]]++; } vector help; for(int i=1; i<=n; i++) { if(a[i]==0) help.push_back(i); } int len=help.size(); for(int i=0; i<len-1; i++) { int tem=help[i]; for(int j=1; j<=n; j++) { if(x[j]==tem&&a[y[j]]>1) { a[y[j]]--; swap(x[j],y[j]); break; } } } for(int i=1; i<=n-1; i++) { vec[x[i]].push_back(y[i]); } for(int i=1; i<=n; i++) { if(a[i]==0) up=i; } //cout<<"---------"<<up<<endl; dfs(up); cout<<sum-max(f[up][1],f[up][0])+sum<<endl; vec.clear(); } } //2 1 //1 4 //3 2 //5 3 //2 6 //7 5 //16 8521 1428 4732 0223 //2 1 //1 4 //3 2 //5 3 //2 6 //7 5
why my code is wrong
feecle6418
Let the mex of a set be the smallest positive integer that does not appear in it. Note that in an optimal arrangement, bi=mex(j,i)∈Ebj
.
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 f(1)=1, f(u)≥1+∑1≤i<uf(i)→f(u)≥2u−1
This ends the proof.
The Proof is not clear and most of us are not even able to understand this:- bi=mex(j,i)∈Ebj
It's my request, if possible please edit the editorial. or Please reply this comment explaining the proof more properly. I will be thankful.
Note that in an optimal arrangement, bi=mex(j,i)∈Ebj.
okay, for root node, this is definitely true. but can someone give me the proof for every node?
can you please explain me what is bi=mex(j,i)(=Ebj here... i am not able to think or understand what it is.
bi is just mex of all the nodes adjacent to the ith node.
Hi. I have tried to expain this in Part 2 of my comment.
Please give that a read and let me know if you understand.
Let's call $$$\displaystyle m_i = \mathop{\mathrm{mex}}_{(j,i) \in E} b_j$$$.
If $$$b_i < m_i$$$, then $$$b_i = b_j$$$ holds for some $$$j$$$, which is not allowed (in the round $$$b_i = b_j$$$, the monster $$$i$$$ and $$$j$$$ are killed at the same time, but there's an edge between $$$j$$$ and $$$i$$$). If $$$b_i > m_i$$$, the monster $$$i$$$ can be killed in an earlier round (specifically, in the round $$$m_i$$$), because no other adjacent monster is killed in the round $$$m_i$$$, so this $$$b_i$$$ is not optimal. Therefore, $$$b_i = m_i$$$.
If possible please someone provide an explanation, why at most rounds in problem D is ⌊log2n⌋+1 ??
https://youtu.be/exUm24JN2-A?si=uQsyu0tz571kwinW check this
For Problem C the solution for testcase 1 has to be 2 i.e 0, 1
It is because the bitwise OR of 0 and 1 is also 1, so the answer for 1 is 2 and the sequence is 0 1. Please clear my doubt...
[...] Find the longest sequence of positive integers [...]
Thks for the cool round!
For D, any ideas on how to approach this when the graph has cycle?
Hello! Can someone please explain why the upper bound for the number of rounds to kill all the monsters is not 4?
What makes me think of this is because of Appel and Haken's 4 Color Theorem for loopless planar graphs. Any help and advice is greatly appreciated!
You are ignoring the damage that the monsters who are not killed in round 1 would inflict. In fact, according to what you are thinking, the upper bound should be 2 (why not kill monsters at odd level in round 1 and monsters in even levels in round 2?). But this has the same flaw as the greedy solution in knapsack, i.e, keep picking highest valued items as long as the total weight is less than the capacity.
But why is the upper bound $$$O(Log(n))$$$ regardless of the monster's damage? I talk about it in my video editorial
Aah ok
that was lol !!!
I used recursion and then memoized the solution using dp but I am still getting TLE on test 3. Plz help somebody !!!! :((((( Here is my solution 275618595
can someone help me write formal proof of this solution for problem B ->
first idea is every string of consecutive 0's can be replaced by a single 0 like 000000000 -> 0 what i did is i calculated ones in prefix and suffix of last zero -> there r 3 cases either prefix + suffix > total zeros , prefix + suffix < total zeros or equal
My solution to problem E, using monotonic stack, prefix sum, and binsearch.
First, notice we can use a monotonic stack to calculate $$$f(a)$$$. The idea is for each $$$i$$$ we can store the sum of all ranges with right endpoint at $$$i$$$, and quickly update from $$$i$$$ to $$$i+1$$$. Thus, if we go through the whole array, we will have the answer.
Specifically, keep a stack $$$s$$$ where each element is an index $$$i$$$ (representing $$$a_i$$$), and store $$$\sum_{1 \le i \le sz(s)} a_{s_i} \cdot (s_i - s_{i-1})$$$, which is the sum of all ranges with right endpoint at $$$i$$$. For each $$$i$$$ from $$$1$$$ to $$$n$$$, pop any indices $$$j$$$ from $$$s$$$ where $$$a_{s_j} > a_i$$$, then push $$$i$$$ into the stack, updating the sum accordingly.
Notice that the stack is monotonically increasing in value and index. Also notice that we can take a prefix sum of our stack $$$s$$$ from earlier: Additions/removals will still take $$$O(1)$$$ asymptotically.
This will give the answer for $$$a$$$. Call the index of the element we remove $$$i$$$. Now, notice that the answer for $$$b$$$ is quite similar to the answer for $$$a$$$ — we have to make $$$4$$$ adjustments from the answer for $$$a$$$ to get the answer for $$$b$$$:
#1 is trivial.
For #2, we can binary search for $$$a_i$$$ on the stack (since it is sorted). Call the resultant index on the array $$$left$$$. Then for any range $$$[l, i]$$$ where $$$left \le l < i$$$, the value is $$$a_i$$$. For the ranges $$$[l, i]$$$ where $$$0 \le l < left$$$, we can take the appropriate value from our prefix sum.
For #3, we can reuse the strategy for #2, keeping a backwards stack and prefix sum that starts from the end and goes towards the front.
For #4: I think the algorithm makes more sense if you think about it in your head... Essentially, for each element of the left stack, we binary search on the right stack and add values to the answer accordingly. We also need to subtract $$$a_i * (a_i - l) * (r - a_i - 1)$$$. Even though a single operation could go through the whole stack, it is still $$$O(\log n)$$$ per element asymptotically!
Implementation was very hard for me. 280260483
Problem D — The Omnipotent Monster Killer
Part 1 — DFS
Assume a rooted tree of monsters. We will assign each monster a number which denotes the round when it will be killed.
If i'th monster is killed at round r[i], then it means that it has lived for r[i] rounds. The damage caused by this monster is a[i]*r[i].
The monster at the child node cannot be killed in the same round as the monster at the parent.
We can do a dfs from the root monster and try killing the monsters in all possible rounds. When we fix a monster to be killed at round 'x', then we have to check by killing all the children in all rounds except 'x'.
We can of course, kill all the monsters in 2 rounds, say we kill all the monsters in the odd distance from root in one round and all in even distance in next. But this might not always give the minimum damage.
We need to determine how big the total number of rounds can be.
- If we assume it to be arbitrarily large, greater than number of monsters, then there would be some rounds when no monster is killed.
- We can have number of rounds equal to number of monsters. But if there are 3*1e5 monsters, then trying to kill each monster in 3*1e5 rounds will show TLE.
We can definitely improve this by grouping some monsters who are not connected by an edge.
Say, an alien told us that it is futile to play this game for 'u' number of rounds, i.e. there can be no more grouping possible to reduce number of rounds any further.
Assume a tree that has 'n' monsters and each monster is killed at round r[i] <= u. Root that tree at the monster that gets killed at last round, i.e. the u'th round. The direct children of the root are killed at rounds strictly less than u.
Now what can be said about the children that forced the parent to be killed at u'th round.
If there was some round r < u, where no children are getting killed, then the parent could have been killed in that r'th round. But here the premise is that the parent is killed exactly at round 'u', not earlier.
Parent could not get killed at round 1, because some child is getting killed at round 1.
Parent could not get killed at round 2, because some child is getting killed at round 2.
Parent could not get killed at round 3, because some child is getting killed at round 3.
.
Parent could not get killed at round "u-1", because some child is getting killed at round "u-1".
This is like MEX. Parent takes the MEX value of the rounds of the children.
Lets, look at the same tree and try to find the minimum monsters needed to ensure that there are 'u' rounds.
For root node to be killed at 'u'th round -
First child be killed at round 1. Minimum subtree size of the first child is such that it has minimum 1 round.
Second child be killed at round 2. Minimum subtree size of the second child is such that it has minimum 2 rounds.
.
"u-1"th child be killed at round "u-1". Minimum subtree size of the "u-1"th child is such that it has minimum "u-1" rounds.
If f(u) is a function that gives how many monsters at minimum are needed for 'u' rounds.
f(u) = (minimum monsters needed for 'u' rounds)
1 (Counting the root node)
+ f(1) (Subtree size of the child killed at round=minimum monsters needed for 1 round)
+ f(2) (Subtree size of the child killed at round 2=minimum monsters needed for 2 rounds)
.
+ f(u-1) (Subtree size of the child killed at round "u-1"=minimum monsters needed for "u-1" rounds)
This recurrence relation can be solved as following.
Subtracting above two equations
Using the resulting equation,
f(1) = 1 (for 1 round, at minimum 1 monster needed)
f(2) = 2*f(1) = 2 = 2^(2-1)
f(3) = 2*f(2) = 2*2 = 2^(3-1)
.
f(u) = 2^(u-1) (for "u" rounds, at minimum 2^(u-1) monsters needed)
For n monsters, how many rounds are enough?
f(x) = n
=> 2^(x-1) = n
=> x-1 = log(n) (taking log on both sides. log base 2 is assumed)
=> x = log(n) + 1
We perform the DFS trying each monster to get killed at each of log(n) rounds.
Time complexity depends on the implementation.
We kill a monster at round 1. The children of that monster are tried for all rounds except round 1. Then we try to kill that monster at round 2. The children are tried for all rounds except round 2. For each round of the parent and we try its children for log(n) rounds. Thus for 'n' monsters, the time complexity is O(n*log(n)*log(n)).
This can be further optimized to O(n*log(n)) by maintaining prefix and suffix minima arrays. Then there will be no need for iterating over all rounds of the children for every round of the parent. The "except round x" part for the children can be retrieved from the prefix and suffix minima arrays directly.
For Tutorial of problem-D, "depending on whether you use prefix/suffix maximums to optimize the taking max part." should be "depending on whether you use prefix/suffix maximums to optimize the taking min part.".
Why does this TLE for D?