**Tutorial**

Tutorial is loading...

**Solution (adedalic)**

```
fun main() {
val t = readLine()!!.toInt()
for (ct in 1..t) {
val (str, int, exp) = readLine()!!.split(' ').map { it.toInt() }
val minAddStr = maxOf(0, (exp + int - str + 2) / 2)
println(maxOf(exp - minAddStr + 1, 0))
}
}
```

Idea: Roms

**Tutorial**

Tutorial is loading...

**Solution (Roms)**

```
#include <bits/stdc++.h>
using namespace std;
const int N = 105;
int t;
int n, m;
int d[N], h[N];
int main() {
cin >> t;
for(int tc = 0; tc < t; ++tc){
cin >> n >> m;
int maxDH = -2e9;
for(int i = 0; i < n; ++i){
cin >> d[i] >> h[i];
maxDH = max(maxDH, d[i] - h[i]);
}
int res = 1;
int maxD = *max_element(d, d + n);
m -= maxD;
if(m > 0){
if(maxDH <= 0) res = -1;
else res += (m + maxDH - 1) / maxDH;
}
cout << res << endl;
}
return 0;
}
```

1217C - The Number Of Good Substrings

Idea: Roms

**Tutorial**

Tutorial is loading...

**Solution (Roms)**

```
#include <bits/stdc++.h>
using namespace std;
const int N = int(3e5) + 99;
int t;
string s;
int nxt[N];
int main() {
cin >> t;
for(int tc = 0; tc < t; ++tc){
cin >> s;
for(int i = 0; i < s.size(); ++i)
if(s[i] == '1') nxt[i] = i;
else nxt[i] = (i == 0? -1 : nxt[i - 1]);
int res = 0;
for(int r = 0; r < s.size(); ++r){
int sum = 0;
for(int l = r; l >= 0 && r - l < 20; --l){
if(s[l] == '0') continue;
sum += 1 << (r - l);
if(sum <= r - (l == 0? -1 : nxt[l - 1]))
++res;
}
}
cout << res << endl;
}
return 0;
}
```

Idea: BledDest

**Tutorial**

Tutorial is loading...

**Solution (Roms)**

```
#include<bits/stdc++.h>
using namespace std;
const int N = int(1e6) + 55;
int n, m;
vector <pair<int, int> > g[N];
int col[N];
bool cyc;
int res[N];
void dfs(int v){
col[v] = 1;
for(auto p : g[v]){
int to = p.first, id = p.second;
if(col[to] == 0){
dfs(to);
res[id] = 1;
}
else if(col[to] == 2)
res[id] = 1;
else{
res[id] = 2;
cyc = true;
}
}
col[v] = 2;
}
int main(){
cin >> n >> m;
for(int i = 0; i < m; ++i){
int u, v;
cin >> u >> v;
--u, --v;
g[u].push_back(make_pair(v, i));
}
for(int i = 0; i < n; ++i)
if(col[i] == 0)
dfs(i);
cout << (cyc? 2 : 1) << endl;
for(int i = 0; i < m; ++i) cout << res[i] << ' ';
cout << endl;
return 0;
}
```

Idea: BledDest

**Tutorial**

Tutorial is loading...

**Solution (PikMike)**

```
#include <bits/stdc++.h>
#define forn(i, n) for (int i = 0; i < int(n); i++)
using namespace std;
const int N = 200 * 1000 + 13;
const int INF = 2e9;
const int LOGN = 9;
struct node{
int best;
int mn[LOGN];
node(){
best = INF;
forn(i, LOGN)
mn[i] = INF;
}
int& operator [](int x){
return mn[x];
}
};
int a[N];
node t[4 * N];
void upd(node &t, int val){
int x = val;
forn(i, LOGN){
if (x % 10 != 0)
t[i] = min(t[i], val);
x /= 10;
}
}
node merge(node &a, node &b){
node c;
c.best = min(a.best, b.best);
forn(i, LOGN){
c[i] = min(a[i], b[i]);
if (a[i] < INF && b[i] < INF)
c.best = min(c.best, a[i] + b[i]);
}
return c;
}
void build(int v, int l, int r){
if (l == r - 1){
t[v] = node();
upd(t[v], a[l]);
return;
}
int m = (l + r) / 2;
build(v * 2, l, m);
build(v * 2 + 1, m, r);
t[v] = merge(t[v * 2], t[v * 2 + 1]);
}
void upd(int v, int l, int r, int pos, int val){
if (l == r - 1){
t[v] = node();
upd(t[v], val);
return;
}
int m = (l + r) / 2;
if (pos < m)
upd(v * 2, l, m, pos, val);
else
upd(v * 2 + 1, m, r, pos, val);
t[v] = merge(t[v * 2], t[v * 2 + 1]);
}
node get(int v, int l, int r, int L, int R){
if (l == L && r == R)
return t[v];
int m = (l + r) / 2;
if (R <= m)
return get(v * 2, l, m, L, R);
if (L >= m)
return get(v * 2 + 1, m, r, L, R);
node ln = get(v * 2, l, m, L, m);
node rn = get(v * 2 + 1, m, r, m, R);
return merge(ln, rn);
}
int main() {
int n, m;
scanf("%d%d", &n, &m);
forn(i, n)
scanf("%d", &a[i]);
build(1, 0, n);
forn(i, m){
int t, x, y;
scanf("%d%d%d", &t, &x, &y);
--x;
if (t == 1)
upd(1, 0, n, x, y);
else{
node res = get(1, 0, n, x, y);
printf("%d\n", res.best == INF ? -1 : res.best);
}
}
return 0;
}
```

1217F - Forced Online Queries Problem

Idea: BledDest

**Tutorial**

Tutorial is loading...

**Solution (PikMike)**

```
#include <bits/stdc++.h>
#define forn(i, n) for (int i = 0; i < int(n); i++)
using namespace std;
const int BUF = 10 * 1000 * 1000 + 13;
const int N = 300 * 1000 + 13;
const int M = 300 * 1000 + 13;
const int P = 400;
struct query{
int t, x, y;
int e0, e1;
};
int n, m;
query q[M];
int p[N], rk[N];
int cnt;
int* where[BUF];
int val[BUF];
void rollback(){
while (cnt > 0){
*where[cnt - 1] = val[cnt - 1];
--cnt;
}
}
int getp(int a){
return (a == p[a] ? a : getp(p[a]));
}
void unite(int a, int b){
a = getp(a), b = getp(b);
if (a == b) return;
if (rk[a] < rk[b]) swap(a, b);
where[cnt] = &rk[a];
val[cnt++] = rk[a];
where[cnt] = &p[b];
val[cnt++] = p[b];
assert(cnt <= BUF);
rk[a] += rk[b];
p[b] = a;
}
int getpFast(int a){
return (a == p[a] ? a : p[a] = getpFast(p[a]));
}
void uniteFast(int a, int b){
a = getpFast(a), b = getpFast(b);
if (a == b) return;
if (rk[a] < rk[b]) swap(a, b);
rk[a] += rk[b];
p[b] = a;
}
struct edge{
int v, u;
};
bool operator <(const edge &a, const edge &b){
if (a.v != b.v)
return a.v < b.v;
return a.u < b.u;
}
edge edges[2 * M];
map<edge, int> rev;
bool used[2 * M];
bool state[2 * M];
int ans[M];
vector<int> cur;
void rebuild(int l){
int r = min(m, l + P);
forn(i, n) p[i] = i, rk[i] = 1;
memset(used, 0, sizeof(used));
memset(state, 0, sizeof(state));
forn(i, l) if (q[i].t == 1){
int e = (ans[i] ? q[i].e1 : q[i].e0);
used[e] = true;
state[e] ^= 1;
}
for (int i = l; i < r; ++i) if (q[i].t == 1)
used[q[i].e0] = used[q[i].e1] = false;
cur.clear();
cnt = 0;
forn(i, l) if (q[i].t == 1){
int e = (ans[i] ? q[i].e1 : q[i].e0);
if (used[e] && state[e]){
state[e] = false;
uniteFast(edges[e].v, edges[e].u);
}
else if (!used[e] && state[e]){
state[e] = false;
cur.push_back(e);
}
}
}
int get_edge(edge e){
if (!rev.count(e)){
int k = rev.size();
edges[k] = e;
rev[e] = k;
}
return rev[e];
}
int main(){
scanf("%d%d", &n, &m);
forn(i, m){
scanf("%d%d%d", &q[i].t, &q[i].x, &q[i].y);
--q[i].x, --q[i].y;
if (q[i].t == 1){
edge e({q[i].x, q[i].y});
if (e.v > e.u) swap(e.v, e.u);
q[i].e0 = get_edge(e);
e.v = (e.v + 1) % n, e.u = (e.u + 1) % n;
if (e.v > e.u) swap(e.v, e.u);
q[i].e1 = get_edge(e);
}
}
string res = "";
ans[0] = 0;
forn(i, m){
if (i % P == 0)
rebuild(i);
int x = (q[i].x + ans[i]) % n;
int y = (q[i].y + ans[i]) % n;
if (x > y) swap(x, y);
if (q[i].t == 1){
rollback();
int e = get_edge({x, y});
auto it = find(cur.begin(), cur.end(), e);
if (it == cur.end())
cur.push_back(e);
else
cur.erase(it);
ans[i + 1] = ans[i];
}
else{
for (auto e : cur)
unite(edges[e].v, edges[e].u);
bool rc = (getp(x) == getp(y));
ans[i + 1] = rc;
res += ('0' + rc);
}
}
puts(res.c_str());
return 0;
}
```

Thank you very much for the round!

In E, it's said:

The problem now got reduced to: find a pair of numbers $$$a_i$$$ and $$$a_j$$$ such that $$$l$$$ $$$<=$$$ $$$i$$$ $$$<=$$$ $$$j$$$ $$$<=$$$ $$$r$$$, there is at least one position such that both $$$a_i$$$ and $$$a_j$$$ have non-zero digits on it and $$$a_i$$$ $$$+$$$ $$$a_j$$$ is minimal possible.Shouldn't $$$i$$$ and $$$j$$$ imply $$$i$$$ $$$!=$$$ $$$j$$$?

I think it does

why is the bound from problem D so low? the solution should be in $$$O(n)$$$?

i'm not sure, but the checker may have a higher asymptotic time complexity, $$$O(n^2)$$$, for example

the checker will create a graph with edges of a single color (at most two graphs) and do a toposort on each of them to detect cycles. Therefore the checker is in $$$O(n+m)$$$ and can also handle much larger inputs

I think in general when you're setting problems, you should strive to exclude all the naive solutions, but let certain solutions pass. However, if possible, you should try not to give away desired complexity with the bounds, because that makes the problem easier. Usually, this second part is not possible because CF has a lot of problems where O(n^2) is naive and O(n) or O(n log n) is optimal, so any MAXN less than 10^5 will let O(n^2) solutions pass.

However, here, the naive solutions are in the exponential range, and there aren't really any "bad" quadratic solutions, so I think it's okay to leave the bounds there so that it doesn't give anything away about the solution.

well the idea may sound good but by setting the limit like this you risk that weird stuff gets AC... for example those:

randomized (which seems to be correct even without randomisation the author just did not realized that it would always work...): 60128957

slow solutions in $$$O(n^2)$$$: 60121420 60123728

IMO, this problem $$$O(n^2)$$$ solution isn't really bad. Checking cycles in $$$O(n)$$$ is important, but that's not the main idea and it leaves more freedom to slow languages and implementations.

here is written if r-l>18 then f(l,r)>2*10^5.and why? example: 00000000000000000000000000001. it's obvious that that binary number is 1.

also here is written — "lets iterate over the right boundary of substring and high 1-bit position (denote it as r and l respectively)", which means that we consider only the cases when a[l] == '1'

Can you share more questions like this?

Use of nxt array was something extraordinary... is it a general technique like building prefix sum array?

can you explain where we are using binary search in this problem because the problem is tagged as binary search

if f(l,r) > 2*10^5 then the binary number can't fit in the string

While solving A by fixing the condition on minAddI, I get WA.

What's the mistake here? Can't we look at the various ways of points to be added for Intelligence?

the res has to be lower than exp + 1! testcase: 4 1 0

can somebody explain me problem c? you can write short answer, but bigger is better :D

My solution is like this: Iterate through the string (i), then if encounter a '1', start another loop from the i position (j), this time calculating the decimal expansion of binary from i to j, then checking if number of previous consecutive zeros + (j — i + 1) is larger than or equal to the decimal expansion (cuz the length is equal to the decimal expansion).

for example,

thanks, but i get idea after 5 minutes of that comment, thanks anyways.

What will be the time complexity ?

n^2

C*n, where C is a constant.

wow so op

I have written the same algorithm still I am getting wrong answer on one test case. Can you please check it?I think it should be (right + prevZero >= num)

please i am not able to understand where we are using binary search in this problem because the problem is tagged as binary search

thank you so much i was struggling with this question from 2 days when i read your explanation i got it...!

Can somebody explain B? How does the formula come? I think sorting on the basis of difference is enough. After sorting we just have to see the first element, isn't?

if max damage >= head, you only need 1 hit if it's not and max ratio pair of damage and regen <= 0, you wont be able to win

lastly, you know you need to deal x times max ratio pair of damage and regen + 1 times using max damage to finish, so the answer will be x + 1 ( 1 times using max damage).

Another way to color edges in problem D. Neither simpler nor harder but just another XD.

Let's iterate over all vertices and color all "$$$in$$$" edges in color $$$1$$$ and "$$$out$$$" edges in color $$$2$$$. For every cycle, there will be the vertex which was considered last in it (let's call it $$$u$$$). It implies that color from the previous vertex in the cycle to $$$u$$$ and color from $$$u$$$ to the next vertex in the cycle are different.

Does anyone know how to solve F in LCT implementation?

can you explain c? such algorithm does not support substrings like 00000000000001, because there hightest position is 13 and lowest 0, i don't understand please explain to me

I have a doubt in E, in the proof that an unbalanced set can never be made balanced again. Where are you using the assumption that $$$a\subset b$$$ ?.

We've made some set unbalanced by having two numbers with non-zero digits at some position — that's the set $$$a$$$. So now we can always find such a position in the set $$$b$$$.

Another easier approach to problem D:

Suppose a graph $$$ G = (V, E) $$$. Partition $$$ E $$$ to one group contains $$$ in > out $$$ only, and one group contain $$$ out > in $$$ only. Clearly no cycle in two sets. So the maximum number of colour is 2. One can just check if 1 colour is OK.

Can you explain your solution in detail? Thanks.

The lower bound is trivially 1.

Construction of the upper bound:

Consider two sets

and

Note that they are disjoint and their union is $$$E$$$. Also note that no cycle exist in both two sets. So there always exist one valid coloring method when number of colour is 2, i.e. the upper bound of the answer is 2.

Check if answer is 1 by cycle detection.

That's a very nice and intuitive solution. Thanks

Hey. Can you please tell me why two coloring the edges when the graph has cycle doesn't work? Here's my code: https://codeforces.com/contest/1217/submission/60264580

If you simulate your algorithm for test case 3 you will see.

I used to implement the same as you.

Can someone explain me why my code to F with block = 500 gets AC, but with block = sqrt(n) + 10 gets WA? https://codeforces.com/contest/1217/submission/60218374, https://codeforces.com/contest/1217/submission/60218188.

You missed a trivial solution to D: If there's a cycle, paint each edge $$$(u,v)$$$ such that $$$u>v$$$ black and all others white.

Nice solution! Actually I think that this is almost the same as the one in the editorial. Just that I don't like the complicated proof that was presented.

I think that we can easily prove that your solution works because if we consider the indexes of nodes that are in a cycle, there will obviously be a distinct maximum and minimum index because there are at least 2 nodes in a cycle.

The predecessor of the node with max index clearly has a smaller index. This means that we have an edge (u, v) where u < v. The predecessor of the node with minimum index clearly has a larger index. This means that we have an edge (u, v) where u > v.

Therefore, in any cycle, we will always have an edge (u, v) where u > v and an edge (u', v') where u' < v'. In this way, we will always have at least one black and one white edge in a cycle.

I believe this proof works for the official solution as well.

Why I got TLE in E,my solution is only O((n+m)⋅logn⋅log10MAXN).link

In problem C why we are doing precalculation of nxt array?? can someone elaborate this?

I'm not sure I understand the editorial solution either, but I coded up a simple brute-force / two pointer solution with a pruning heuristic: 60334519

To summarize, we iterate through the string from left to right. If $$$s[i] = 0$$$, we increment a $$$len$$$ accumulator and move on. If $$$s[i] = 1$$$, we start a secondary loop, where we keep track of the potential values of $$$f(z,j)$$$ (where $$$z$$$ is an imaginary pointer $$$\leq i$$$ that includes the "streak" of $$$0$$$s just before this $$$1$$$ if it exists). $$$ans$$$ is incremented whenever $$$f(z,j) \leq len(z,j)$$$ since it means we have found a good substring (you can "cut" a substring of the right length), but as soon as $$$f(z,j) > len(z,j)$$$ no more good substrings can be found from this position as $$$f$$$ grows faster than $$$len$$$, so we cut off the search and reset $$$len$$$ before moving on. Since the inner loop will never iterate more than $$$\lfloor \log_2 n \rfloor + 1$$$ times before being cut off, the algorithm runs in $$$O(n \log n)$$$ time.

Edit: Actually it might be in $$$O(n)$$$ time, because an adversarial input can only force more inner loop iterations by including zeros before the one, but zeros don't trigger the inner loop, and increasing the number of zeros has rapidly diminishing returns

Edit 2: Just noticed that toshinaritong explained a similar solution

Can you please elaborate how can we cut a substring of right length if f(z,j)<=len(z,j)

$$$f(z,j) \leq len(z,j) \Rightarrow \exists! x : z \leq x \leq i \land f(x,j) = len(x,j)$$$, i.e. substring $$$x..j$$$ is "good".

In less formal terms, the indices between $$$z$$$ and $$$i$$$ indicate the "pool" of zeros we can use to manipulate the length of the substring; as long as $$$f(z,j) \leq len(z,j)$$$ we can always choose to include the exact number of zeros required for the substring to be good. When $$$f(z,j) > len(z,j)$$$, we don't have enough zeros, so we break the inner loop and move on.

Or in more concrete terms, take the example $$$s = 00001010$$$

When $$$i = 5$$$ (one-indexed), $$$z = 1$$$. Since $$$s_5 = 1$$$, we start the inner loop.

When $$$j = 5$$$, $$$f(z, j) = 1 \leq len(z, j) = 5$$$. Pick $$$x = 5$$$. Note that substring $$$5..5$$$ is good cause $$$f(5, 5) = 1 = len(5, 5)$$$

When $$$j = 6$$$, $$$f(z, j) = 2 \leq len(z, j) = 6$$$. Pick $$$x = 5$$$. Note that substring $$$5..6$$$ is good cause $$$f(5, 6) = 2 = len(5, 6)$$$

When $$$j = 7$$$, $$$f(z, j) = 5 \leq len(z, j) = 7$$$. Pick $$$x = 3$$$. Note that substring $$$3..7$$$ is good cause $$$f(3, 7) = 5 = len(3, 7)$$$

When $$$j = 8$$$, $$$f(z, j) = 10 > len(z, j) = 8$$$, so we break the loop and continue iterating $$$i$$$.

Thank you, now I understand.

Problem E. While updating, why don't we consider the case when a[pos] was the minimal number with non-zero j-th digit in the interval [l,r), and x > a[pos]?

For instance we have the array [1,2] and we're getting the update query with pos = 1, x = 5. When updating, t[v] for [1,2), min_digit[0] still will be 1, but it should be 5.

Ok, I understood it.

Can someone please help in problem D.

I am using the concept of back-edge only, If I found a back edge, color it with '2', else 1.

My solution: https://codeforces.com/contest/1217/submission/60415966 Its based on this article: https://cp-algorithms.com/graph/bridge-searching.html

The article you are referring to is for undirected graphs, not directed ones.

DFS on digraphs induces more types of edges, you can read it here.

There's something weird with problem F. I got accepted with 748ms by setting P=5*10^4. If I use P=sqrt(m), my submission receives TLE verdict. What is going on?

I am getting a TLE on test case 5 for problem E — Sum Queries. Can someone tell me how to make my solution faster ? 62117228

can i do the same in problem d as in the editorial, but instead just make the first edge of a cycle into a second color, all the others edges are the first color? if im not mistaking the logic of the proof of my solution is the same as authors solution, but my solution gets wa3. can someone tell why approach with first edge in cycle is not working, or its working and my implementation is bad submission

I think setting such TL in problem E is stupid. I don't care about cache-friendliness or whatever. If my solution has the right complexity, it should pass.

For the above case(problem D), a cycle is possible with black edges. Black ones are black edges and purple edges are white edges. Visiting order of DFS is 1, 2, 3, 4, 5. If I'm missing something, can anyone say what is it?