I only got 1 :(. Should have got C but not good with graphs/dijkstra's. :( :(

His speed is just unbelievable.

He is dmga44

A was really straightforward. Very little case work. (Actually 0).

#include<bits/stdc++.h>

void solve() {
    int n, k;
    cin >> n >> k;
    string s;
    cin >> s;
    int tcnt0 = count(all(s), '0');
    int tcnt1 = count(all(s), '1');
    int cnt0 = 0, cnt1 = 0;
    for (int i = 0; i < k - 1; i++) {
        if (s[i] == '0') cnt0++;
        else if (s[i] == '1') cnt1++;
    }
    int ans = 0;
    for (int i = k - 1; i < n; i++) {
        if (s[i] == '0') cnt0++;
        else if (s[i] == '1') cnt1++;
        if (cnt0 == 0 && cnt1 == tcnt1) {
            ans++;
        }
        if (s[i - k + 1] == '0') cnt0--;
        else if (s[i - k + 1] == '1') cnt1--;
    }
    cout << (ans == 1 ? yes : no) << '\n';
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t = 1;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

I write this solution during contest too and it passed. Maybe the tests are too weak.

That is essentially the same as editorial, just another way how to implement 0/1 bfs.The values in array $$$d$$$ are euqivalent to the amount of iterations before you discovered some value in your case.

Why would it be wa? also if you know z you don't need to bruteforce y. This is my solution

Will you please explain more what you are doing in remaining cases(a>1mil) part? I am unable to understand only by watching your code.

maybe 01bfs

Let me know if you got the reason why using BFS is not working.Thanks in advance

The outcome of the random variable $$$X_v$$$ depends on status of the parents of $$$v$$$. That is, it just needs to 'keep track' of the parents to know when $$$v$$$ has become good and it needs to stop performing operations. This intuition explains why we don't care about the operations which pick something apart from $$$v$$$ and its parents. Those operations neither change the state of $$$v$$$'s parents, nor do they directly change the value of the random variable (which would only be affected when we pick precisely $$$v$$$).

A similar argument holds for not caring about whether we pick good or bad vertices. Even if we pick a good vertex, it was already coloured black from earlier. So the status of none of the parents change. We know we didn't pick $$$v$$$ itself, since the process would have already stopped if $$$v$$$ was good beforehand. This operation doesn't affect the value of the random variable as well. And so we're free to consider them as valid moves.

We want $$$B+Y$$$ to be a multiple of $$$A+X$$$, i.e., $$$B+Y = k(A+X)$$$ for some positive integer $$$k$$$.

If someone told you what $$$k$$$ you need to use, then part 1 of the editorial tells you how to find $$$X$$$ and $$$Y$$$ such that $$$X+Y$$$ is smallest. We have, $$$Y = kX+kA-B$$$ and $$$X+Y = (k+1)X+kA-B$$$. To minimize $$$X+Y$$$ is then same is to minimize $$$X$$$, because $$$k$$$, $$$A$$$, and $$$B$$$ are fixed. We choose smallest $$$X$$$ such that $$$Y \ge 0$$$ (recall $$$Y = kX+kA-B$$$). This value is $$$\max(0, \lfloor\frac{B-1}{k}\rfloor + 1 -A)$$$ (convince yourself of this).

Part 2 then tells you that for $$$k \le \sqrt{B})$$$ you can just compute this value, and the number of different values of $$$\lfloor\frac{B-1}{k}$$$ for $$$k \gt \sqrt{B}$$$ is at most $$$\sqrt{B}$$$. For example, if $$$B = 101$$$, then $$$\lfloor\frac{B-1}{k}\rfloor$$$ can take values $$$9, 8, 7, 6, 5, 4, 3, 2, 1$$$ if $$$k\ge 11$$$. So you compute minimizing $$$X$$$ using $$$k = 1, 2, \ldots, \sqrt{B}$$$ first then compute minimizing $$$X$$$ using $$$\lfloor\frac{B-1}{k}\rfloor = 1, 2, \ldots, \sqrt{B}$$$. (Maybe try 2 or 3 more values if I am missing some constants.)

I also couldn't understand the editorial of B. Then I looked at more editorials and found a better explanation from the official video editorial:

For B + Y = k(A+X), there are two approaches to find X + Y:

• Approach 1: Enumerate X from 0 to A-1, we can get a value of X + Y for each case and keep the minimum.
• Approach 2: Enumerate k from 1 to B/A, we can get a value of X + Y for each case and keep the minimum.

Note the range of X and k, when A is extremely small or extremely large, either Approach 1 or Approach 2 can be very slow. Therefore, pick a value of sqrt(B) to determine to only use the faster of the 2 approaches.

In path every consecutive vertex is connected directly by an edge. 2 and 3 do not share an edge