codeforces-scrape

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

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: