2053.md (56890B)
1 Source: https://codeforces.com/blog/entry/136455 2 3 Thank you for participating in this round! Problems A and G are authored by [Cocoly1990](/profile/Cocoly1990 "Grandmaster Cocoly1990") and the rest by me. 4 5 Currently, I'm not sure if the editorials are fine enough. Please feel free to tell me where I can improve. 6 7 **Rating Predictions** 8 9 | | A | B | C | D | E | F | G | H | I | 10 | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | 11 | [_istil](/profile/_istil "International Grandmaster _istil") | 800 | 1200 | 1400 | 1700 | 1900 | 2500 | [2800, 3300] | 3200 | [800, 3000] | 12 | [Cocoly1990](/profile/Cocoly1990 "Grandmaster Cocoly1990") | 800 | 1300 | | | | | 3000 | | | 13 | [TheScrasse](/profile/TheScrasse "International Grandmaster TheScrasse") | 800 | 1200 | ? | 1800 | | 2500 | 3000 | 3000 | 3500 | 14 | [LMydd0225](/profile/LMydd0225 "International Grandmaster LMydd0225") | 800 | 1300 | 1600 | 1900 | 2100 | 2400 | 2800 | 2900 | [2500, 3200] | 15 | [Error_Yuan](/profile/Error_Yuan "Grandmaster Error_Yuan") | 900 | 1200 | 1400 | 2000 | 2100 | 2500 | 3000 | | 3200 | 16 | [Caylex](/profile/Caylex "International Master Caylex") | 800 | 1300 | 1500 | 1900 | 2200 | 2600 | [2500, 3100] | | | 17 | [tzl_Dedicatus545](/profile/tzl_Dedicatus545 "Master tzl_Dedicatus545") | 800 | 1000 | 1100 | 1400 | | 2300 | | | | 18 | [PaciukZvichainyi](/profile/PaciukZvichainyi "Candidate Master PaciukZvichainyi") | 800 | 1200 | 1500 | 1800 | 2100 | 2500 | | | | 19 | [doujinshi_master](/profile/doujinshi_master "Candidate Master doujinshi_master") | 800 | 1200 | 1500 | 1800 | | | | | | 20 | [juan_123](/profile/juan_123 "International Master juan_123") | 800 | [800, 1100] | 1000 | 1700 | | 2400 | 2800 | | [2700, 3500] | 21 | [StarSilk](/profile/StarSilk "Legendary Grandmaster StarSilk") | 800 | 1300 | 1400 | 1700 | | 2500 | 3100 | 2700 | | 22 | [SkyWave2022](/profile/SkyWave2022 "Specialist SkyWave2022") | 800 | 1200 | 1600 | [1600, 1900] | | | | | | 23 | [fossil823656](/profile/fossil823656 "Master fossil823656") | 800 | 1200 | 1500 | 1800 | 2100 | | | | | 24 | [FFTotoro](/profile/FFTotoro "Candidate Master FFTotoro") | 800 | 1200 | 1400 | 1900 | 1900 | 2400 | 2900 | | 25 26 [2053A - Tender Carpenter](/contest/2053/problem/A "Good Bye 2024: 2025 is NEAR") 27 28 **Hint 1** 29 30 Can you find a partition that is always valid? 31 32 **Hint 2** 33 34 Suppose you are given a set $S$. How do you judge whether $S$ is *stable* in $\mathcal O(\lvert S\rvert)$? 35 36 **Hint 3** 37 38 Are sets that are very large really necessary? 39 40 **Solution** 41 42 Note that: we always have a partition like $[a_1], [a_2], \dots, [a_n]$, since $(x, x, x)$ always forms a non-degenerate (equilateral) triangle. 43 44 We focus on the second partition scheme in which not all continuous subsegments have a length of $1$. One can also note that if a set $S$ is *stable* then for all $T \subsetneq S$ ($T \neq \varnothing$), $T$ is also *stable*. 45 46 * Short proof: If $\exists u, v, w \in T$ such that $(u, v, w)$ doesn't form a non-degenerate triangle, therefore $u, v, w \in S$ so it is concluded that $S$ is not *stable*. Contradiction! 47 48 If such a partition exists, we can always split long continuous subsegments into shorter parts, while the partition remains valid. Therefore, it's enough to check the case in which there is one subsegment of length $2$ and the rest of length $1$. So, we should output `NO` if and only if for all $1 \leq i \lt n$, $2\min(a_i, a_{i+1}) \leq \max(a_i, a_{i+1})$. 49 50 **Code (C++)** 51 52 ``` 53 #include <bits/stdc++.h> 54 55 #define MAXN 1001 56 int a[MAXN]; 57 void solve() { 58 int n; std::cin >> n; 59 for (int i = 1; i <= n; ++i) std::cin >> a[i]; 60 for (int i = 1; i < n; ++i) if (2 * std::min(a[i], a[i + 1]) > std::max(a[i], a[i + 1])) 61 { std::cout << "YES\n"; return; } 62 std::cout << "NO\n"; 63 } 64 65 int main() { 66 std::ios::sync_with_stdio(false); 67 std::cin.tie(nullptr), std::cout.tie(nullptr); 68 int t; std::cin >> t; while (t--) solve(); return 0; 69 } 70 ``` 71 72 **Rate the Problem** 73 74 * Amazing problem: 75 * Good problem: 76 * Average problem: 77 * Bad problem: 78 * Didn't solve: 79 80 [2053B - Outstanding Impressionist](/contest/2053/problem/B "Good Bye 2024: 2025 is NEAR") 81 82 **Hint 1** 83 84 What if for all $1 \leq i \leq n$, $l_i \ne r_i$ holds? How do you prove it? 85 86 **Hint 2** 87 88 Use prefix sums or similar to optimize your solution. 89 90 **Solution** 91 92 For each $1 \leq i \leq n$, for each $l_i \leq x \leq r_i$, we want to check if it is okay for impression $i$ being *unique* at the value of $x$. Note that: for each $j \neq i$, we can always switch $w_j$ to a value different from $x$ if $l_j \neq r_j$, since there are at least two options. Therefore, it is impossible if and only if there exists a $1 \leq j \leq n$ with $j \neq i$ such that $l_j = r_j = x$. 93 94 Let's record $a_i$ as the number of different $k$ satisfying $1 \leq k \leq n$ and $l_k = r_k = i$. If $l_i \neq r_i$, then we say impression $i$ **cannot** be made *unique* if and only if for all $l_i \leq k \leq r_i$, $a_k \geq 1$; otherwise ($l_i = r_i$), it cannot be *unique* if and only if $a_{l_i} \geq 2$. 95 96 This can all be checked quickly within a prefix sum, so the overall time complexity is $\mathcal O(\sum n)$. 97 98 **Code (C++)** 99 100 ``` 101 #include <bits/stdc++.h> 102 103 #define MAXN 400001 104 int l[MAXN], r[MAXN], sum[MAXN], cnt[MAXN]; 105 void solve() { 106 int n; std::cin >> n; 107 for (int i = 1; i <= 2 * n; ++i) sum[i] = cnt[i] = 0; 108 for (int i = 1; i <= n; ++i) { 109 std::cin >> l[i] >> r[i]; 110 if (l[i] == r[i]) sum[l[i]] = 1, ++cnt[l[i]]; 111 } 112 for (int i = 2; i <= 2 * n; ++i) sum[i] += sum[i - 1]; 113 for (int i = 1; i <= n; ++i) 114 std::cout << ((l[i] == r[i] ? cnt[l[i]] <= 1 : sum[r[i]] - sum[l[i] - 1] < r[i] - l[i] + 1) ? "1" : "0"); 115 std::cout << '\n'; 116 } 117 int main() { 118 std::ios::sync_with_stdio(false); 119 std::cin.tie(nullptr), std::cout.tie(nullptr); 120 int t; std::cin >> t; while (t--) solve(); return 0; 121 } 122 ``` 123 124 **Rate the Problem** 125 126 * Amazing problem: 127 * Good problem: 128 * Average problem: 129 * Bad problem: 130 * Didn't solve: 131 132 [2053C - Bewitching Stargazer](/contest/2053/problem/C "Good Bye 2024: 2025 is NEAR") 133 134 **Hint 1** 135 136 Process many segments simultaneously. What kind of segments do we process at a time? 137 138 **Hint 2** 139 140 The length. 141 142 **Solution** 143 144 The point that must be noted is: that if we call the process of splitting a large segment into two smaller segments a round, then all segments are of the same length when the $i$-th round of the observation is conducted; and, the number of rounds does not exceed $\mathcal O(\log n)$. The $k$ restriction is equivalent to specifying that only a certain prefix of rounds is computed. 145 146 Here are some different approaches: 147 148 * (Most succinctly) Note that the distribution of segments after round 1 is centrally symmetric; Also, $x$ and $y$ being centrally symmetric implies that $x + y = n + 1$, so it is simple to calculate by simulating the number of segments and the length directly. 149 * If a segment $[l, r]$ is split into $[l, m - 1]$ and $[m + 1, r]$, its left endpoint sum changes from $l$ to $2l + \frac{r - l}{2} + 1$, and since $(r - l)$ is fixed, the sum of the left endpoints of all segments can be maintained similarly. 150 * The following recursive method also works: the answer to $n$ can be recovered by the answer to $\lfloor \frac{n}{2} \rfloor$. The time complexity is $\mathcal O(t\log n)$. 151 152 **Code (C++)** 153 154 This is written by [_TernaryTree_](/profile/_TernaryTree_ "Candidate Master _TernaryTree_"). 155 156 ``` 157 #include <bits/stdc++.h> 158 #define int long long 159 160 using namespace std; 161 162 int T; 163 int n, k; 164 165 signed main() { 166 cin >> T; 167 while (T--) { 168 cin >> n >> k; 169 int mul = n + 1, sum = 0, cur = 1; 170 while (n >= k) { 171 if (n & 1) sum += cur; 172 n >>= 1; 173 cur <<= 1; 174 } 175 cout << mul * sum / 2 << endl; 176 } 177 return 0; 178 } 179 ``` 180 181 **Rate the Problem** 182 183 * Amazing problem: 184 * Good problem: 185 * Average problem: 186 * Bad problem: 187 * Didn't solve: 188 189 [2053D - Refined Product Optimality](/contest/2053/problem/D "Good Bye 2024: 2025 is NEAR") 190 191 **Hint 1** 192 193 What if $q = 0$? 194 195 **Hint 2** 196 197 How do you keep the array sorted? 198 199 **Solution** 200 201 The problem makes no difference when both $a$ and $b$ can be rearranged. Let the rearranged arrays of $a$ and $b$ be $c$ and $d$ respectively. 202 203 If $q = 0$, we can write $c$ as $\operatorname{SORTED}(a_1, a_2 \ldots, a_n)$ and $d$ as $\operatorname{SORTED}(b_1, b_2 \ldots, b_n)$. It can be proved that this reaches the maximum value: if not so, then 204 205 * There must be some pair $(i, j)$ such that $c_i \lt c_j, d_i \gt d_j$. 206 * Since $\min(c_i, d_i) \cdot \min(c_j, d_j) = c_i \cdot \min(c_j, d_j) \leq c_i \cdot \min(c_j, d_i) = \min(c_i, d_j) \cdot \min(c_j, d_i)$, we can swap $d_i$ and $d_j$, and the product does not decrease. 207 208 Consider the modification, which is a single element increment by $1$. Without loss of generality, let $c_x$ be increased by $1$ (and the processing method for $d$ is the same). If $c_x \lt c_{x+1}$, then after the modification $c_x \leq c_{x+1}$, which would be fine. Otherwise, we can modify the array $c$ in the form of a single round of "Insertion Sort": We continuously swap $c_x$ and $c_{x+1}$, $x \gets x + 1$, until $c_x \lt c_{x+1}$ (or $x = n$), and thus the array remains sorted after the increment. 209 210 In fact, the swap operation does nothing in the above process: in these cases, $c_x = c_{x+1}$ holds! So we can just set $x'$ as the maximum $k$ such that $c_k = c_x$, and then increase $c_{x'}$ by $1$, after which $c$ is still sorted. The $k$ can be found with a naive binary search, so the problem is solved in $\mathcal O(n\log n + q(\log p + \log n))$ per test case. 211 212 **Code (C++)** 213 214 ``` 215 #include <bits/stdc++.h> 216 217 constexpr int MOD = 998244353; 218 int qpow(int a, int x = MOD - 2) { 219 int res = 1; 220 for (; x; x >>= 1, a = 1ll * a * a % MOD) if (x & 1) res = 1ll * res * a % MOD; 221 return res; 222 } 223 224 #define MAXN 200001 225 int a[MAXN], b[MAXN], c[MAXN], d[MAXN]; 226 void solve() { 227 int n, q, res = 1; std::cin >> n >> q; 228 for (int i = 1; i <= n; ++i) std::cin >> a[i], c[i] = a[i]; 229 for (int i = 1; i <= n; ++i) std::cin >> b[i], d[i] = b[i]; 230 std::sort(c + 1, c + n + 1), std::sort(d + 1, d + n + 1); 231 for (int i = 1; i <= n; ++i) res = 1ll * res * std::min(c[i], d[i]) % MOD; 232 std::cout << res << " \n"[q == 0]; 233 for (int i = 1, op, x; i <= q; ++i) { 234 std::cin >> op >> x; 235 if (op == 1) { 236 int p = std::upper_bound(c + 1, c + n + 1, a[x]) - c - 1; 237 if (c[p] < d[p]) res = 1ll * res * qpow(c[p]) % MOD * (c[p] + 1) % MOD; 238 ++a[x], ++c[p]; 239 } else { 240 int p = std::upper_bound(d + 1, d + n + 1, b[x]) - d - 1; 241 if (d[p] < c[p]) res = 1ll * res * qpow(d[p]) % MOD * (d[p] + 1) % MOD; 242 ++b[x], ++d[p]; 243 } 244 std::cout << res << " \n"[i == q]; 245 } 246 } 247 248 int main() { 249 std::ios::sync_with_stdio(false); 250 std::cin.tie(nullptr), std::cout.tie(nullptr); 251 int t; std::cin >> t; while (t--) solve(); return 0; 252 } 253 ``` 254 255 **Rate the Problem** 256 257 * Amazing problem: 258 * Good problem: 259 * Average problem: 260 * Bad problem: 261 * Didn't solve: 262 263 [2053E - Resourceful Caterpillar Sequence](/contest/2053/problem/E "Good Bye 2024: 2025 is NEAR") 264 265 **Hint 1** 266 267 Suppose somebody wins. In which round does he or she win? 268 269 **Hint 2** 270 271 A player can always undo what his opponent did in the previous turn. 272 273 **Hint 3** 274 275 Can you find the necessary and sufficient condition for $(p, q)$ to be a caterpillar that makes Aron win? 276 277 **Solution** 278 279 Denote Nora's first move as round $1$, Aron's first move as round $2$, and so on. Suppose a player does not have a winning strategy in the $k$-th round, but he or she has a winning strategy in the $(k + 2)$-th round — it can be shown impossible because the other player can always withdraw the last move of another player so that the status is the same as it was before the $k$-th round. 280 281 Therefore: if a player wins in the $k$-th round, we claim that $k \leq 2$. 282 283 Given $p, q$, let's determine who will eventually win the game. 284 285 1. If both $p$ and $q$ are leaves, the result is a tie. 286 2. If $p$ is a leaf while $q$ is not, Nora wins. 287 3. If $q$ is a leaf while $p$ is not, Aron wins. 288 4. If neither $p$ nor $q$ is a leaf: 289 * Can $k = 1$? Nora wins if and only if $p$ is adjacent to a leaf. 290 * Can $k = 2$? Aron wins if and only if $p$ is not adjacent to a leaf, and $f(p, q)$ is adjacent to a leaf. 291 * Otherwise, the result is a tie. 292 293 The counting part can also be solved easily in $\mathcal O(n)$. Denote $c$ as the number of leaves. The initial answer would be $c \cdot (n - c)$, considering the third case. For the fourth case, we can enumerate $m = f(p, q)$, which is adjacent to at least one leaf. Given $m$, $q$ must be a non-leaf neighbor of $m$, and let the number of different $q$ be $k$. For each of the potential $p$, which is a non-leaf node whose neighbors are all non-leaf nodes too, it is computed exactly $k - 1$ times for all the $k$ candidates of $q$ (since $m$ must be on the simple path from $p$ to $q$), so the extra contributions are easy to calculate. (If you do not think that much, you can use some simple DP, which I will not elaborate here.) 294 295 **Code (C++)** 296 297 ``` 298 #include <bits/stdc++.h> 299 300 #define MAXN 200001 301 std::vector<int> g[MAXN]; 302 inline int deg(int u) { return g[u].size(); } 303 304 int d[MAXN]; 305 void solve() { 306 int n; std::cin >> n; long long ans = 0; 307 for (int i = 1, u, v; i < n; ++i) { 308 std::cin >> u >> v; 309 g[u].push_back(v), g[v].push_back(u); 310 } 311 int c1 = 0, c2 = 0; 312 for (int i = 1; i <= n; ++i) c1 += (deg(i) == 1); 313 ans += 1ll * c1 * (n - c1); 314 for (int i = 1; i <= n; ++i) if (deg(i) > 1) { 315 for (int v : g[i]) d[i] += (deg(v) > 1); 316 c2 += (d[i] == deg(i)); 317 } 318 for (int m = 1; m <= n; ++m) if (deg(m) > 1 && d[m] != deg(m)) 319 ans += 1ll * c2 * (d[m] - 1); 320 std::cout << ans << '\n'; 321 for (int i = 1; i <= n; ++i) 322 (std::vector<int>()).swap(g[i]), d[i] = 0; 323 } 324 325 int main() { 326 std::ios::sync_with_stdio(false); 327 std::cin.tie(nullptr), std::cout.tie(nullptr); 328 int t; std::cin >> t; while (t--) solve(); return 0; 329 } 330 ``` 331 332 **Rate the Problem** 333 334 * Amazing problem: 335 * Good problem: 336 * Average problem: 337 * Bad problem: 338 * Didn't solve: 339 340 [2053F - Earnest Matrix Complement](/contest/2053/problem/F "Good Bye 2024: 2025 is NEAR") 341 342 Special thanks to [LMydd0225](/profile/LMydd0225 "International Grandmaster LMydd0225") for implementing a correct MCS ~~ahead of me~~, and [Error_Yuan](/profile/Error_Yuan "Grandmaster Error_Yuan") for generating the test data for this problem. 343 344 **Hint 1** 345 346 What are we going to fill into the matrix? In other words, is there any relationship between the filed numbers? 347 348 **Hint 2** 349 350 Try to come up with a naive DP solution that works in large time complexity, such as $\mathcal O(nk^2)$. 351 352 **Hint 3** 353 354 For many different numbers between two consecutive rows, however, the transition is almost the same. 355 356 **Hint 4** 357 358 If $x' = \max(a, x + b)$ and $x'' = \max(c, x' + d)$, then $x'' = \max(\max(a + d, c), x + b + d)$. 359 360 **Solution** 361 362 > **Conclusion**: For each row, an optimal solution exists, such that the newly filled-in numbers are the same. 363 364 * **Proof**: Consider fixing the rows $i - 1$ and $i + 1$, and observe all the newly filled-in numbers at row $i$. Then a new number $u$ brings a contribution of $c_{u, i-1} + c_{u, i+1}$, and it is clear that there exists a scheme that takes the maximum value such that all the $u$ filled in are equal. Adjusting for each row leads to the above conclusion. 365 366 Consider dp. Let $f_{i,j}$ denote the maximum contribution that can be achieved between the first $i$ rows **(ignoring the initial contribution)** when the empty elements in the $i$-th row are filled with $j$. Let $c_i$ be the number of $-1$ numbers in the $i$-th row, and $d_{i,j}$ denote the number of elements $j$ in the $i$-th row initially. 367 368 The transfer should be as follows: 369 370 $f_{i, j} = \max(\max\limits_{1 \leq w \leq k}(f_{i-1, w} + c_i \cdot d_{i-1, w} + c_{i-1} \cdot d_{i-1, j}), f_{i-1, j} + (d_{i, j} + c_i) \cdot (d_{i-1, j} + c_{i-1}) - d_{i, j}d_{i-1, j}).$ 371 372 In addition to being able to optimize the above transition to $\mathcal O(nk)$, the present problem in a matrix has a good property. Specifically, for the same $i$, there are only $\mathcal O(m)$ values of $j$ such that $d_{i,j} \neq 0$! 373 374 If $d_{i,j} = 0$ and $d_{i-1, j} = 0$, the original transfer can be viewed as 375 376 $f_{i,j} = \max(\max\limits_{1 \leq w \leq k}(f_{i-1, w}), f_{i-1, j} + c_i \cdot c_{i-1}).$ 377 378 This can be seen as a global modification in the form of $x \gets \max(a, x + b)$. The tags are composable in $\mathcal O(1)$; Otherwise, we can brutely update the new $dp_j$ for $\mathcal O(m)$ positions. 379 380 Therefore, this problem is solved in $\mathcal O(nm)$. We decided to let every segment tree solution pass comfortably, so that we set small constraints and large TL. 381 382 Bonus Hint for implementation: always use $\max(a, dp_j + b)$ to get the real value. 383 384 **Code (C++)** 385 386 ``` 387 #include <bits/stdc++.h> 388 389 namespace FastIO { 390 char buf[1 << 21], *p1 = buf, *p2 = buf; 391 #define getchar() (p1 == p2 && (p1 = buf, p2 = (p1 + fread(buf, 1, 1 << 21, stdin))) == p1 ? EOF : *p1++) 392 template <typename T> inline T read() { T x = 0, w = 0; char ch = getchar(); while (ch < '0' || ch > '9') w |= (ch == '-'), ch = getchar(); while ('0' <= ch && ch <= '9') x = x * 10 + (ch ^ '0'), ch = getchar(); return w ? -x : x; } 393 template <typename T> inline void write(T x) { if (!x) return; write<T>(x / 10), putchar((x % 10) ^ '0'); } 394 template <typename T> inline void print(T x) { if (x > 0) write<T>(x); else if (x < 0) putchar('-'), write<T>(-x); else putchar('0'); } 395 template <typename T> inline void print(T x, char en) { print<T>(x), putchar(en); } 396 #undef getchar 397 }; using namespace FastIO; 398 399 using ll = long long; 400 void solve() { 401 int n = read<int>(), m = read<int>(), k = read<int>(); ll cntP = 0, cntQ = 0; 402 std::vector<int> vep(m), veq(m), cntp(k + 1), cntq(k + 1), vis(k + 1); 403 std::vector<ll> dp(k + 1); ll a = 0, b = 0, v = 0, ext = 0; // max(a, x + b). 404 cntp[0] = cntq[0] = m; 405 auto get = [&](int x) -> int { return (~x) ? x : 0; }; 406 auto read_q = [&]() -> void { 407 for (int i = 0; i < m; ++i) --cntq[get(veq[i])]; 408 for (int i = 0; i < m; ++i) ++cntq[get(veq[i] = read<int>())]; 409 cntQ = cntq[0]; 410 }; 411 auto roll = [&]() -> void { std::swap(vep, veq), std::swap(cntp, cntq), std::swap(cntP, cntQ); }; 412 auto chkmax = [&](ll &a, ll b) -> void { a = std::max(a, b); }; 413 read_q(), roll(); 414 for (int i = 2; i <= n; ++i) { 415 read_q(); 416 ll max_dp = std::max(a, v + b); 417 for (int k : vep) if (~k) chkmax(max_dp, std::max(a, dp[k] + b) + cntP * cntq[k]); 418 for (int k : veq) if (~k) chkmax(max_dp, std::max(a, dp[k] + b) + cntP * cntq[k]); 419 for (int k : vep) if ((~k) && vis[k] != i) { 420 vis[k] = i, ext += 1ll * cntp[k] * cntq[k]; 421 dp[k] = std::max(a, dp[k] + b) + cntP * cntq[k] + cntQ * cntp[k] - b; 422 chkmax(dp[k], max_dp + cntp[k] * cntQ - b - cntP * cntQ); 423 chkmax(v, dp[k]); 424 } for (int k : veq) if ((~k) && vis[k] != i) { 425 vis[k] = i; 426 dp[k] = std::max(a, dp[k] + b) + cntP * cntq[k] + cntQ * cntp[k] - b; 427 chkmax(dp[k], max_dp + cntp[k] * cntQ - b - cntP * cntQ); 428 chkmax(v, dp[k]); 429 } a = std::max(max_dp, a + cntP * cntQ), b += cntP * cntQ; 430 roll(); 431 } print<ll>(std::max(a, v + b) + ext, '\n'); 432 } 433 434 int main() { int T = read<int>(); while (T--) solve(); return 0; } 435 ``` 436 437 **Rate the Problem** 438 439 * Amazing problem: 440 * Good problem: 441 * Average problem: 442 * Bad problem: 443 * Didn't solve: 444 445 [2053G - Naive String Splits](/contest/2053/problem/G "Good Bye 2024: 2025 is NEAR") 446 447 Special thanks to [LMydd0225](/profile/LMydd0225 "International Grandmaster LMydd0225") for generating the test data for this problem, and [TheScrasse](/profile/TheScrasse "International Grandmaster TheScrasse") for providing an alternative solution. 448 449 And thanks to [Caylex](/profile/Caylex "International Master Caylex") for implementing a really correct MCS and rewriting the editorial, and [crazy_sea](/profile/crazy_sea "International Grandmaster crazy_sea") for offering a suggestion. 450 451 **Hint 1** 452 453 (If we do not have to be deterministic) We do not need any hard string algorithm. 454 455 **Hint 2** 456 457 In what cases won't greed work? Why? 458 459 **Hint 3** 460 461 Is your brute forces actually faster (maybe you can explain it by harmonic series)? 462 463 **Solution** 464 465 Let's call the prefix $s_1$ the short string and the suffix $s_2$ the long string. If $\lvert s_1\rvert\gt \lvert s_2\rvert$, swapping the order doesn't affect the answer. 466 467 Consider a greedy approach. We first match a few short strings until we can't match anymore. If we can't match, we try discarding a few short strings and placing one long string. We enumerate how many short strings to discard. **Find the first position where we can place a long string.** We call this placing once a "matching process." The starting position of each "matching process" is the next position after the previous "matching process." 468 469 However, this approach has a flaw. Below, I will explain the situation where this flaw occurs. 470 471 **Why it has a flaw** 472 473 It's not difficult to view the long string as several short strings concatenated with a "tail" at the end. 474 475 Why only find the first position? Why wouldn't it be better to backtrack and discard a few more $s_1$'s before placing the long string? 476 477  478 479 The diagram above is an example. The red line indicates the cutoff position for matching $s_1$. The three orange boxes represent the possible choices for attempting to match the long string. 480 481 The last one is invalid, so skip it. Replace it with the "The first valid position to place the long string." box. This box is correct. 482 483 The difference between choosing the second box and the first box is that when we end the matching and proceed to the next round, the content we need to match is that a suffix of $s_1$ has been moved to the beginning of $s_1$。 484 485 As shown in the diagram. 486 487  488 489 The alignment results in the following diagram. 490 491  492 493 In the diagram, the case where $\lvert pre\rvert \gt \lvert suf\rvert$ is shown. The other case follows similarly. 494 495 $pre+suf=suf+pre$, and as can be seen from the diagram, here $pre+suf$ needs to be "misaligned but equal." This means that $s_1$ must have a periodic cycle, and the "tail" must also be able to be formed through this cycle. Additionally, the $\lvert s_1 \rvert$ characters at the beginning of $s_2$ must still be able to be formed by the periodic cycle. 496 497 In summary, it is equivalent to $s_1$ and $s_2$ having a **common periodic cycle**. 498 499 In other words, **backtracking twice can lead to a solution, but backtracking once may not always work**. It is necessary for $s_1$ and $s_2$ to have a common periodic cycle. 500 501 Having a common periodic cycle is too specific. First, the common periodic cycle of these two strings must indeed be the periodic cycle of string $s$. By finding this cycle in advance, it essentially becomes a problem of solving an equation. Let $a=\lvert s_1\rvert $ and $b=\lvert s_2\rvert$, and we need to check whether there are non-negative integer solutions $x$ and $y$ that satisfy the equation $xa+yb=\lvert s \rvert$. 502 503 This equation-solving part is just for show. We enumerate $y$, and for each value of $y$, we compute the enumeration $\mathcal O\left(\frac{m}{n}\right)$ times. At most, we do this $n$ times, so the overall complexity is $\mathcal O(m)$. 504 505 If we directly implement this, the worst-case complexity is related to the harmonic series. Consider a case like $s_1 = \texttt{a}, s_2 = \texttt{aaaaaaaab}$, and $t = \texttt{aaaaaaaaaaaaaaaaaaaaaaaaab}$. In this case, we would need to attempt $\mathcal O\left(\frac{m}{\lvert s_1\rvert }\right)$ steps to finish matching the short string. Each time we backtrack, it requires at most $\mathcal O\left(\frac{m}{\lvert s_2\rvert }\right)$ steps, and each of those takes $\mathcal O\left(\frac{\lvert s_2\rvert }{\lvert s_1\rvert }\right)$. 506 507 **Optimization to Linear** 508 509 Thanks to [zhoukangyang](/profile/zhoukangyang "Legendary Grandmaster zhoukangyang") and [crazy_sea](/profile/crazy_sea "International Grandmaster crazy_sea") for pointing out it! 510 511 Yes, this problem can indeed be solved in linear time. 512 513 First, let the prefix of the long string contain $c$ short strings. Then, the first "valid position to place the long string" we backtrack to can only be obtained by either backtracking $c$ short strings or $c+1$ short strings. 514 515 This is easy to understand. Backtracking $c$ short strings means considering the prefix of the long string, then adding the "tail" of the long string. Backtracking $c + 1$ short strings only happens when the "tail" part of the long string is a prefix of the short string. For example, the hack in the CF comment section: 516 517 <https://codeforces.com/blog/entry/136455?#comment-1234262> 518 519 ``` 520 1 521 8 8 522 abaabaab 523 abaababa 524 ``` 525 526 The correct output should be: 527 528 ``` 529 0010000 530 ``` 531 532 When $k = 3$, $s_1 = \texttt{aba}$, $s_2 = \texttt{abaab}$, we first filled in 2 short strings, but if we backtrack $c = 1$ short string, it will be judged as unsolvable. This is how the error in std occurs. This situation only arises when the "tail" part of $s_2$ is a prefix of $s_1$. 533 534 So, each time we calculate, we first use binary search to find this $c$, and the complexity is $\mathcal O\left(\sum\limits_{i=1}^n\log(\frac n i)\right)=\mathcal O(n)$. After that, backtracking only requires two checks. The backtracking process becomes linear. 535 536 Next, let's accelerate the process of filling in short strings. The hack for brute-force filling has already been given above. If we directly use the method that everyone initially thought was correct, which is the "binary search for the number of short string occurrences" method, Then it can be accelerated by this set of hacks to achieve a $\log$ complexity. 537 538 ``` 539 1 540 2 5000000 541 ab 542 abababab....abababab 543 ``` 544 545 [crazy_sea](/profile/crazy_sea "International Grandmaster crazy_sea") points out an alternative solution. 546 547 Similar to block division, let $B = \frac{n}{\lvert s_1\rvert}$. We first try to match $B$ occurrences of $s_1$, meaning that each match can move forward by $n$ positions. After that, the remaining part will not exceed $B$ occurrences, and we binary search to find how many are left. For the part where we moved forward by $B$ occurrences, we can backtrack at most once, and then the binary search will take $\mathcal O(\log B)$. Each time, we can at least fill in $\lvert s_2\rvert $ occurrences. The time complexity for calculating the answer becomes $\mathcal O\left(\frac{m}{\lvert s_2\rvert }\log B\right)$, and the total complexity, due to $\mathcal O\left(\sum\limits_{i=1}^n \log(\frac{n}{i})\right) = \mathcal O(n)$, is $\mathcal O(m)$. 548 549 Thus, the problem is solved in linear time. 550 551 **...wtf?** 552 553 During testing, we found that [EvenImage](/profile/EvenImage "Legendary Grandmaster EvenImage")'s solution is actually more violent than we thought (We have also received something similar in contest). 554 555 He specially handled the case in which $X$ and $T$ share a common shortest period, and for the rest $i$, he just used two queues to optimize the BFS progress (actually changing it to `std::priority_queue<int>` or similar also works), and it passed just seeming to have a larger constant time complexity. 556 557 I'm curious if anybody can (hack it or) prove that it is correct. Thanks in advance! 558 559 **Code (log, C++)** 560 561 This is written by [Caylex](/profile/Caylex "International Master Caylex"). 562 563 ``` 564 #include <bits/stdc++.h> 565 using namespace std; 566 template <int P> 567 class mod_int 568 { 569 using Z = mod_int; 570 571 private: 572 static int mo(int x) { return x < 0 ? x + P : x; } 573 574 public: 575 int x; 576 int val() const { return x; } 577 mod_int() : x(0) {} 578 template <class T> 579 mod_int(const T &x_) : x(x_ >= 0 && x_ < P ? static_cast<int>(x_) : mo(static_cast<int>(x_ % P))) {} 580 bool operator==(const Z &rhs) const { return x == rhs.x; } 581 bool operator!=(const Z &rhs) const { return x != rhs.x; } 582 Z operator-() const { return Z(x ? P - x : 0); } 583 Z pow(long long k) const 584 { 585 Z res = 1, t = *this; 586 while (k) 587 { 588 if (k & 1) 589 res *= t; 590 if (k >>= 1) 591 t *= t; 592 } 593 return res; 594 } 595 Z &operator++() 596 { 597 x < P - 1 ? ++x : x = 0; 598 return *this; 599 } 600 Z &operator--() 601 { 602 x ? --x : x = P - 1; 603 return *this; 604 } 605 Z operator++(int) 606 { 607 Z ret = x; 608 x < P - 1 ? ++x : x = 0; 609 return ret; 610 } 611 Z operator--(int) 612 { 613 Z ret = x; 614 x ? --x : x = P - 1; 615 return ret; 616 } 617 Z inv() const { return pow(P - 2); } 618 Z &operator+=(const Z &rhs) 619 { 620 (x += rhs.x) >= P && (x -= P); 621 return *this; 622 } 623 Z &operator-=(const Z &rhs) 624 { 625 (x -= rhs.x) < 0 && (x += P); 626 return *this; 627 } 628 Z operator-() { return -x; } 629 Z &operator*=(const Z &rhs) 630 { 631 x = 1ULL * x * rhs.x % P; 632 return *this; 633 } 634 Z &operator/=(const Z &rhs) { return *this *= rhs.inv(); } 635 #define setO(T, o) \ 636 friend T operator o(const Z &lhs, const Z &rhs) \ 637 { \ 638 Z res = lhs; \ 639 return res o## = rhs; \ 640 } 641 setO(Z, +) setO(Z, -) setO(Z, *) setO(Z, /) 642 #undef setO 643 friend istream & 644 operator>>(istream &is, mod_int &x) 645 { 646 long long tmp; 647 is >> tmp; 648 x = tmp; 649 return is; 650 } 651 friend ostream &operator<<(ostream &os, const mod_int &x) 652 { 653 os << x.val(); 654 return os; 655 } 656 }; 657 typedef long long ll; 658 typedef unsigned long long ull; 659 mt19937 rnd(chrono::system_clock::now().time_since_epoch().count()); 660 constexpr int p = 993244853; 661 using Hash = mod_int<p>; 662 // using Hash = ull; 663 const Hash base = rnd() % 20091119 + 30; 664 string s, t; 665 Hash st; 666 int mnlen; 667 Hash S[5000020]; 668 Hash T[5000020]; 669 Hash pw[5000020]; 670 inline Hash SUM(const int l, const int r, const Hash *s) { return s[r] - s[l - 1] * pw[r - l + 1]; } 671 int n, m; 672 inline bool check(const int l, const int r, const Hash x, const int len, const Hash *S) { return r - l + 1 >= len && SUM(l, l + len - 1, S) == x && SUM(l, r - len, S) == SUM(l + len, r, S); } 673 inline bool calc(const int L1, const int R1, const int L2, const int R2, const int l1, const int l2) 674 { 675 if (mnlen && check(L1, R1, st, mnlen, S) && check(L2, R2, st, mnlen, S)) 676 { 677 if (check(1, m, st, mnlen, T)) 678 { 679 for (int i = 0; i <= m; i += l2) 680 { 681 if (!((m - i) % l1)) 682 return 1; 683 } 684 return 0; 685 } 686 } 687 const Hash s1 = SUM(L1, R1, S); 688 const Hash s2 = SUM(L2, R2, S); 689 // int l = 1, r = l2 / l1, okcnt = 0; 690 // while (l <= r) 691 // { 692 // int mid = l + r >> 1; 693 // if (check(L2, L2 + mid * l1 - 1, s1, l1, S)) 694 // l = (okcnt = mid) + 1; 695 // else 696 // r = mid - 1; 697 // } 698 int ed = 0; 699 while (ed <= m) 700 { 701 int L = 1, R = (m - ed) / l1, cnt = 0; 702 while (L <= R) 703 { 704 int mid = L + R >> 1; 705 if (check(ed + 1, ed + mid * l1, s1, l1, T)) 706 L = (cnt = mid) + 1; 707 else 708 R = mid - 1; 709 } 710 if (ed + cnt * l1 + 1 > m) 711 return 1; 712 // bool found = 0; 713 // int st = ed + (cnt - okcnt) * l1 + 1; 714 // if (st > ed && st + l2 - 1 <= m && SUM(st, st + l2 - 1, T) == s2) 715 // { 716 // ed = st + l2 - 1; 717 // found = 1; 718 // } 719 // if (!found) 720 // return 0; 721 bool found = 0; 722 for (int st = ed + cnt * l1 + 1; st > ed; st -= l1) 723 { 724 if (st + l2 - 1 <= m && SUM(st, st + l2 - 1, T) == s2) 725 { 726 ed = st + l2 - 1; 727 found = 1; 728 break; 729 } 730 } 731 if (!found) 732 return 0; 733 } 734 return 1; 735 } 736 void solve() 737 { 738 // build(); 739 mnlen = 0; 740 cin >> n >> m >> s >> t; 741 s = ' ' + s; 742 t = ' ' + t; 743 for (int i = 1; i <= n; i++) 744 S[i] = S[i - 1] * base + Hash(s[i] - 'a' + 1); 745 for (int i = 1; i <= m; i++) 746 T[i] = T[i - 1] * base + Hash(t[i] - 'a' + 1); 747 for (int i = 1; i <= n; i++) 748 { 749 if (n % i == 0 && check(1, n, S[i], i, S)) 750 { 751 st = S[i]; 752 mnlen = i; 753 break; 754 } 755 } 756 for (int i = 1; i < n; i++) 757 putchar('0' ^ (i <= n - i ? calc(1, i, i + 1, n, i, n - i) : calc(i + 1, n, 1, i, n - i, i))); 758 putchar('\n'); 759 } 760 int main() 761 { 762 pw[0] = Hash(1); 763 for (int i = 1; i <= 5'000'000; i++) 764 pw[i] = pw[i - 1] * base; 765 ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); 766 int t; 767 cin >> t; 768 while (t--) 769 solve(); 770 return 0; 771 } 772 ``` 773 774 **Code (linear, C++)** 775 776 This is written by [Caylex](/profile/Caylex "International Master Caylex"). 777 778 ``` 779 #include <bits/stdc++.h> 780 using namespace std; 781 template <int P> 782 class mod_int 783 { 784 using Z = mod_int; 785 786 private: 787 static int mo(int x) { return x < 0 ? x + P : x; } 788 789 public: 790 int x; 791 int val() const { return x; } 792 mod_int() : x(0) {} 793 template <class T> 794 mod_int(const T &x_) : x(x_ >= 0 && x_ < P ? static_cast<int>(x_) : mo(static_cast<int>(x_ % P))) {} 795 bool operator==(const Z &rhs) const { return x == rhs.x; } 796 bool operator!=(const Z &rhs) const { return x != rhs.x; } 797 Z operator-() const { return Z(x ? P - x : 0); } 798 Z pow(long long k) const 799 { 800 Z res = 1, t = *this; 801 while (k) 802 { 803 if (k & 1) 804 res *= t; 805 if (k >>= 1) 806 t *= t; 807 } 808 return res; 809 } 810 Z &operator++() 811 { 812 x < P - 1 ? ++x : x = 0; 813 return *this; 814 } 815 Z &operator--() 816 { 817 x ? --x : x = P - 1; 818 return *this; 819 } 820 Z operator++(int) 821 { 822 Z ret = x; 823 x < P - 1 ? ++x : x = 0; 824 return ret; 825 } 826 Z operator--(int) 827 { 828 Z ret = x; 829 x ? --x : x = P - 1; 830 return ret; 831 } 832 Z inv() const { return pow(P - 2); } 833 Z &operator+=(const Z &rhs) 834 { 835 (x += rhs.x) >= P && (x -= P); 836 return *this; 837 } 838 Z &operator-=(const Z &rhs) 839 { 840 (x -= rhs.x) < 0 && (x += P); 841 return *this; 842 } 843 Z operator-() { return -x; } 844 Z &operator*=(const Z &rhs) 845 { 846 x = 1ULL * x * rhs.x % P; 847 return *this; 848 } 849 Z &operator/=(const Z &rhs) { return *this *= rhs.inv(); } 850 #define setO(T, o) \ 851 friend T operator o(const Z &lhs, const Z &rhs) \ 852 { \ 853 Z res = lhs; \ 854 return res o## = rhs; \ 855 } 856 setO(Z, +) setO(Z, -) setO(Z, *) setO(Z, /) 857 #undef setO 858 friend istream & 859 operator>>(istream &is, mod_int &x) 860 { 861 long long tmp; 862 is >> tmp; 863 x = tmp; 864 return is; 865 } 866 friend ostream &operator<<(ostream &os, const mod_int &x) 867 { 868 os << x.val(); 869 return os; 870 } 871 }; 872 typedef long long ll; 873 typedef unsigned long long ull; 874 mt19937 rnd(chrono::system_clock::now().time_since_epoch().count()); 875 constexpr int p = 993244853; 876 using Hash = mod_int<p>; 877 // using Hash = ull; 878 const Hash base = rnd() % 20091119 + 30; 879 string s, t; 880 Hash st; 881 int mnlen; 882 Hash S[5000020]; 883 Hash T[5000020]; 884 Hash pw[5000020]; 885 // int doit; 886 inline Hash SUM(const int l, const int r, const Hash *s) { return s[r] - s[l - 1] * pw[r - l + 1]; } 887 int n, m; 888 inline bool check(const int l, const int r, const Hash x, const int len, const Hash *S) 889 { 890 // doit++; 891 return r - l + 1 >= len && SUM(l, l + len - 1, S) == x && SUM(l, r - len, S) == SUM(l + len, r, S); 892 } 893 inline bool calc(const int L1, const int R1, const int L2, const int R2, const int l1, const int l2) 894 { 895 if (mnlen && check(L1, R1, st, mnlen, S) && check(L2, R2, st, mnlen, S)) 896 { 897 if (check(1, m, st, mnlen, T)) 898 { 899 for (int i = 0; i <= m; i += l2) 900 { 901 if (!((m - i) % l1)) 902 return 1; 903 } 904 return 0; 905 } 906 } 907 const Hash s1 = SUM(L1, R1, S); 908 const Hash s2 = SUM(L2, R2, S); 909 int l = 1, r = l2 / l1, okcnt = 0; 910 while (l <= r) 911 { 912 int mid = l + r >> 1; 913 if (check(L2, L2 + mid * l1 - 1, s1, l1, S)) 914 l = (okcnt = mid) + 1; 915 else 916 r = mid - 1; 917 } 918 const int tt = (n / l1); 919 int ed = 0; 920 while (ed <= m) 921 { 922 int L = 1, R = (m - ed) / l1, cnt = 0; 923 int tcnt = 0; 924 while (tcnt + tt <= R && check(ed + 1, ed + (tcnt + tt) * l1, s1, l1, T)) 925 tcnt += tt; 926 L = max(L, tcnt); 927 R = min(R, tcnt + tt - 1); 928 // cerr << ed << ' ' << L << ' ' << R << '\n'; 929 while (L <= R) 930 { 931 int mid = L + R >> 1; 932 if (check(ed + 1, ed + mid * l1, s1, l1, T)) 933 L = (cnt = mid) + 1; 934 else 935 R = mid - 1; 936 } 937 if (ed + cnt * l1 + 1 > m) 938 return 1; 939 // int st = ed + (cnt - okcnt) * l1 + 1; 940 // if (st > ed && st + l2 - 1 <= m && SUM(st, st + l2 - 1, T) == s2) 941 // { 942 // ed = st + l2 - 1; 943 // continue; 944 // } 945 // return 0; 946 bool found = 0; 947 for (int st = ed + (cnt - okcnt) * l1 + 1, cnt = 1; cnt <= 2 && st > ed; st -= l1, cnt++) 948 { 949 if (st + l2 - 1 <= m && SUM(st, st + l2 - 1, T) == s2) 950 { 951 ed = st + l2 - 1; 952 found = 1; 953 break; 954 } 955 } 956 if (!found) 957 return 0; 958 } 959 return 1; 960 } 961 void solve() 962 { 963 // build(); 964 mnlen = 0; 965 cin >> n >> m >> s >> t; 966 s = ' ' + s; 967 t = ' ' + t; 968 for (int i = 1; i <= n; i++) 969 S[i] = S[i - 1] * base + Hash(s[i] - 'a' + 1); 970 for (int i = 1; i <= m; i++) 971 T[i] = T[i - 1] * base + Hash(t[i] - 'a' + 1); 972 for (int i = 1; i <= n; i++) 973 { 974 if (n % i == 0 && check(1, n, S[i], i, S)) 975 { 976 st = S[i]; 977 mnlen = i; 978 break; 979 } 980 } 981 for (int i = 1; i < n; i++) 982 putchar('0' ^ (i <= n - i ? calc(1, i, i + 1, n, i, n - i) : calc(i + 1, n, 1, i, n - i, i))); 983 putchar('\n'); 984 // cerr << doit << '\n'; 985 } 986 int main() 987 { 988 // freopen("out.txt", "r", stdin); 989 pw[0] = Hash(1); 990 for (int i = 1; i <= 5'000'000; i++) 991 pw[i] = pw[i - 1] * base; 992 ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); 993 int t; 994 cin >> t; 995 while (t--) 996 solve(); 997 // cerr << fixed << setprecision(10) << 1.0 * clock() / CLOCKS_PER_SEC << '\n'; 998 return 0; 999 } 1000 ``` 1001 1002 **Rate the Problem** 1003 1004 * Amazing problem: 1005 * Good problem: 1006 * Average problem: 1007 * Bad problem: 1008 * Didn't solve: 1009 1010 [2053H - Delicate Anti-monotonous Operations](/contest/2053/problem/H "Good Bye 2024: 2025 is NEAR") 1011 1012 Special thanks to [LMydd0225](/profile/LMydd0225 "International Grandmaster LMydd0225") and [N_z__](/profile/N_z__ "International Grandmaster N_z__") for developing this problem. 1013 1014 **Hint 1** 1015 1016 What if $w = 2$? Is it optimal to increase $\sum\limits_{i=0}^n [a_i \neq a_{i+1}]$ (suppose $a_0 = a_{n+1} = 2$)? 1017 1018 **Hint 2** 1019 1020 If $w \geq 3$, what's the answer to the first question? 1021 1022 **Hint 3** 1023 1024 If $a_i = a_{i+1}$, after the operation we can obtain $a_{i-1} = a_i$ or $a_{i+1} = a_{i+2}$ (and possibly, both). 1025 1026 **Hint 4** 1027 1028 Try to think of the whole process reversedly. If $w \geq 3$, $1 \leq a_i \leq w - 1$, can you solve the problem? 1029 1030 **Hint 5** 1031 1032 How many extra operations are required for each $1 \leq i \leq n$ if $a_i = w$, in the above scheme you use for $a_i \leq w - 1$? 1033 1034 **Solution** 1035 1036 Read the Hints. 1037 1038 * $w = 2$ 1039 1040 After any operation, $k = \sum\limits_{i=0}^n [a_i \neq a_{i+1}]$ won't decrease (suppose $a_0 = a_{n+1} = 2$). For a fixed $k$, the maximal $\sum a_i = 2n - \frac{1}{2}k$ and can be reached by each time turning a $[2, 1, 1]$ into $[2, 2, 1]$ (or symmetrically, $[1, 1, 2] \rightarrow [1, 2, 2]$. 1041 1042 * $w \geq 3$ 1043 + No initial operations can be conducted, or $\min(a_i) = w$ 1044 1045 This case is trivial. 1046 1047 * $w \geq 3$ 1048 + Some initial operations can be conducted 1049 1050 We claim that the answer to the first question is $nw - 1$. For the second question, let's study some rather easier cases below. 1051 1052 * $w \geq 3$ 1053 + Some initial operations can be conducted 1054 - $a_i \neq w$ 1055 1056 We pretend that the final sequence is $[w, w, \dots, w, (w-1), w, w, \dots, w]$, then since $(a_i, a_{i+1})$ must be different after the operation, the last operation can only occur on $[w, (w-1)]$ (or $[(w-1), w]$). And since initially $a_i \neq w$, each position must have been operated on at least once. 1057 1058 This gives us states such as $[w, \dots, w, x, x, w, \dots, w]$, $[w, \dots, w, y, y, x, w, \dots, w]$, etc. To the leftmost positions, we get $a_1 = a_2$ (essentially based on Hint 3). Also, we get ...... $a_{n-1} = a_n$? This is if and only if the initial $[w, (w - 1)]$ is neither at the beginning nor at the end. If the initial $[w, (w - 1)]$ is at the beginning, we only need $a_{n-1} = a_n$ to achieve the goal, and symmetrically the same. Less is more. Obviously, we only need to satisfy either $a_1 = a_2$ or $a_{n-1} = a_n$, and then use $n - 1$ more operations to reach the target situation. 1059 1060 How do we get to $a_1 = a_2$ (symmetrically the same)? Based on Hint 3, we find the smallest $x$ that satisfies $a_x = a_{x+1}$, and then follow the example above, again using $x - 1$ operations to conduct the equality sign to $a_1 = a_2$. 1061 1062 **Why is it optimal?** 1063 1064 > **Lemma 1**: We can never choose an index $a_i = w$, fix it (i.e. avoid changing $a_i$ in the following operations), and then use some operations to reach $\sum a_i = nw - 1$ unless $[a_1, \ldots, a_i] = [w, \ldots, w]$ or $[a_i, \ldots, a_n] = [w, \ldots, w]$. 1065 1066 **Proof**: If not so, the array is split into two parts: $[a_1, \ldots, a_{i-1}]$ and $[a_{i+1}, \ldots, a_n]$. We have: after some operations, the maximum $\sum a_i$ we can get for each part are respectively $(i-1)w - 1, (n-i)w - 1$, and add them up and we get $nw - 2$, which is less than $nw - 1$, so it's never optimal. 1067 1068 > **Lemma 2**: Look at the final array $a$, consisting of $n - 1$ element $w$ and $1$ element $(w - 1)$. Obtain an array $a'$ by keeping the elements with the value of $w$. Denote $t_i$ as the last round in which ${a'}_i$ was changed to $w$ (and then become fixed). Then, there exists some $k$ such that $t_1 \lt t_2 \lt \dots \lt t_k \gt t_{k+1} \gt \dots \gt t_{n-1}$. 1069 1070 **Proof**: This follows from **Lemma 1**. 1071 1072 According to **Lemma 2**, we can see the pattern that we used above is optimal. 1073 1074 * $w \geq 3$ 1075 + Some initial operations can be conducted 1076 - $a_1 \neq w, a_n \neq w$ 1077 1078 Basically, the idea remains to reach $a_1 = a_2$ in the same way first (symmetrically the same), and then to extend to all positions. However, at this point, in the second stage, some problems may arise as follows: 1079 1080 * $[\dots \underline{a_k}\ a_{k+1}\ w\ a_{k+3} \dots]$ 1081 * $[\dots \underline{\color{red}{a_{k+1}}\ a_{k+1}}\ w\ a_{k+3} \dots]$ 1082 * $[\dots \color{red}s\ \underline{\color{red}w\ w}\ a_{k+3} \dots]$ 1083 * $[\dots \color{red}{\underline{s\ s}}\ t\ a_{k+3} \dots]$ 1084 * $[\dots \color{red}w\ \underline{\color{red}t\ t}\ a_{k+3} \dots]$ 1085 * $[\dots \color{red}{w\ w}\ \underline{\color{red}{a_{k+3}}\ a_{k+3}} \dots]$ 1086 1087 In which $s, t, w$ are three distinct integers in the range $[1, w]$ (This also explains why we need to specially deal with the $w = 2$ case). Since we cannot fix $a_{k+2} = w$ at the beginning (refer to the "Why is it optimal?" spoiler above), we have to first change $a_{k+2}$ into something not equal to $w$, and that cost at least $2$ extra operations, which is shown here. 1088 1089 **Do we always need $2$ extra operations?** One may note that if $a_i = a_{i+1} = w$, in which the two elements are both in the way of expansion, we can only use $1$ operation to vanish their existence. Formally, if there is a maximum continuous subsegment of $w$ in the way of expansion, let its length be $L$, then we will spend $\lceil \frac{L}{2} \rceil + [L = 1]$ extra operations. 1090 1091 **What is 'in the way of expansion'?** 1092 1093 Suppose in the first stage, we pick $a_x = a_{x+1}$ and keep operating on it until $a_1 = a_2$. Then after it, $\forall 3 \leq k \leq x + 1$, $a_k$ can be an arbitrary number which is different from the initial $a_{k-1}$, thus we can always force it to be $\neq w$. 1094 1095 In the above case, only elements $[a_{x+2}, \ldots, a_n]$ are considered 'in the way of expansion', and symmetrically the same. 1096 1097 * $w \geq 3$ 1098 + Some initial operations can be conducted 1099 - No additional constraints 1100 1101 It may come to you that if $a_1 = w$, we can ignore $a_1$; if $a_1 = a_2 = w$, we can ignore $a_2$. Symmetrically the same. And so on... Then we boil the problem down to the case above. 1102 1103 It is correct unless in some rare cases when we ignore all the prefixes and suffixes, there will be no remaining $a_i = a_{i+1}$; or if we pick any pair $a_i = a_{i+1}$ as the starting pair in the remaining array, it is not optimal compared to picking an $a_k = a_{k+1} = w (a_{k+2} \neq w)$ (symmetrically the same). So, we have to special handle the deleted prefix and suffix, once it has a length greater than $2$. 1104 1105 In summary, the problem can be solved in $\mathcal O(n)$. 1106 1107 **Code (C++)** 1108 1109 ``` 1110 #include <bits/stdc++.h> 1111 1112 #define MAXN 200005 1113 int a[MAXN]; 1114 1115 void solve() { 1116 int N, w; scanf("%d%d", &N, &w); 1117 for (int i = 1; i <= N; ++i) scanf("%d", a + i); 1118 if (N == 1) return (void)printf("%d 0\n", a[1]); 1119 if (*std::min_element(a + 1, a + N + 1) == w) 1120 return (void)printf("%lld 0\n", 1ll * w * N); 1121 if (w == 2) { 1122 int ans = N * 2, pans = 0; 1123 for (int i = 1, j = 1; i <= N; i = ++j) if (a[i] == 1) { 1124 --ans; while (j < N && a[j + 1] == 1) ++j; pans += j - i; 1125 } 1126 return (void)printf("%d %d\n", ans, pans); 1127 } 1128 bool flag = true; 1129 for (int i = 1; i < N; ++i) if (a[i] == a[i + 1]) flag = false; 1130 if (flag) return (void)printf("%lld 0\n", std::accumulate(a + 1, a + N + 1, 0ll)); 1131 printf("%lld ", 1ll * w * N - 1); 1132 if (std::accumulate(a + 1, a + N + 1, 0ll) == 1ll * w * N - 1) return (void)puts("0"); 1133 int ans = 0x3f3f3f3f, l = (a[1] == w ? 2 : 1), r = (a[N] == w ? N - 1 : N); 1134 if ((a[1] == w && a[2] == w) || (a[N] == w && a[N - 1] == w)) { 1135 int Lw = 0, Rw = N + 1; 1136 while (a[Lw + 1] == w) ++Lw; while (a[Rw - 1] == w) --Rw; 1137 int pans = Rw - Lw; 1138 for (int i = Lw + 1, j = i; i < Rw; i = ++j) if (a[i] == w) { 1139 while (j + 1 < Rw && a[j + 1] == w) ++j; 1140 pans += (i == j ? 2 : ((j - i) >> 1) + 1); 1141 } 1142 ans = pans, l = Lw + 1, r = Rw - 1; 1143 } 1144 for (int d = 0; d < 2; std::reverse(a + l, a + r + 1), ++d) 1145 for (int i = l - 1, pre = 0, len = 0; i + 2 <= r; ) { 1146 if (a[i + 1] == a[i + 2]) 1147 ans = std::min(r - (i + 1) + r - l - 1 + pre - ((len == 1) && i + 2 < r && a[i + 3] != w ? 1 : 0), ans); 1148 ++i; if (a[i] == w) ++len, pre += (len == 1 ? 2 : len == 2 ? -1 : (len & 1)); else len = 0; 1149 } 1150 printf("%d\n", ans); 1151 } 1152 1153 int main() { int T; scanf("%d", &T); while (T--) solve(); return 0; } 1154 ``` 1155 1156 **Rate the Problem** 1157 1158 * Amazing problem: 1159 * Good problem: 1160 * Average problem: 1161 * Bad problem: 1162 * Didn't solve: 1163 1164 [2053I1 - Affectionate Arrays (Easy Version)](/contest/2053/problem/I1 "Good Bye 2024: 2025 is NEAR") 1165 1166 **Hint 1** 1167 1168 What is the minimized LIS? 1169 1170 **Hint 2** 1171 1172 How do you prove that it is an achievable lower bound? 1173 1174 **Hint 3** 1175 1176 Go for a brute DP first. 1177 1178 **Solution** 1179 1180 We claim that the minimized LIS is $\sum a_i$. Let $p$ be $\sum a_i$. 1181 1182 Since it is required that $\operatorname{LIS}(b) = p$ while $\sum b_i = p$, we point out that it is equivalent to **each of the prefix sums of the sequence being between $[0, p]$**. 1183 1184 * **Sufficiency**: $\forall X \in [0, p], Y \in [0, p]$, $X - Y \leq p$. Also, we can pick $X = p, Y = 0$, so it can only be $= p$. 1185 * **Necessity**: disproof. If a prefix sum is $ \lt 0$, then choose the whole array except for this prefix; if a prefix sum is $ \gt p$, then choose this prefix. Both derive a contradiction of the LIS being greater than $p$. 1186 1187 Consider dp. Let $f_{i,j}$ denote, after considering the first $i$ numbers, the minimum **extra** sequence length (i.e. the actual length minus $i$), when the current prefix sum is $j$. The initial states are $f_{0,j} = [j \neq 0]$. The transfer is simple too: 1188 1189 $f_{i,j} = \min\limits_{0 \leq k + a_i \leq p} (f_{i-1,k} + [k + a_i \neq j])$ 1190 1191 It is possible to optimize the transfer to $\mathcal O(np)$, since for each $j$, the contribution from at most one $k$ is special ($+0$). We can calculate the prefix and suffix $\min$ for $f_{i-1}$ and it will be fast to get the dp array in the new row. Then, let's focus on optimizing it to $\mathcal O(n)$. 1192 1193 We call the set of $0 \leq k \leq p$ satisfying $0 \leq k + a_i \leq p$ as the legal interval of $i$ (denoted as $L_i$). 1194 1195 It is concluded that the range of $f_{i, 0\dots p}$ is at most $1$, and this can be proven by considering the transfer to each of the $j$ with the $k \in L_i$ which has the least $f_{i-1, k}$. Let $v_i = \min_{0 \leq j \leq p}(f_{i, j})$. We also have: for those $j$ with $f_{i,j} = v_i$, they form a consecutive segment in the integer field. Let the segment be covering $[l_i, r_i]$. 1196 1197 Inductive proof. The essence of the transfer is that it shifts all the DP values $= v_{i-1}$ by $a_i$ unit length, and all the other numbers will be updated to $v_{i-1} + 1$. Then truncates the $j \in ((-\inf, 0) \cup (p, +\inf))$ part. The consecutive segment remains consecutive. Specially, if $[l_{i-1}, r_{i-1}] \cap L_i = \varnothing$, then $\min_{k \in L_i}(f_{i-1, k}) = v_{i-1} + 1$, hence we need to set $v_i = v_{i-1} + 1$, and $l_i, r_i$ as the range of $j = k + a_i$ in which $k \in L_i$. Otherwise, $v_i = v_{i-1}$, and $l_i, r_i$ can be calculated by shifting $l_{i-1}, r_{i-1}$ by $a_i$ unit length. 1198 1199 In fact, we only need to maintain three variables $l, r, v$ to represent the current consecutive segment and the current value field. Therefore, this problem can be easily solved in $\mathcal O(n)$. 1200 1201 **Code (C++)** 1202 1203 ``` 1204 #include <bits/stdc++.h> 1205 1206 namespace FastIO { 1207 template <typename T> inline T read() { T x = 0, w = 0; char ch = getchar(); while (ch < '0' || ch > '9') w |= (ch == '-'), ch = getchar(); while ('0' <= ch && ch <= '9') x = x * 10 + (ch ^ '0'), ch = getchar(); return w ? -x : x; } 1208 template <typename T> inline void write(T x) { if (!x) return; write<T>(x / 10), putchar((x % 10) ^ '0'); } 1209 template <typename T> inline void print(T x) { if (x > 0) write<T>(x); else if (x < 0) putchar('-'), write<T>(-x); else putchar('0'); } 1210 template <typename T> inline void print(T x, char en) { print<T>(x), putchar(en); } 1211 }; using namespace FastIO; 1212 1213 #define MAXN 3000001 1214 int a[MAXN]; 1215 void solve() { 1216 int N = read<int>(); long long p = 0, l = 0, r = 0, v = 0; 1217 for (int i = 1; i <= N; ++i) p += (a[i] = read<int>()); 1218 for (int i = 1; i <= N; ++i) if (a[i] >= 0) { 1219 l += a[i], r = std::min(r + a[i], p); 1220 if (l > r) ++v, l = a[i], r = p; 1221 } else { 1222 a[i] = -a[i]; 1223 r -= a[i], l = std::max(l - a[i], 0ll); 1224 if (l > r) ++v, l = 0, r = p - a[i]; 1225 } 1226 print<int>(v + N + (int)(r != p), '\n'); 1227 } 1228 int main() { int T = read<int>(); while (T--) solve(); return 0; } 1229 ``` 1230 1231 **Rate the Problem** 1232 1233 * Amazing problem: 1234 * Good problem: 1235 * Average problem: 1236 * Bad problem: 1237 * Didn't solve: 1238 1239 [2053I2 - Affectionate Arrays (Hard Version)](/contest/2053/problem/I2 "Good Bye 2024: 2025 is NEAR") 1240 1241 **Hint 1** 1242 1243 Try insert numbers into spaces between the elements of $a$ (including the beginning and the end). Note that an array be can be formed in multiple ways (for example, you can insert a number $x$ to the left or right of the original number $x$ in array $a$). What's the number of different ways? 1244 1245 **Answer** 1246 1247 It's actually the "value", that is, the number of occurrances of $a$. Use the fact that "only one number can be inserted into each space" to prove. 1248 1249 **Solution** 1250 1251 Read the editorial for I1 and the hints first. 1252 1253 According to the hint, you can count the number of ways to insert the new numbers into the space, so the dp and transitions are similar to those in problem I1. 1254 1255 We can add an additional dp array, $g_{i, j}$ representing the number of different ways when everything meets the description of $f_{i, j}$. Let's see from which values it can be transferred: 1256 1257 * If $f_{i, j} = v_i$, then $f_{i, j}$ can only be transferred from $f_{i-1, j-a_i}$. That is, $g_{i, j} = g_{i-1, j-a_i}$. 1258 * If $f_{i, j} = v_i + 1$, then $f_{i, j} = \sum_{k \in L_i, f_{i-1, k} = f_{i, j} - 1} g_{i-1, k}$. 1259 1260 We can use some tags and a Deque to maintain the whole process, so the amortized time complexity is $\mathcal O(n)$. 1261 1262 **Code (C++)** 1263 1264 ``` 1265 #include <bits/stdc++.h> 1266 1267 namespace FastIO { 1268 template <typename T> inline T read() { T x = 0, w = 0; char ch = getchar(); while (ch < '0' || ch > '9') w |= (ch == '-'), ch = getchar(); while ('0' <= ch && ch <= '9') x = x * 10 + (ch ^ '0'), ch = getchar(); return w ? -x : x; } 1269 template <typename T> inline void write(T x) { if (!x) return; write<T>(x / 10), putchar((x % 10) ^ '0'); } 1270 template <typename T> inline void print(T x) { if (x > 0) write<T>(x); else if (x < 0) putchar('-'), write<T>(-x); else putchar('0'); } 1271 template <typename T> inline void print(T x, char en) { print<T>(x), putchar(en); } 1272 }; using namespace FastIO; 1273 1274 const int MOD = 998244353; 1275 namespace Modint { 1276 inline int add(int x, int y) { return (x += y) >= MOD ? x - MOD : x; } 1277 inline int sub(int x, int y) { return x < y ? x - y + MOD : x - y; } 1278 inline int mul(int x, int y) { return 1ll * x * y % MOD; } 1279 inline int pow(int x, int y) { int r = 1; for (; y; y >>= 1, x = mul(x, x)) if (y & 1) r = mul(r, x); return r; } 1280 inline int inv(int x) { return pow(x, MOD - 2); } 1281 }; 1282 struct modint { 1283 int v; 1284 modint (int x = 0) : v(x) { /* for debug only. assert(0 <= x && x < MOD); */ } 1285 inline int get() { return v; } 1286 modint operator - () const { return v ? MOD - v : 0; } 1287 modint operator + (const modint &k) const { return Modint::add(v, k.v); } 1288 modint operator - (const modint &k) const { return Modint::sub(v, k.v); } 1289 modint operator * (const modint &k) const { return Modint::mul(v, k.v); } 1290 modint operator / (const modint &k) const { return Modint::mul(v, Modint::inv(k.v)); } 1291 modint pow(const modint &k) const { return Modint::pow(v, k.v); } 1292 modint inverse() const { return Modint::inv(v); } 1293 modint operator += (const modint &k) { (v += k.v) >= MOD && (v -= MOD); return *this; } 1294 modint operator -= (const modint &k) { (v -= k.v) < 0 && (v += MOD); return *this; } 1295 modint operator *= (const modint &k) { return v = Modint::mul(v, k.v); } 1296 modint operator /= (const modint &k) { return v = Modint::mul(v, Modint::inv(k.v)); } 1297 }; 1298 1299 struct Node { 1300 int f; modint g; long long len; 1301 Node () {} 1302 Node (int F, int G, long long L) : f(F), g(G), len(L) {} 1303 Node (int F, modint G, long long L) : f(F), g(G), len(L) {} 1304 }; std::deque<Node> Q; 1305 1306 #define MAXN 3000001 1307 int a[MAXN]; 1308 void solve() { 1309 int N = read<int>(); long long p = 0, l = 0, r = 0, v = 0; 1310 for (int i = 1; i <= N; ++i) p += (a[i] = read<int>()); 1311 for (int i = 1; i <= N; ++i) assert (std::abs(a[i]) <= p); 1312 Q.clear(); Q.push_back(Node(0, 1, 1)), Q.push_back(Node(1, 1, p)); 1313 modint gv = 1, gz = p % MOD, tv = 0, tz = 0; 1314 for (int i = 1; i <= N; ++i) if (a[i] >= 0) { 1315 for (long long ls = a[i]; ls > 0; ) { 1316 Node k = Q.back(); Q.pop_back(); 1317 if (ls < k.len) Q.push_back(Node(k.f, k.g, k.len - ls)), k.len = ls; 1318 (k.f == v ? gv : gz) -= k.g * (k.len % MOD), ls -= k.len; 1319 } 1320 l += a[i], r = std::min(r + a[i], p); 1321 if (l > r) ++v, l = a[i], r = p, gv = gz, tv = tz, gz = tz = 0; 1322 gz += -tz * (a[i] >= MOD ? a[i] - MOD : a[i]); 1323 if (a[i] > 0) Q.push_front(Node(v + 1, -tz, a[i])); 1324 tz += gv + tv * ((r - l + 1) % MOD); 1325 } else if (a[i] < 0) { 1326 a[i] = -a[i]; 1327 for (long long ls = a[i]; ls > 0; ) { 1328 Node k = Q.front(); Q.pop_front(); 1329 if (ls < k.len) Q.push_front(Node(k.f, k.g, k.len - ls)), k.len = ls; 1330 (k.f == v ? gv : gz) -= k.g * (k.len % MOD), ls -= k.len; 1331 } 1332 r -= a[i], l = std::max(l - a[i], 0ll); 1333 if (l > r) ++v, l = 0, r = p - a[i], gv = gz, tv = tz, gz = tz = 0; 1334 gz += -tz * (a[i] >= MOD ? a[i] - MOD : a[i]), Q.push_back(Node(v + 1, -tz, a[i])), tz += gv + tv * ((r - l + 1) % MOD); 1335 } 1336 print<int>((Q.back().g + (r == p ? tv : tz)).get(), '\n'); 1337 } 1338 int main() { int T = read<int>(); while (T--) solve(); return 0; } 1339 ``` 1340 1341 **Bonus** 1342 1343 Try to solve the initial problem: count the number of valid array $b$ for $n\le 500$. 1344 1345 **hint** 1346 1347 Consider $f_{i,j,k}$: the number of ways to fill the first $i$ elements of $b$, which contains at most $j$ first elements from $a$ as a subsequence, and the sum of the first $i$ elements is $k$. 1348 1349 Try to optimize this from $O(n^2s^2)$ to $O(n^2s)$, and then $O(\rm{poly}(n))$, and then $O(n^3)$. 1350 1351 **Rate the Problem** 1352 1353 * Amazing problem: 1354 * Good problem: 1355 * Average problem: 1356 * Bad problem: 1357 * Didn't solve: