codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

1658.md (18379B)


      1 Source: https://codeforces.com/blog/entry/101302
      2 
      3 Thank you for participating in the contest! We hope you enjoy the problems. You can also give feedback on each problem, it will help us much in future problem settings. By the way, feel free to share your solution!
      4 
      5 [1658A - Marin and Photoshoot](/contest/1658/problem/A "Codeforces Round 779 (Div. 2)")
      6 
      7 **Hint 1**
      8 
      9 How will you solve this problem if there are just $2$ male cosplayers?
     10 
     11 **Hint 2**
     12 
     13 Notice the distance between $2$ consecutive male cosplayers.
     14 
     15 **Tutorial**
     16 
     17 It is easy to see, in a beautiful picture, there must be at least $2$ female cosplayers between $2$ consecutive male cosplayers. It is also the sufficient condition, as if there are $x$ male cosplayers in a subsegment, there are at least $2(x - 1) = 2x - 2 \geq x$ for all $x \geq 2$.
     18 
     19 **Solution**
     20 
     21 **C++**
     22 
     23 ```
     24 #include <bits/stdc++.h>
     25 using namespace std;
     26  
     27 const int N = 2e5 + 5;
     28  
     29 int n;
     30 string s;
     31 vector<int> v;
     32  
     33 void solve() {
     34     v.clear();
     35     cin >> n >> s;
     36     int ans = 0;
     37     for (int i = 0; i < n; ++i) {
     38         if (s[i] == '0') v.push_back(i);
     39     }
     40     for (int i = 0; i < (int)v.size() - 1; ++i) {
     41         if (v[i + 1] - v[i] <= 2) ans += 2 - (v[i + 1] - v[i]) + 1;
     42     }
     43     cout << ans << '\n';
     44 }
     45  
     46 int main() {
     47     ios_base::sync_with_stdio(false);
     48     cin.tie(NULL);
     49     int t; cin >> t;
     50     while (t--) solve();
     51 }
     52 ```
     53 
     54 **Python**
     55 
     56 ```
     57 t = int(input())
     58 for _ in range(t):
     59     n = input()
     60     s = input()
     61     ans = 0
     62     cnt = 2
     63     for c in s:
     64         if c == '1': cnt += 1
     65         else:
     66             ans += max(2 - cnt, 0)
     67             cnt = 0
     68     print(ans)
     69 ```
     70 
     71 **Feedback**
     72 
     73 * Didn't solve
     74 * Good problem
     75 * Average problem
     76 * Bad problem
     77 
     78 [1658B - Marin and Anti-coprime Permutation](/contest/1658/problem/B "Codeforces Round 779 (Div. 2)")
     79 
     80 **Hint 1**
     81 
     82 Let's $ g = \gcd (1 \cdot p_1, \, 2 \cdot p_2, \, \dots, \, n \cdot p_n) $. What is the maximum value of $g$?
     83 
     84 **Hint 2**
     85 
     86 For each value of $g$, can you construct a satisfying permutation?
     87 
     88 **Tutorial**
     89 
     90 We can prove that $g \leq 2$.
     91 
     92 **Proof**
     93 
     94 Assuming $g \gt 2$:
     95 
     96 * If there exists a prime number $p \gt 2$ that $p \mid g$, there are $\left \lfloor \dfrac{n}{p} \right \rfloor$ numbers divisible by $p$, so we can match at most $2 \left \lfloor \dfrac{n}{3} \right \rfloor$ numbers into pairs, which is smaller than $n$.
     97 * Otherwise, we can match odd numbers with even positions, and even numbers with odd positions, which leads to $2 \mid g$. Because $p_2$ is odd, $2 \cdot p_2$ is not divisible by $2^k$ with $k \gt 1$.
     98 
     99 Therefore, $g\leq 2$.
    100 
    101 Therefore:
    102 
    103 * If $n$ is odd, the answer is $0$ since the number of odd is greater than the number of even.
    104 * Otherwise, we will match odd with even and vice versa. For odd number in even position, we have $(\dfrac{n}{2})!$ ways. According to the multiplicative rule, the answer will be $((\dfrac{n}{2})!)^2$.
    105 
    106 **Solution**
    107 
    108 **C++**
    109 
    110 ```
    111 #include <bits/stdc++.h>
    112 using namespace std;
    113 
    114 const int MOD = 998244353;
    115 
    116 void solve() {
    117     int n; cin >> n;
    118     if (n & 1) {
    119         cout << "0\n";
    120         return;
    121     }
    122     long long ans = 1;
    123     for (int i = 1; i <= n / 2; ++i) {
    124         ans *= 1LL * i * i % MOD;
    125         ans %= MOD;
    126     }
    127     cout << ans << '\n';
    128 }
    129 
    130 int main() {
    131     ios_base::sync_with_stdio(false);
    132     cin.tie(NULL);
    133     int t; cin >> t;
    134     while (t--) solve();
    135     return 0;
    136 }
    137 ```
    138 
    139 **Python**
    140 
    141 ```
    142 MOD = 998244353
    143 t = int(input())
    144 
    145 for _ in range(t):
    146 	n = int(input())
    147 	if n & 1:
    148 	    print(0)
    149 	    continue
    150 	ans = 1
    151 	for i in range(1, n // 2 + 1):
    152 		ans = ans * i % MOD
    153 	ans = ans * ans % MOD
    154 	print(ans)
    155 ```
    156 
    157 **Feedback**
    158 
    159 * Didn't solve
    160 * Good problem
    161 * Average problem
    162 * Bad problem
    163 
    164 [1658C - Shinju and the Lost Permutation](/contest/1658/problem/C "Codeforces Round 779 (Div. 2)")
    165 
    166 **Hint 1**
    167 
    168 There is exactly one $1$ in array $c$ (in $(i - 1)$-th cyclic shift, $c_i \gt 1$ if $p_1 \neq n$, and $c_i = 1$ if $p_1 = n$), so if the number of $1s$ is greater or less than one, the answer is $\texttt{NO}$.
    169 
    170 **Hint 2**
    171 
    172 We can rotate the array such that $c_1 = 1$ (initial state) because we don't have to construct the permutation, so if there exists a permutation with $p_1 = n$, the answer is $\texttt{YES}$.
    173 
    174 **Hint 3**
    175 
    176 Notice the difference of $c_i$ and $c_{i + 1}$.
    177 
    178 **Tutorial**
    179 
    180 In the $i$-th cyclic shift, if $p_1 \gt p_2$ then $c_{i + 1} \leq c_i$, otherwise $c_{i + 1} - c_i = 1$, so if there exists a position $i$ such that $c_{i + 1} - c_i \gt 1$, the answer is $\texttt{NO}$.
    181 
    182 This is the sufficient condition. It can be shown that, if $c_{i + 1} - c_i \leq 1$ for all $1 \leq i \lt n$, then there exists a permutation that satisfies.
    183 
    184 Here is a sketch of the construction: <https://codeforces.com/blog/entry/101302?#comment-899523>
    185 
    186 **Solution**
    187 
    188 **C++**
    189 
    190 ```
    191 #include <bits/stdc++.h>
    192 using namespace std;
    193  
    194 void solve() {
    195     int n; cin >> n;
    196     vector<int> a(n);
    197     for (int &v: a) cin >> v;
    198     if (count(a.begin(), a.end(), 1) != 1) {
    199         cout << "NO\n";
    200         return;
    201     }
    202     int p = find(a.begin(), a.end(), 1) - a.begin();
    203     rotate(a.begin(), a.begin() + p, a.end());
    204     for (int i = 1; i < n; ++i) {
    205         if (a[i] - a[i - 1] > 1) {
    206             cout << "NO\n";
    207             return;
    208         }
    209     }
    210     cout << "YES\n";
    211 }
    212  
    213 int main() {
    214     ios_base::sync_with_stdio(false);
    215     cin.tie(NULL);
    216     int t; cin >> t;
    217     while (t--) solve();
    218     return 0;
    219 }
    220 ```
    221 
    222 **Python**
    223 
    224 ```
    225 import sys
    226 input = sys.stdin.readline
    227  
    228 t = int(input())
    229 for _ in range (t):
    230     n = int(input())
    231     a = list(map(int, input().split()))
    232  
    233     if a.count(1) != 1:
    234         print("NO")
    235         continue
    236  
    237     a.append(a[0])
    238     ok = True
    239     for i in range (0, n):
    240         if a[i + 1] - a[i] > 1:
    241             ok = False
    242             break
    243     
    244     if ok: print("YES")
    245     else: print("NO")
    246 ```
    247 
    248 **Feedback**
    249 
    250 * Didn't solve
    251 * Good problem
    252 * Average problem
    253 * Bad problem
    254 
    255 [1658D1 - 388535 (Easy Version)](/contest/1658/problem/D1 "Codeforces Round 779 (Div. 2)")
    256 
    257 **Tutorial**
    258 
    259 Let's look at the binary representation of numbers from $0$ to $7$:
    260 
    261 * $000$
    262 * $001$
    263 * $010$
    264 * $011$
    265 * $100$
    266 * $101$
    267 * $110$
    268 * $111$
    269 
    270 Let us look at the $i$-th bit only (maybe $i=2$), we will get a sequence like $[0,0,1,1,0,0,1,1]$. Notice that the number of zeroes equals the number of ones in a prefix only when the length of the prefix is a multiple of $2^i$. Otherwise, there will be more zeros than ones.
    271 
    272 So, we will count the number of flipped and unflipped bits for each bit position.
    273 
    274 * If the number of ones is greater than the number of zeros, the $i$-th bit of $x$ must be $1$.
    275 * If the number of zeros is greater than the number of ones, the $i$-th bit of $x$ must be $0$.
    276 * If the number of ones is equal to the number of zeros, that $i$-th bit of $x$ can either be $0$ or $1$.
    277 
    278 However, if the number of ones is equal to the number of zeros, we can assign the $i$-th bit anything we like. The rough sketch of the proof is that if $x$ is inside $a$ then $x\oplus2^i$ is also inside $a$.
    279 
    280 **Solution**
    281 
    282 **C++**
    283 
    284 ```
    285 #include <bits/stdc++.h>
    286 using namespace std;
    287 
    288 const int N = 2e5 + 5;
    289 int p[N], cnt[32][2];
    290  
    291 void solve() {
    292     memset(cnt, 0, sizeof cnt);
    293     int l, r; cin >> l >> r;
    294     for (int i = l; i <= r; ++i) {
    295     	int x; cin >> x;
    296     	for (int j = 0; j <= 30; ++j, x >>= 1)
    297     		cnt[j][x & 1]++;
    298     }
    299     int ans = 0;
    300     for (int i = 0; i <= 30; ++i) {
    301     	ans |= ((cnt[i][0] < cnt[i][1]) * (1 << i));
    302     }
    303     cout << ans << '\n';
    304 }
    305 
    306 int main() {
    307     ios_base::sync_with_stdio(false);
    308     cin.tie(NULL);
    309     int t; cin >> t;
    310     while (t--) solve();
    311     return 0;
    312 }
    313 ```
    314 
    315 **Python**
    316 
    317 ```
    318 import sys
    319 input = sys.stdin.readline
    320  
    321 t = int(input())
    322 for _ in range (t):
    323     l, r = map(int, input().split())
    324     a = list(map(int, input().split()))
    325     cnt = [[0] * 2 for _ in range (32)]
    326  
    327     for x in a:
    328         for i in range (31):
    329             cnt[i][x & 1] += 1
    330             x >>= 1
    331  
    332     ans = 0
    333     for i in range (31):
    334         if (cnt[i][0] < cnt[i][1]):
    335             ans |= (1 << i)
    336     
    337     print(ans)
    338 ```
    339 
    340 [1658D2 - 388535 (Hard Version)](/contest/1658/problem/D2 "Codeforces Round 779 (Div. 2)")
    341 
    342 **Hint 1**
    343 
    344 If $a \oplus b = 1$, then $(a \oplus x) \oplus (b \oplus x) = 1$.
    345 
    346 **Hint 2**
    347 
    348 if $l$ is even and $r$ is odd, the last bit of $x$ can be either $0$ or $1$ (we can pair $a_i$ with $a_i \oplus 1$).
    349 
    350 **Tutorial**
    351 
    352 There are two solutions to this problem.
    353 
    354 If $l$ is even and $r$ is odd, we can skip the last bit and divide the range by two, then recursively solve it. Otherwise, we will pair $a_i$ with $a_i \oplus 1$, and we will left with at most $2$ candidates for $x$ to check.
    355 
    356 There is also another solution: we can iterate all possibilities of $x$ (by assuming $a_i$ is $l \oplus x$ for all $1 \leq i \leq n$). If $x$ is the hidden number, $l \leq a_i \oplus x \leq r$ for all $1 \leq i \leq n$, so the problem reduce to "count the number of $a_i$ that $l \leq a_i \oplus x \leq r$", which can be solved with binary trie.
    357 
    358 **Solution**
    359 
    360 **C++**
    361 
    362 ```
    363 #include <bits/stdc++.h>
    364 using namespace std;
    365 
    366 const int N = 2e5 + 5;
    367 int a[N], l, r; 
    368 set <int> s, s2;
    369  
    370 void solve() {
    371     int mul = 1;
    372     s.clear();
    373     cin >> l >> r; 
    374     for (int i = l; i <= r; ++i) {
    375         cin >> a[i];
    376         s.insert(a[i]);
    377     }
    378 
    379     for (; l % 2 == 0 && r % 2 == 1; l >>= 1, r >>= 1, mul <<= 1) {
    380         s2.clear();
    381         for (int i: s) s2.insert(i >> 1);
    382         swap(s, s2);   
    383     }
    384 
    385     int ans;
    386     if (l % 2 == 0) ans = r;
    387     else ans = l;
    388 
    389     for (int i: s) {
    390         if (s.find(i ^ 1) == s.end()) {
    391             int cur = i ^ ans;
    392             bool f = true;
    393             for (int j : s)
    394                 f &= ((cur ^ j) >= l && (cur ^ j) <= r);
    395             if (f) {
    396                 ans = cur;
    397                 break;
    398             }
    399         }
    400     }
    401     cout << ans * mul << '\n';
    402 }
    403 
    404 int main() {
    405     ios_base::sync_with_stdio(false);
    406     cin.tie(NULL);
    407     int t; cin >> t;
    408     while (t--) solve();
    409     return 0;
    410 }
    411 ```
    412 
    413 **Python**
    414 
    415 ```
    416 import sys
    417 input = sys.stdin.readline
    418  
    419 def solve(l: int, r: int, s: set):
    420     if l % 2 == 0 and r % 2 == 1:
    421         t = set()
    422         for v in s: t.add(v >> 1)
    423         return solve(l >> 1, r >> 1, t) << 1
    424     else:
    425         for v in s:
    426             if (v ^ 1) not in s:
    427                 ok = True
    428                 ans = v
    429                 if l % 2 == 0: ans ^= r
    430                 else: ans ^= l
    431                 for x in s:
    432                     if (x ^ ans) < l or (x ^ ans) > r:
    433                         ok = False
    434                         break
    435                 if ok: return ans
    436             
    437  
    438 t = int(input())
    439 for _ in range (t):
    440     l, r = map(int, input().split())
    441     s = set(map(int, input().split()))
    442     print(solve(l, r, s))
    443 ```
    444 
    445 **Feedback**
    446 
    447 * Didn't solve
    448 * Good problem
    449 * Average problem
    450 * Bad problem
    451 
    452 [1658E - Gojou and Matrix Game](/contest/1658/problem/E "Codeforces Round 779 (Div. 2)")
    453 
    454 **Hint 1**
    455 
    456 What if a player is forced to play in a cell where they get fewer points than the previous move?
    457 
    458 **Hint 2**
    459 
    460 Rephrase the problem, then solve it with dynamic programming.
    461 
    462 **Tutorial**
    463 
    464 Suppose that Marin places a token at $(a,b)$. If Gojou places a token at $(c,d)$ where $V_{c,d} \lt V_{a,b}$, then Gojou would not have any advantage as Marin can play at $(a,b)$ again. After a very huge number of turns, Marin will have more points than Gojou. Generally, if a player is forced to play in a cell where they get fewer points than the previous move, they would instantly lose.
    465 
    466 Therefore, we can rephrase the problem as such:
    467 
    468 * Apart from the first move, the token placed by a player must be more than Manhattan distance *k* away from the previous token placed on the matrix.
    469 * Apart from the first move, the token placed by a player must be on a cell with more points than the cell with the token placed by the previous player.
    470 * The player who plays the last token is the winner.
    471 
    472 This turns out to be a standard dynamic programming.
    473 
    474 Let $dp[i][j]$ return $1$ if the player who places a token at $(i,j)$ wins.
    475 
    476 Let $V_{a,b}=n^2$, then we have $dp[a][b]=1$ as a base case.
    477 
    478 Then we will fill the values of $dp$ in decreasing values of $V_{i,j}$. $dp[i][j]=1$ if for all $(i',j')$ such that $|i-i'|+|j-j'| \gt k$, we have $dp[i'][j']=0$. Note that by taking the contrapositive, this is equivalent to for all $(i',j')$ such that $dp[i'][j']=1$, we have $|i-i'|+|j-j'| \leq k$.
    479 
    480 Let us maintain a set $S$ that stores the pairs $(i',j')$ such that $dp[i'][j']=1$, then our operations are:
    481 
    482 * adding point $(i,j)$ to $S$
    483 * given $(i,j)$, check if for all $(i',j')$ in $S$, $|i-i'|+|j-j'| \leq k$
    484 
    485 Notice that $|i-i'|+|j-j'| \leq k \Leftrightarrow \max(|(i+j)-(i'+j')|,|(i-j)-(i'-j')|) \leq k$.
    486 
    487 Checking $\max(|(i+j)-(i'+j')|,|(i-j)-(i'-j')|) \leq k$ is very simple as we only need to store the minimum and maximum of all $(i+j)$ and $(i-j)$.
    488 
    489 **Solution**
    490 
    491 **C++**
    492 
    493 ```
    494 #include <bits/stdc++.h>
    495 using namespace std;
    496 
    497 const int N = 2e3 + 5;
    498 bool f[N][N];
    499 int l, r, u, d, n, k;
    500 vector<array<int, 5>> v;
    501 
    502 bool check(int i, int j) {
    503     return (abs(i - u) <= k && abs(i - d) <= k && abs(j - l) <= k && abs(j - r) <= k);
    504 }
    505 
    506 void solve(){
    507     cin >> n >> k;
    508     for (int i = 1; i <= n; ++i) {
    509         for (int j = 1; j <= n; ++j) {
    510             f[i][j] = false;
    511             int x; cin >> x;
    512             v.push_back({x, i, j, i + j, j - i});
    513         }
    514     }
    515 
    516     sort(v.begin(), v.end(), greater<array<int, 5>>());
    517     l = v[0][4], r = v[0][4], u = v[0][3], d = v[0][3];
    518     for (array<int, 5> cell: v) {
    519         if (check(cell[3], cell[4])) {
    520             f[cell[1]][cell[2]] = true;
    521             l = min(l, cell[4]);
    522             r = max(r, cell[4]);
    523             u = min(u, cell[3]);
    524             d = max(d, cell[3]);
    525         }
    526     }
    527 
    528     for (int i = 1; i <= n; ++i) {
    529         for (int j = 1; j <= n; ++j) {
    530             if (f[i][j]) cout << 'M';
    531             else cout << 'G';
    532         }
    533         cout << '\n';
    534     }
    535 }
    536 
    537 int main() {
    538     ios_base::sync_with_stdio(false);
    539     cin.tie(NULL);
    540     solve();
    541     return 0;
    542 }
    543 ```
    544 
    545 **Feedback**
    546 
    547 * Didn't solve
    548 * Good problem
    549 * Average problem
    550 * Bad problem
    551 
    552 [1658F - Juju and Binary String](/contest/1658/problem/F "Codeforces Round 779 (Div. 2)")
    553 
    554 **Hint 1**
    555 
    556 Let $b$ be the number of black balls and $w$ be the number of white balls.
    557 
    558 The answer will be impossible if $m$ is not a multiple of $\dfrac{b+w}{gcd(b, w)}$.
    559 
    560 **Observation**
    561 
    562 It is easy to show that the cuteness of $s$ is $\dfrac{b}{n}$.
    563 
    564 What is the number of $\texttt{1}$ in the concatenated string needed so that the answer exists?
    565 
    566 **Proof**
    567 
    568 The cuteness of $s$ is $\dfrac{b}{n} = \dfrac{b}{b+w}$ by definition.
    569 
    570 Now consider $t = s[l_1, r_1] + [l_2, r_2] + \dots + s[l_k, r_k]$, the cuteness of the concatenated string.
    571 
    572 The cuteness of $t$ is $\dfrac{b}{b+w}$, so the number of $\texttt{1}$ needed is $k = \dfrac{m \cdot w}{b + w}$.
    573 
    574 If $k$ is not an integer then there will be no answer, so $m$ must be a multiple of $\dfrac{b+w}{gcd(b, w)}$.
    575 
    576 **Hint 2**
    577 
    578 We don't need more than 2 parts, or to say $k \leq 2$ is needed in this problem.
    579 
    580 **Observation**
    581 
    582 Let $c_i =$ (the number of $\texttt{1}$ in $s[i \dots i + m - 1]$).
    583 
    584 For convenient, from now let assume the array and string is wrapped around: $s[i] = s[i + n]$ and $c_i = c_{i+n}$.
    585 
    586 We have $|c_i-c_{i+1}| \leq 1$ and there exists $c_i = y$ for all $y$ that $min(c_i) \leq y \leq max(c_i)$.
    587 
    588 **Contestant's Proof**
    589 
    590 GM+ [smax](/profile/smax "Grandmaster smax") provides a simple and clean answer [here](https://codeforces.com/blog/entry/101302?#comment-899678).
    591 
    592 **Author's Proof**
    593 
    594 Let $L = min(c_i)$, $R = max(c_i)$ and we are doing with wrap around arrays for convenient.
    595 
    596 We want to prove that for any $y$ that $L \leq y \leq R$ there will be some $c_i = y$.
    597 
    598 Let $d_i = max(c_p, c_{p+1}, \dots, c_i)$ for $p$ is the minimal position that $c_p = L$.
    599 
    600 Let $f_x$ is the first position $i$ starting $p$ that $d_i = x$, we have $d_{f_x} = c_{f_x}$
    601 
    602 [1] Since $L \leq y \leq R$ and, we have $L = d_p \leq d_{p+1} \leq \dots \leq d_{p+n-1} = R$.
    603 
    604 [2] Since $|c_{i+1} - c_i| \leq 1$ we can show that.
    605 
    606 $\forall p \lt i \lt p + n \rightarrow \left[\begin{array}{l} d_i = d_{i-1} \\ d_i = d_{i-1} + 1 \end{array}\right.$
    607 
    608 [3] Since $c_i \in \mathbb{N}$, we also have $d_i \in \mathbb{N}$
    609 
    610 From [1], [2], [3], if there is $d_i = v \gt L$ then there will be $d_j = v - 1$ for some $j$ that $p + (v - L) \leq j \lt i$.
    611 
    612 $\Leftrightarrow \forall v, min(d_i) \leq v \leq max(d_i) \rightarrow \exists d_{f_i} = v$
    613 
    614 $\Leftrightarrow \exists d_{f_i} = y$
    615 
    616 $\Leftrightarrow \exists c_{f_i} = y$
    617 
    618 **Tutorial**
    619 
    620 The answer will be impossible if $m$ is not a multiple of $\dfrac{b+w}{gcd(b, w)}$.
    621 
    622 Otherwise, it is proved that $k \leq 2$ is needed.
    623 
    624 Since we need to select a minimum $k$, let's first check if there is a solution with $k = 1$
    625 
    626 **Spoiler**
    627 
    628 If there exist such position $p$ that $1 \leq p \leq n - m + 1$ and $s[p, p + m - 1]$ have the same cuteness as $s[1, n]$ then we found an answer.
    629 
    630 Otherwise there must be an answer with $k = 2$, and it is simple too
    631 
    632 **Spoiler**
    633 
    634 If there exist such position $p$ that $1 \leq p \lt m$ and $s[1, p] \cup s[n - (m - p) + 1, n]$ have the same cuteness as $s[1, n]$ then we found an answer.
    635 
    636 Both can be done in linear $O(n)$ with the sliding window technique or prefixsum.
    637 
    638 **Solution**
    639 
    640 **C++**
    641 
    642 ```
    643 #include <bits/stdc++.h>
    644 using namespace std;
    645  
    646 int main() {
    647     ios_base::sync_with_stdio(false);
    648     cin.tie(nullptr);
    649     int t; cin >> t;
    650     while (t--) {
    651         int n, k; cin >> n >> k;
    652         string s; cin >> s;
    653         int one = count_if(s.begin(), s.end(), [](char c) { return c == '1'; });
    654         if (1LL * one * k % n != 0) {
    655             cout << "-1\n";
    656         } else {
    657             one = 1LL * one * k / n;
    658             vector<int> suf(2 * n + 1);
    659             for (int i = 1; i <= 2 * n; i++) {
    660                 suf[i] = suf[i - 1] + (s[(i - 1) % n] == '1');
    661                 if (i >= k && suf[i] == suf[i - k] + one) {
    662                     if (i <= n) {
    663                         cout << "1\n";
    664                         cout << i - k + 1 << " " << i << '\n';
    665                     } else {
    666                         cout << "2\n";
    667                         cout << 1 << " " << i - n << '\n';
    668                         cout << i - k + 1 << " " << n << '\n';
    669                     }
    670                     break;
    671                 }
    672             }
    673         }
    674     }
    675 }
    676 ```
    677 
    678 **Feedback**
    679 
    680 * Didn't solve
    681 * Good problem
    682 * Average problem
    683 * Bad problem