2092.md (23749B)
1 Source: https://codeforces.com/blog/entry/141023 2 3 Thank you for participating, and we truly hope you enjoyed the contest! 4 5 **How did you find the contest?** 6 7 * Great: 8 * Good: 9 * Average: 10 * Bad: 11 * Trash: 12 13 **Which problem was your favorite?** 14 15 * A: 16 * B: 17 * C: 18 * D: 19 * E: 20 * F: 21 22 **Which problem did you find the least enjoyable?** 23 24 * A: 25 * B: 26 * C: 27 * D: 28 * E: 29 * F: 30 31 --- 32 33 ## [2092A - Kamilka and the Sheep](/contest/2092/problem/A "Codeforces Round 1014 (Div. 2)") 34 35 Author: [k1sara](/profile/k1sara "Grandmaster k1sara") 36 37 **Hint** 38 39 It's always possible to make Kamilka's pleasure at least $|x - y|$ for any $x, y \in a$. 40 41 **Solution** 42 43 First of all, it can be observed that for any two sheep with beauty levels $x \lt y$, the maximum possible pleasure cannot exceed $y - x$, since $\gcd(x, y) = \gcd(x, y - x)$. 44 45 Secondly, we can choose $x = \min(a)$, $y = \max(a)$, and $d = -x \bmod (y - x)$, achieving a pleasure of $\max(a) - \min(a)$. 46 47 Thus, the answer is $\max(a) - \min(a)$. 48 49 **Code (C++)** 50 51 ``` 52 #include <bits/stdc++.h> 53 54 using namespace std; 55 56 void solve() { 57 int n; cin >> n; 58 vector<int> a(n); 59 for (int i = 0; i < n; i++) cin >> a[i]; 60 sort(a.begin(), a.end()); 61 cout << a[n - 1] - a[0] << endl; 62 } 63 64 signed main() { 65 ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); 66 int tt; cin >> tt; 67 while (tt--) { 68 solve(); 69 } 70 } 71 ``` 72 73 **Code (Python)** 74 75 ``` 76 t = int(input()) 77 78 for test in range(t): 79 n = int(input()) 80 a = [int(i) for i in input().split()] 81 print(max(a) - min(a)) 82 ``` 83 84 **Rate the problem** 85 86 * Amazing problem: 87 * Good problem: 88 * Average problem: 89 * Bad problem: 90 * Didn't solve: 91 92 ## [2092B - Lady Bug](/contest/2092/problem/B "Codeforces Round 1014 (Div. 2)") 93 94 Author: [sergeev.PRO](/profile/sergeev.PRO "Master sergeev.PRO") 95 96 **Hint 1** 97 98 Note that you can split strings $a$ and $b$ into two "zig-zags": $a_0, b_1, a_2, b_3, \dots$ and $b_0, a_1, b_2, a_3, \dots$ 99 100 **Hint 2** 101 102 What are the necessary and sufficient conditions for each of these zig-zags? 103 104 **Solution** 105 106 Note that you can split strings $a$ and $b$ into two "zig-zags": $a_0, b_1, a_2, b_3, \dots$ and $b_0, a_1, b_2, a_3, \dots$. 107 108 For each of these zig-zags, you can achieve any sequence of `0`s and `1`s, provided that their quantities within the zig-zag are preserved. Therefore, the answer is `Yes` if and only if the number of `0` is at least $\lceil \frac{n}{2} \rceil$ in the first zig-zag and at least $\lfloor \frac{n}{2} \rfloor$ in the second one. 109 110 **Code (C++)** 111 112 ``` 113 #include <iostream> 114 115 using namespace std; 116 117 void solve() { 118 int n; cin >> n; 119 string a, b; cin >> a >> b; 120 int cnt1 = 0, cnt2 = 0; 121 for (int i = 0; i < n; ++i) { 122 if (i & 1) { 123 cnt2 += a[i] == '0'; 124 cnt1 += b[i] == '0'; 125 } else { 126 cnt1 += a[i] == '0'; 127 cnt2 += b[i] == '0'; 128 } 129 } 130 cout << (cnt1 >= (n + 1) / 2 && cnt2 >= n / 2 ? "Yes" : "No") << '\n'; 131 } 132 133 signed main() { 134 ios_base::sync_with_stdio(false); 135 cin.tie(nullptr); 136 cout.tie(nullptr); 137 int t; cin >> t; 138 while (t--) solve(); 139 } 140 ``` 141 142 **Code (Python)** 143 144 ``` 145 t = int(input()) 146 147 for test in range(t): 148 n = int(input()) 149 a = input() 150 b = input() 151 cnt1, cnt2 = 0, 0 152 for i in range(n): 153 if i % 2: 154 cnt2 += (a[i] == '0') 155 cnt1 += (b[i] == '0') 156 else: 157 cnt1 += (a[i] == '0') 158 cnt2 += (b[i] == '0') 159 160 if cnt1 >= (n + 1) // 2 and cnt2 >= n // 2: 161 print("Yes") 162 else: 163 print("No") 164 ``` 165 166 **Rate the problem** 167 168 * Amazing problem: 169 * Good problem: 170 * Average problem: 171 * Bad problem: 172 * Didn't solve: 173 174 ## [2092C - Asuna and the Mosquitoes](/contest/2092/problem/C "Codeforces Round 1014 (Div. 2)") 175 176 Author: [sergeev.PRO](/profile/sergeev.PRO "Master sergeev.PRO") 177 178 **Hint 1** 179 180 Consider two cases: first, when all numbers have the same parity; and second, when there is at least one even and one odd number. 181 182 **Hint 2** 183 184 Let $S$ be the sum of all numbers, and $k$ be the number of odd numbers in the array. Then, in the second case, the answer is $S - k + 1$. 185 186 **Solution** 187 188 **Case 1.** All numbers in $a$ have the same parity. In this case, it is impossible to perform any operation, so the answer is $\max(a)$. 189 190 **Case 2.** There is at least one even and one odd number. Let $S$ be the sum of all numbers, and $k$ be the number of odd numbers in the array. We will now prove that the answer is $S - k + 1$. 191 192 First of all, the answer cannot exceed $S - k + 1$, since the number of odd elements in the array remains unchanged after performing the operation. 193 194 Secondly, we will show that $S - k + 1$ is always achievable. Consider an arbitrary odd number $A \in a$. We can then *merge* all even numbers into $A$ $\left( \text{i.e.} \ (A, 2k) \to (A + 2k, 0) \right)$, resulting in an array consisting of the number $A + 2m$, $k-1$ odd numbers, and zeros for the remaining elements (here $2m$ denotes the sum of all even numbers in the initial array). 195 196 After this step, for each remaining odd number, we can *sacrifice* one unit by transferring it to any zero element in the array and then merge the resulting even number into $A$. It's easy to see that there will always be at least one zero available in the array before merging each odd number. Eventually, we will obtain an array consisting of one element equal to $S - k + 1$, $k - 1$ elements equal to one, and zeros filling the remaining positions. 197 198 Therefore, the answer in this case will be $S-k+1$. 199 200 **Code (C++)** 201 202 ``` 203 #include <algorithm> 204 #include <iostream> 205 #include <vector> 206 207 using namespace std; 208 209 void solve() { 210 int n; cin >> n; 211 vector <int> a(n); 212 long long ans = 0, cnt = 0; 213 for (int i = 0; i < n; ++i) { 214 cin >> a[i]; 215 ans += a[i]; cnt += (a[i] & 1); 216 } 217 if (!cnt || cnt == n) { 218 cout << *max_element(a.begin(), a.end()) << '\n'; 219 } else { 220 cout << ans - cnt + 1 << '\n'; 221 } 222 } 223 224 signed main() { 225 ios_base::sync_with_stdio(false); 226 cin.tie(nullptr); 227 cout.tie(nullptr); 228 int t; cin >> t; 229 while (t--) solve(); 230 } 231 ``` 232 233 **Code (Python)** 234 235 ``` 236 t = int(input()) 237 238 for test in range(t): 239 n = int(input()) 240 a = [int(i) for i in input().split()] 241 ans, cnt = 0, 0 242 for i in a: 243 ans += i 244 cnt += i % 2 245 246 if not cnt or cnt == n: 247 print(max(a)) 248 else: 249 print(ans - cnt + 1) 250 ``` 251 252 **Rate the problem** 253 254 * Amazing problem: 255 * Good problem: 256 * Average problem: 257 * Bad problem: 258 * Didn't solve: 259 260 ## [2092D - Mishkin Energizer](/contest/2092/problem/D "Codeforces Round 1014 (Div. 2)") 261 262 Author: [k1sara](/profile/k1sara "Grandmaster k1sara") 263 264 **Hint** 265 266 It is impossible to balance the string if and only if all its letters are the same. 267 268 **Solution 1** 269 270 It is clear that there is no solution if all the letters in $s$ are the same. Let us now prove that a solution always exists in all other cases. 271 272 While the string remains unbalanced, let us assume that $\text{cnt}(a) \le \text{cnt}(b) \le \text{cnt}(c)$, where $a, b, c \in \lbrace \tt{L}, \tt{I}, \tt{T} \rbrace$, and $\text{cnt}(l)$ denotes the number of occurrences of the letter $l$ in $s$. Consider two cases: 273 274 1. The string $s$ contains the substring `bc` or `cb`. In this case, we can perform the operation on it to obtain `bac` or `cab`. 275 2. Otherwise, the string $s$ must contain the substring `ca` or `ac`. Without loss of generality, assume that $s$ contains `ca`. Then we can perform the following sequence of operations: `ca` $\to$ `cba` $\to$ `cbca` $\to$ `cbaca` $\to$ `cabaca`. 276 277 It can be observed that after each operation, the value of $2 \cdot \text{cnt}(c) - \text{cnt}(b) - \text{cnt}(a)$ decreases by one. Here, $a$, $b$, and $c$ are always chosen such that $\text{cnt}(a) \le \text{cnt}(b) \le \text{cnt}(c)$. Therefore, the algorithm is guaranteed to terminate, and it does so when $2 \cdot \text{cnt}(c) - \text{cnt}(b) - \text{cnt}(a) = 0$, which implies $\text{cnt}(a) = \text{cnt}(b) = \text{cnt}(c)$. 278 279 It remains to prove that the number of operations performed by the proposed algorithm does not exceed $2n$. 280 281 **Proof** 282 283 Assume that initially $x = \text{cnt}(a), y = \text{cnt}(b), z = \text{cnt}(c)$, where $\text{cnt}(a) \le \text{cnt}(b) \le \text{cnt}(c)$. Then $x + y + z = n$. 284 285 While $\text{cnt}(a) \lt \text{cnt}(b)$, we increment $\text{cnt}(a)$ by one in each step, using no more than $4$ operations per step. Therefore, this phase requires at most $4(y - x)$ operations. 286 287 Afterwards, the algorithm alternately increments $\text{cnt}(a)$ and $\text{cnt}(b)$ by one until both become equal to $\text{cnt}(c)$. I claim that this phase will use the $4$-operations sequence (i.e., the second case in the algorithm) at most once. Indeed, let us consider the first time we perform the transformation `ca` $\to$ `cabaca`. It is easy to see that all subsequent steps will involve only single-operation transformations. Thus, this phase requires no more than $2(z - y) + 3$ operations. 288 289 Summing up, the total number of operations is bounded above by $4(y - x) + 2(z - y) + 3 = 2z + 2y - 4x + 3$. If $x \neq 0$, this number is less than $2n$ given that $n = x + y + z$. Otherwise, the first step of the algorithm will be either `bc` $\to$ `bac` or `cb` $\to$ `cab`, requiring only one operation. This improves the estimate for the number of operations in the first phase from $4(y-x)$ to $4(y - x) - 3$. As a result, in the case where $x = 0$, the total number of operations does not exceed $4(y - x) - 3 + 2(z-y) + 3 = 2z + 2y = 2n$. 290 291 **Code 1 (C++)** 292 293 ``` 294 #include <algorithm> 295 #include <iostream> 296 #include <vector> 297 298 using namespace std; 299 300 signed main() { 301 ios_base::sync_with_stdio(false); 302 cin.tie(nullptr); 303 cout.tie(nullptr); 304 string base = "LIT"; 305 int t; cin >> t; 306 while (t--) { 307 int n; string s; 308 cin >> n >> s; 309 if (count(s.begin(), s.end(), s[0]) == n) { 310 cout << -1 << '\n'; 311 } else { 312 vector <int> ans; 313 while (true) { 314 vector <pair<int, char>> cnt; 315 for (auto i : base) cnt.push_back(make_pair(count(s.begin(), s.end(), i), i)); 316 sort(cnt.begin(), cnt.end()); 317 if (cnt[0].first == cnt[1].first && cnt[1].first == cnt[2].first) break; 318 319 auto op = [&] (int i) -> void { 320 string z = base; z.erase(find(z.begin(), z.end(), s[i])); z.erase(find(z.begin(), z.end(), s[i + 1])); 321 ans.push_back(i); 322 s = s.substr(0, i + 1) + z[0] + s.substr(i + 1); 323 }; 324 325 bool done = false; 326 for (int i = 0; i < s.size() - 1; ++i) { 327 if (s[i] == s[i + 1]) continue; 328 if (s[i] != cnt[0].second && s[i + 1] != cnt[0].second) { 329 op(i); 330 done = true; 331 break; 332 } 333 } 334 335 if (done) continue; 336 337 for (int i = 0; i < s.size() - 1; ++i) { 338 if (s[i] == s[i + 1]) continue; 339 if (s[i] == cnt[2].second) { 340 op(i); op(i + 1); op(i); op(i + 2); break; 341 } else if (s[i + 1] == cnt[2].second) { 342 op(i); op(i); op(i + 1); op(i + 3); break; 343 } 344 } 345 } 346 347 cout << ans.size() << '\n'; 348 for (auto i : ans) cout << i + 1 << '\n'; 349 } 350 } 351 } 352 ``` 353 354 **Solution 2** 355 356 We assume that a solution exists (refer to the beginning of the first solution). Now, at each step, let's greedily find the first position where the rarest letter can be inserted and place it there. If no such position exists during a given iteration, we insert the most frequent letter instead. The algorithm terminates when all letters occur the same number of times. We claim that this greedy strategy performs no more than $2n$ operations. 357 358 Assume that initially $x = \text{cnt}(a), y = \text{cnt}(b), z = \text{cnt}(c)$, where $\text{cnt}(a) \le \text{cnt}(b) \le \text{cnt}(c)$. Then $x + y + z = n$. Here, $\text{cnt}(l)$ denotes the number of occurrences of the letter $l$ in $s$. 359 360 **Claim 1.** If the rarest letter cannot be inserted, there always exists a position where the most frequent letter can be inserted. 361 362 **Proof** 363 364 Suppose not. Then every pair of distinct adjacent letters must contain both `a` and `c`. This would imply that the number of `b`s is zero, which contradicts the condition $y \ge x$. 365 366 **Claim 2.** If $x = y$, the solution can always be obtained in exactly $(z - x) + (z - y) = 2z - x - y$ operations. 367 368 **Proof** 369 370 Let's find the first position $i$ such that $s_i \ne s_{i+1}$ and either $s_i$ or $s_{i+1}$ is `c`. Without loss of generality, assume the substring is of the form `cb...`. Then, the algorithm performs the following sequence of operations: 371 372 `cb...` $\to$ `cab...` $\to$ `cbab...` $\to$ `cabab` $\to$ $\dots$ $\to$ `cbababab...` 373 374 Since every two iterations increase the counts of both `a` and `b` by one, we will reach a count of $z$ in exactly the required number of steps. 375 376 Now consider the case when $x \lt y$. Observe that in two operations, the algorithm increases the count of the rarest letter by one and increases the count of the most frequent letter by **at most** one. This is true because, after inserting the most frequent letter, we obtain a substring like `bc`. It is easy to see that `a` can be inserted into it, and the algorithm, being greedy, will do exactly that. 377 378 After some number of iterations, $x$ becomes equal to $y$ (note that $y$ remains unchanged throughout the algorithm). Then, by the reasoning above, the final value of $z' = \text{cnt}(c)$ satisfies: 379 380 $z' \le z + (y - x)$ 381 382 Applying *Claim 2*, we get that the total number of operations does not exceed 383 384 $((z + (y - x)) - y) + ((z + (y - x)) - x) = 2z + y - 3x \le 2n$ 385 386 **Code 2 (C++)** 387 388 ``` 389 #include <vector> 390 #include <string> 391 #include <iostream> 392 #include <set> 393 #include <map> 394 using namespace std; 395 396 vector<char> a = {'L', 'I', 'T'}; 397 398 int main() { 399 int t; cin >> t; 400 while (t--) { 401 int n; cin >> n; 402 string s; cin >> s; 403 set<char> se; 404 for (auto u : s) se.insert(u); 405 if (se.size() == 1) { 406 cout << -1 << endl; 407 continue; 408 } 409 vector<int> ans; 410 map<char, int> mp; 411 for (auto u : s) { 412 mp[u]++; 413 } 414 auto func = [&](int i) { 415 for (auto u : a) { 416 if (s[i] != u && s[i + 1] != u) return u; 417 } 418 return '$'; 419 }; 420 while (max({mp['L'], mp['I'], mp['T']}) != min({mp['L'], mp['I'], mp['T']})) { 421 int mn = min({mp['L'], mp['I'], mp['T']}); 422 int mx = max({mp['L'], mp['I'], mp['T']}); 423 int ok = 0; 424 for (int i = 0; i < s.size() - 1; i++) { 425 char x = func(i); 426 if (s[i] != s[i + 1] && mp[x] == mn) { 427 mp[x]++; 428 ok = 1; 429 s.insert(s.begin() + i + 1, x); 430 ans.push_back(i); 431 break; 432 } 433 } 434 if (!ok) { 435 for (int i = 0; i < s.size() - 1; i++) { 436 char x = func(i); 437 if (s[i] != s[i + 1] && mp[x] == mx) { 438 mp[x]++; 439 s.insert(s.begin() + i + 1, x); 440 ans.push_back(i); 441 ok = 1; 442 break; 443 } 444 } 445 } 446 } 447 cout << ans.size() << endl; 448 for (auto u : ans) { 449 cout << u + 1 << endl; 450 } 451 } 452 } 453 ``` 454 455 **Rate the problem** 456 457 * Amazing problem: 458 * Good problem: 459 * Average problem: 460 * Bad problem: 461 * Didn't solve: 462 463 ## [2092E - She knows...](/contest/2092/problem/E "Codeforces Round 1014 (Div. 2)") 464 465 Author: [k1sara](/profile/k1sara "Grandmaster k1sara") 466 467 **Hint** 468 469 If a cell has an even number of neighbours, does its color matter? 470 471 **Solution** 472 473 Let $S$ be the set of cells that have an odd number of neighbouring cells. It is easy to observe that $S$ consists of border cells, excluding the corner ones. More precisely, 474 475 $S = \{(i, j) \ \vert \ \left( i \in \{1, n\} \right) \ \bigoplus \ \left( j \in \{1, m\} \right) = 1 \} $ 476 477 **Idea 1.** I claim that the number of adjacent **border** cell pairs with different colors is even. Indeed, if we *walk* along the border—which essentially forms a cycle—starting and ending at $(1, 1)$, we must change color an even number of times. 478 479 **Idea 2.** It can be observed that the parity of $|A|$ does not change when flipping the color of any cell not in $S$, since such a cell has an even number of neighbouring cells. Therefore, if we fix the coloring of the border cells, the parity of $|A|$ remains unchanged if we imagine recoloring all non-border cells white. This implies that the parity of $|A|$ depends solely on the parity of the number of black (or white) cells in $S$. Moreover, it can be seen that these parities are actually equal. 480 481 **Idea 3.** Now, we are left with counting the number of colorings such that $|S|$ contains an even number of black cells. Let's consider two cases: 482 483 1. All cells in $S$ are initially colored. In this case, the answer is $2^{n \cdot m - k}$ if the number of black cells in $S$ is even, and $0$ otherwise, since the colors of the remaining cells do not affect the parity. 484 2. At least one cell in $S$ is uncolored. In this case, the answer is $2^{n \cdot m - k - 1}$. This follows from the basic identity of the binomial coefficients: 485 486 $C^0_n + C^2_n + C^4_n + \dots = C^1_n + C^3_n + C^5_n + \dots$ 487 488 **Code (C++)** 489 490 ``` 491 #include <iostream> 492 #include <vector> 493 494 using namespace std; 495 496 using ll = long long; 497 const ll mod = 1000000007; 498 499 ll binpow (ll a, ll n) { 500 ll res = 1; 501 while (n) { 502 if (n & 1) { 503 res *= a; res %= mod; 504 } 505 a *= a; a %= mod; n >>= 1; 506 } 507 return res; 508 } 509 510 void solve() { 511 ll n, m, k; cin >> n >> m >> k; 512 int good = 0, sum = 0; 513 for (int i = 0; i < k; ++i) { 514 int x, y, c; cin >> x >> y >> c; 515 if ((x == 1 && y == 1) || (x == 1 && y == m) || (x == n && y == 1) || (x == n && y == m)) continue; 516 if (x == 1 || y == 1 || x == n || y == m) { 517 ++good; sum += c; 518 } 519 } 520 if (good == 2 * (n + m - 4)) { 521 cout << (sum % 2 ? 0 : binpow(2, n * m - k)) << '\n'; 522 } else { 523 cout << binpow(2, n * m - k - 1) << '\n'; 524 } 525 } 526 527 signed main() { 528 ios_base::sync_with_stdio(false); 529 cin.tie(nullptr); 530 cout.tie(nullptr); 531 int t; cin >> t; 532 while (t--) solve(); 533 } 534 ``` 535 536 **Rate the problem** 537 538 * Amazing problem: 539 * Good problem: 540 * Average problem: 541 * Bad problem: 542 * Didn't solve: 543 544 ## [2092F - Andryusha and CCB](/contest/2092/problem/F "Codeforces Round 1014 (Div. 2)") 545 546 Author: [k1sara](/profile/k1sara "Grandmaster k1sara") 547 548 **Hint 1** 549 550 It is sufficient to consider only two types of blocks of consecutive `0`s and `1`s: those of size $1$ and those of size greater than $1$. 551 552 **Hint 2** 553 554 For a fixed beauty value $m$ of a substring, there are $O\left(\frac{sz}{m}\right)$ possible values of $k$, where $sz$ is the number of blocks of consecutive `0`s and `1`s. 555 556 **Hint 3** 557 558 For a fixed pair $(m, k)$, let $S$ be the set of indices $i$ such that it is possible to divide the prefix $[1, i]$ of the string into $k$ substrings of beauty $m$. It is claimed that $S$ forms a continuous segment $[l, r]$ for some $1 \le l \le r \le sz$. 559 560 **Solution** 561 562 First, note that it is sufficient to consider only two types of blocks of consecutive `0`s and `1`s: those of size $1$ and those of size greater than $1$. Based on this, we construct a new string of length $sz$, consisting of characters `1` and `2`, representing the types of blocks. For example, for the original string `00101110`, the new string is `21121`. 563 564 Let’s fix a value of $m$—the desired beauty of the substrings we are dividing the string into. It is easy to see that there are $O\left(\frac{sz}{m}\right)$ possible values of $k$ (the number of substrings). 565 566 Now, for a fixed pair $(m, k)$, let $S_k$ be the set of indices $i$ such that it is possible to divide the prefix $[1, i]$ of the new string (representing block types) into $k$ substrings of beauty $m$. It is claimed that $S_k$ forms a continuous segment $[l, r]$ for some $1 \le l \le r \le sz$. Let’s prove this by induction. 567 568 **Base case ($k = 1$).** We set $l = m$, $r = m$ (0-based indexing). 569 570 **Inductive step ($k \rightarrow k + 1$).** Suppose that for every index $i \in [l, r]$, the first $i$ blocks can be divided into $k$ substrings of beauty $m$. Then we can construct a valid division into $k+1$ substrings by: 571 572 * Simply appending a new substring of length $m+1$ starting at block $i+1$, giving us a new upper bound at $i + m + 1$. 573 * Additionally, if block $i$ is of type $2$, we can split it between the $k$-th and $(k+1)$-th substrings, allowing us to finish the $k$-th substring earlier and start the $(k+1)$-th within the same block. This enables us to reach $i + m$ as well. 574 575 Thus, we conclude: 576 577 * $S_{k+1} = [l + m, r + m + 1]$ if the $l$-th block is of type 2. 578 * Otherwise, $S_{k+1} = [l + m + 1, r + m + 1]$. 579 580 To compute the full solution, we iterate over all values of $m$ from $1$ to $sz - 1$. For each $m$, we iterate over $k$ until the left bound $l$ of the corresponding segment exceeds $sz$. The special case $m=0$ should be handled separately. 581 582 For each $k$, we need to increment the answer for all positions from $l$ to $r$ by one. This can be efficiently done by recording the operations $(l, +1)$ and $(r + 1, -1)$ and then applying a scanline technique to process the accumulated changes. 583 584 Since there are $O\left(\frac{sz}{m}\right)$ possible values of $k$ for each $m$, the total complexity of this solution is $O(n \log n)$. 585 586 **Code (C++)** 587 588 ``` 589 #include <iostream> 590 #include <vector> 591 592 using namespace std; 593 594 using ll = long long; 595 596 void solve() { 597 int n; cin >> n; 598 string s; cin >> s; 599 vector <int> a; 600 int curr = 0; 601 for (int i = 0; i < n; ++i) { 602 if (i && s[i] != s[i - 1]) { 603 if (curr) a.push_back(curr); 604 curr = 1; 605 } 606 else ++curr; 607 } 608 a.push_back(curr); 609 int sz = a.size(); 610 611 vector <int> ans(n, 0), left(sz, 0), right(sz, 0); 612 for (int i = 0; i < sz; ++i) { 613 if (!i) { 614 left[i] = 0; right[i] = a[i] - 1; 615 } else { 616 left[i] = right[i - 1] + 1; 617 right[i] = left[i] + a[i] - 1; 618 } 619 } 620 for (int i = 0; i < sz; ++i) { 621 for (int j = left[i]; j <= right[i]; ++j) { 622 ans[j] += j - i + 1; 623 } 624 } 625 vector <int> add(sz, 0); 626 for (int m = 1; m < sz; ++m) { 627 ll l = m, r = m, k = 1; 628 while (l < sz) { 629 ++add[l]; 630 if (r + 1 < sz) --add[r + 1]; 631 632 if (a[l] == 1) { 633 l += m + 1; 634 } else { 635 l += m; 636 } 637 638 r += m + 1; 639 ++k; 640 } 641 } 642 int pref = 0; 643 for (int i = 0; i < sz; ++i) { 644 pref += add[i]; 645 for (int j = left[i]; j <= right[i]; ++j) { 646 ans[j] += pref; 647 } 648 } 649 for (int i = 0; i < n; ++i) { 650 cout << ans[i]; 651 if (i != n - 1) cout << ' '; 652 } 653 cout << '\n'; 654 } 655 656 signed main() { 657 ios_base::sync_with_stdio(false); 658 cin.tie(nullptr); 659 cout.tie(nullptr); 660 int t; cin >> t; 661 while (t--) { 662 solve(); 663 } 664 } 665 ``` 666 667 **Rate the problem** 668 669 * Amazing problem: 670 * Good problem: 671 * Average problem: 672 * Bad problem: 673 * Didn't solve: