2029.md (40353B)
1 Source: https://codeforces.com/blog/entry/133516 2 3 Thank you all for participating in the round! 4 5 We apologize for the wrong checker in problem E at the beginning of the contest, as well as the weak tests in problem B. To be honest, all the hacked submissions have similar logic and codes in B, which made me suspicious. Anyway, we are sorry for the inconvenience! >_< 6 7 **Rating Predictions** 8 9 | | A | B | C | D | E | F | G | H | I | 10 | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | 11 | [Error_Yuan](/profile/Error_Yuan "Master Error_Yuan") | 800 | 1200 | **1600** | **2100** | **2300** | 2600 | **3000** | 3400 | **3500** | 12 | [sszcdjr](/profile/sszcdjr "Master sszcdjr") | 800 | 1100 | 1600 | 2000 | 2300 | **2600** | 2900 | **3300** | 3500 | 13 | [_istil](/profile/_istil "International Grandmaster _istil") | 800 | **1000** | 1400 | 2200 | **2300** | 2600 | **3000** | 3500 | 3500 | 14 | [Otomachi_Una](/profile/Otomachi_Una "International Grandmaster Otomachi_Una") | **800** | 1000 | 1600 | 2200 | 2400 | 2600 | 3200 | 3500 | 3500 | 15 | [dXqwq](/profile/dXqwq "Legendary Grandmaster dXqwq") | 900 | 1100 | 1700 | 2200 | 2400 | 2600 | 3200 | 3500 | 3500 | 16 | [Kubic](/profile/Kubic "Legendary Grandmaster Kubic") | 800 | 1000 | 1600 | 2400 | 2200 | 2800 | 3000 | 3500 | 3300 | 17 | [wsc2008qwq](/profile/wsc2008qwq "Master wsc2008qwq") | 800 | 1100 | 1600 | 1900 | 2200 | 2700 | 3100 | | | 18 | [chromate00](/profile/chromate00 "Expert chromate00") | 800 | 1000 | 1600 | 1900 | | | | | | 19 | [rui_er](/profile/rui_er "International Grandmaster rui_er") | 800 | 1000 | 1500 | 1800 | 2200 | 2500 | 3000 | | | 20 | [abc864197532](/profile/abc864197532 "International Grandmaster abc864197532") | 800 | 1100 | 1600 | 2200 | 2300 | 2500 | 2900 | | | 21 22 | | A | B | C | D | E | F | G | H | I | 23 | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | 24 | Average | 810 | 1060 | 1580 | 2090 | 2289 | 2611 | 3033 | 3450 | 3467 | 25 | Actual | 800 | 1100 | 1700 | 1900 | 2100 | 2500 | 3000 | 3500 | 3400 (Thank you, [rainboy](/profile/rainboy "Master rainboy")) | 26 27 [2029A - Set](/contest/2029/problem/A "Refact.ai Match 1 (Codeforces Round 985)") 28 29 Author: [Otomachi_Una](/profile/Otomachi_Una "International Grandmaster Otomachi_Una") 30 First Blood: [Benq](/profile/Benq "Legendary Grandmaster Benq") at 00:00:51 31 32 **Hint** 33 34 Greedy from small to large. 35 36 **Solution** 37 38 We can delete the numbers from small to large. Thus, previously removed numbers will not affect future choices (if $x \lt y$, then $x$ cannot be a multiple of $y$). So an integer $x$ ($l\le x\le r$) can be removed if and only if $k\cdot x\le r$, that is, $x\le \left\lfloor\frac{r}{k}\right\rfloor$. The answer is $\max\left(\left\lfloor\frac{r}{k}\right\rfloor-l+1,0\right)$. 39 40 Time complexity: $\mathcal{O}(1)$ per test case. 41 42 **Code (C++)** 43 44 ``` 45 #include <bits/stdc++.h> 46 #define all(s) s.begin(), s.end() 47 using namespace std; 48 using ll = long long; 49 using ull = unsigned long long; 50 51 const int _N = 1e5 + 5; 52 53 int T; 54 55 void solve() { 56 int l, r, k; cin >> l >> r >> k; 57 cout << max(r / k - l + 1, 0) << endl; 58 return; 59 } 60 61 int main() { 62 ios::sync_with_stdio(false), cin.tie(0), cout.tie(0); 63 cin >> T; 64 while (T--) { 65 solve(); 66 } 67 } 68 ``` 69 70 **Code (Python 3)** 71 72 ``` 73 for _ in range(int(input())): 74 l, r, k = map(int, input().split()) 75 print(max(r // k - l + 1, 0)) 76 ``` 77 78 **Rate the Problem** 79 80 * Amazing problem: 81 * Good problem: 82 * Average problem: 83 * Bad problem: 84 * Didn't solve: 85 86 [2029B - Replacement](/contest/2029/problem/B "Refact.ai Match 1 (Codeforces Round 985)") 87 88 Author: [_istil](/profile/_istil "International Grandmaster _istil") 89 First Blood: [Benq](/profile/Benq "Legendary Grandmaster Benq") at 00:02:30 90 91 **Hint** 92 93 ($\texttt{01}$ or $\texttt{10}$ exists) $\Longleftrightarrow$ (both $\texttt{0}$ and $\texttt{1}$ exist). 94 95 **Solution** 96 97 Each time we do an operation, if $s$ consists only of $\texttt{0}$ or $\texttt{1}$, we surely cannot find any valid indices. Otherwise, we can always perform the operation successfully. In the $i$-th operation, if $t_i=\texttt{0}$, we actually decrease the number of $\texttt{1}$-s by $1$, and vice versa. Thus, we only need to maintain the number of $\texttt{0}$-s and $\texttt{1}$-s in $s$. If any of them falls to $0$ before the last operation, the answer is `NO`, otherwise, the answer is `YES`. 98 99 Time complexity: $\mathcal{O}(n)$ per test case. 100 101 **Code (C++)** 102 103 ``` 104 #include <bits/stdc++.h> 105 #define all(s) s.begin(), s.end() 106 107 using namespace std; 108 using ll = long long; 109 110 const int _N = 1e5 + 5; 111 112 void solve() { 113 int n; cin >> n; 114 string s, t; cin >> s >> t; 115 int cnt0 = count(all(s), '0'), cnt1 = n - cnt0; 116 for (int i = 0; i < n - 1; i++) { 117 if (cnt0 == 0 || cnt1 == 0) { 118 cout << "NO" << '\n'; 119 return; 120 } 121 if (t[i] == '1') cnt0--; 122 else cnt1--; 123 } 124 cout << "YES" << '\n'; 125 } 126 127 int main() { 128 int T; cin >> T; 129 while (T--) { 130 solve(); 131 } 132 } 133 ``` 134 135 **Code (Python 3)** 136 137 ``` 138 for _ in range(int(input())): 139 n = int(input()) 140 s = input() 141 one = s.count("1") 142 zero = s.count("0") 143 ans = "YES" 144 for ti in input(): 145 if one == 0 or zero == 0: 146 ans = "NO" 147 break 148 one -= 1 149 zero -= 1 150 if ti == "1": 151 one += 1 152 else: 153 zero += 1 154 print(ans) 155 ``` 156 157 **Rate the Problem** 158 159 * Amazing problem: 160 * Good problem: 161 * Average problem: 162 * Bad problem: 163 * Didn't solve: 164 165 [2029C - New Rating](/contest/2029/problem/C "Refact.ai Match 1 (Codeforces Round 985)") 166 167 Author: [Error_Yuan](/profile/Error_Yuan "Master Error_Yuan") 168 First Blood: [ksun48](/profile/ksun48 "Legendary Grandmaster ksun48") at 00:05:34 169 170 **Solution 1 (with hints)** 171 172 **Hint 1** 173 174 Binary search. 175 176 **Hint 2** 177 178 Do something backward. 179 180 **Solution** 181 182 First, do binary search on the answer. Suppose we're checking whether the answer can be $\ge k$ now. 183 184 Let $f_i$ be the current rating after participating in the $1$-st to the $i$-th contest (without skipping). 185 186 Let $g_i$ be the minimum rating before the $i$-th contest to make sure that the final rating is $\ge k$ (without skipping). 187 188 $f_i$-s can be calculated easily by simulating the process in the statement. For $g_i$-s, it can be shown that 189 190 $ g_i= \begin{cases} g_{i+1}-1, & a_i\ge g_{i+1}\\ g_{i+1}+1, & a_i \lt g_{i+1} \end{cases} $ 191 192 where $g_{n+1}=k$. 193 194 Then, we should check if there exists an interval $[l,r]$ ($1\le l\le r\le n$), such that $f_{l-1}\ge g_{r+1}$. If so, we can choose to skip $[l,r]$ and get a rating of $\ge k$. Otherwise, it is impossible to make the rating $\ge k$. 195 196 We can enumerate on $r$ and use a prefix max to check whether valid $l$ exists. 197 198 Time complexity: $\mathcal{O}(n\log n)$ per test case. 199 200 **Solution 2 (with hints)** 201 202 **Hint 1** 203 204 Consider DP. 205 206 **Hint 2** 207 208 There are only three possible states for each contest: before, in, or after the skipped interval. 209 210 **Solution** 211 212 Consider $dp_{i,0/1/2}=$ the maximum rating after the $i$-th contest, where the $i$-th contest is before/in/after the skipped interval. 213 214 Let $f(a,x)=$ the result rating when current rating is $a$ and the performance rating is $x$, then 215 216 $ \begin{cases} dp_{i,0} = f(dp_{i-1,0}, a_i),\\ dp_{i,1} = \max(dp_{i-1,1}, dp_{i-1,0}), \\ dp_{i,2} = \max(f(dp_{i-1,1}, a_i), f(dp_{i-1,2}, a_i)). \end{cases} $ 217 218 And the final answer is $\max(dp_{n,1}, dp_{n,2})$. 219 220 Time complexity: $\mathcal{O}(n)$ per test case. 221 222 **Code (Solution 1, C++)** 223 224 ``` 225 #include <bits/stdc++.h> 226 #define all(s) s.begin(), s.end() 227 using namespace std; 228 using ll = long long; 229 using ull = unsigned long long; 230 231 const int _N = 1e5 + 5; 232 233 int T; 234 235 void solve() { 236 int n; cin >> n; 237 vector<int> a(n + 1); 238 for (int i = 1; i <= n; i++) cin >> a[i]; 239 vector<int> pre(n + 1); 240 int curf = 0; 241 for (int i = 1; i <= n; i++) { 242 if (curf < a[i]) curf++; 243 else if (curf > a[i]) curf--; 244 pre[i] = max(pre[i - 1], curf); 245 } 246 auto check = [&](int k) { 247 int curg = k; 248 for (int i = n; i >= 1; i--) { 249 if (pre[i - 1] >= curg) return true; 250 if (a[i] < curg) curg++; 251 else curg--; 252 } 253 return false; 254 }; 255 int L = 0, R = n + 1; 256 while (L < R) { 257 int mid = (L + R + 1) >> 1; 258 if (check(mid)) L = mid; 259 else R = mid - 1; 260 } 261 cout << L << '\n'; 262 return; 263 } 264 265 int main() { 266 ios::sync_with_stdio(false), cin.tie(0), cout.tie(0); 267 cin >> T; 268 while (T--) { 269 solve(); 270 } 271 } 272 ``` 273 274 **Code (Solution 2, Python 3)** 275 276 ``` 277 for _ in range(int(input())): 278 n = int(input()) 279 280 def f(a, x): 281 return a + (a < x) - (a > x) 282 283 dp = [0, -n, -n] 284 for x in map(int, input().split()): 285 dp[2] = max(f(dp[1], x), f(dp[2], x)) 286 dp[1] = max(dp[1], dp[0]) 287 dp[0] = f(dp[0], x) 288 289 print(max(dp[1], dp[2])) 290 ``` 291 292 **Rate the Problem** 293 294 * Amazing problem: 295 * Good problem: 296 * Average problem: 297 * Bad problem: 298 * Didn't solve: 299 300 [2029D - Cool Graph](/contest/2029/problem/D "Refact.ai Match 1 (Codeforces Round 985)") 301 302 Author: [Error_Yuan](/profile/Error_Yuan "Master Error_Yuan") 303 First Blood: [ksun48](/profile/ksun48 "Legendary Grandmaster ksun48") at 00:13:24 304 305 There are many different approaches to this problem. Only the easiest one (at least I think so) is shared here. 306 307 **Hint 1** 308 309 Try to make the graph into a forest first. 310 311 **Hint 2** 312 313 ($deg_i\le 1$ for every $i$) $\Longrightarrow$ (The graph is a forest). 314 315 **Solution** 316 317 Let $d_i$ be the degree of vertex $i$. 318 319 First, we keep doing the following until it is impossible: 320 321 * Choose a vertex $u$ with $d_u\ge 2$, then find any two vertices $v,w$ adjacent to $u$. Perform the operation on $(u,v,w)$. 322 323 Since each operation decreases the number of edges by at least $1$, at most $m$ operations will be performed. After these operations, $d_i\le 1$ holds for every $i$. Thus, the resulting graph consists only of components with size $\le 2$. 324 325 If there are no edges, the graph is already *cool*, and we don't need to do any more operations. 326 327 Otherwise, let's pick an arbitrary edge $(u,v)$ as the base of the final tree, and then merge everything else to it. 328 329 For a component with size $=1$ (i.e. it is a single vertex $w$), perform the operation on $(u, v, w)$, and set $(u, v) \gets (u, w)$. 330 331  332 333 For a component with size $=2$ (i.e. it is an edge connecting $a$ and $b$), perform the operation on $(u, a, b)$. 334 335  336 337 It is clear that the graph is transformed into a tree now. 338 339 The total number of operations won't exceed $n+m\le 2\cdot \max(n,m)$. 340 341 In the author's solution, we used some data structures to maintain the edges, thus, the time complexity is $\mathcal{O}(n+m\log m)$ per test case. 342 343 **Code (C++)** 344 345 ``` 346 #include <bits/stdc++.h> 347 using namespace std; 348 #ifdef DEBUG 349 #include "debug.hpp" 350 #else 351 #define debug(...) (void)0 352 #endif 353 354 using i64 = int64_t; 355 constexpr bool test = false; 356 357 int main() { 358 cin.tie(nullptr)->sync_with_stdio(false); 359 int t; 360 cin >> t; 361 for (int ti = 0; ti < t; ti += 1) { 362 int n, m; 363 cin >> n >> m; 364 vector<set<int>> adj(n + 1); 365 for (int i = 0, u, v; i < m; i += 1) { 366 cin >> u >> v; 367 adj[u].insert(v); 368 adj[v].insert(u); 369 } 370 vector<tuple<int, int, int>> ans; 371 for (int i = 1; i <= n; i += 1) { 372 while (adj[i].size() >= 2) { 373 int u = *adj[i].begin(); 374 adj[i].erase(adj[i].begin()); 375 int v = *adj[i].begin(); 376 adj[i].erase(adj[i].begin()); 377 adj[u].erase(i); 378 adj[v].erase(i); 379 ans.emplace_back(i, u, v); 380 if (adj[u].contains(v)) { 381 adj[u].erase(v); 382 adj[v].erase(u); 383 } else { 384 adj[u].insert(v); 385 adj[v].insert(u); 386 } 387 } 388 } 389 vector<int> s; 390 vector<pair<int, int>> p; 391 for (int i = 1; i <= n; i += 1) { 392 if (adj[i].size() == 0) { 393 s.push_back(i); 394 } else if (*adj[i].begin() > i) { 395 p.emplace_back(i, *adj[i].begin()); 396 } 397 } 398 if (not p.empty()) { 399 auto [x, y] = p.back(); 400 p.pop_back(); 401 for (int u : s) { 402 ans.emplace_back(x, y, u); 403 tie(x, y) = pair(x, u); 404 } 405 for (auto [u, v] : p) { 406 ans.emplace_back(y, u, v); 407 } 408 } 409 println("{}", ans.size()); 410 for (auto [x, y, z] : ans) println("{} {} {}", x, y, z); 411 } 412 } 413 ``` 414 415 **Rate the Problem** 416 417 * Amazing problem: 418 * Good problem: 419 * Average problem: 420 * Bad problem: 421 * Didn't solve: 422 423 [2029E - Common Generator](/contest/2029/problem/E "Refact.ai Match 1 (Codeforces Round 985)") 424 425 Author: [Error_Yuan](/profile/Error_Yuan "Master Error_Yuan"), [_istil](/profile/_istil "International Grandmaster _istil") 426 First Blood: [ksun48](/profile/ksun48 "Legendary Grandmaster ksun48") at 00:23:50 427 428 **Hint 1** 429 430 $2$ is powerful. 431 432 **Hint 2** 433 434 Consider primes. 435 436 **Hint 3** 437 438 How did you prove that $2$ can generate every integer except odd primes? Can you generalize it? 439 440 **Solution** 441 442 In this problem, we do not take the integer $1$ into consideration. 443 444 **Claim 1.** $2$ can generate every integer except odd primes. 445 446 **Proof.** For a certain non-prime $x$, let $\operatorname{mind}(x)$ be the minimum divisor of $x$. Then $x-\operatorname{mind}(x)$ must be an even number, which is $\ge 2$. So $x-\operatorname{mind}(x)$ can be generated by $2$, and $x$ can be generated by $x-\operatorname{mind}(x)$. Thus, $2$ is a generator of $x$. 447 448 **Claim 2.** Primes can only be generated by themselves. 449 450 According to the above two claims, we can first check if there exist primes in the array $a$. If not, then $2$ is a common generator. Otherwise, let the prime be $p$, the only possible generator should be $p$ itself. So we only need to check whether $p$ is a generator of the rest integers. 451 452 For an even integer $x$, it is easy to see that, $p$ is a generator of $x$ if and only if $x\ge 2\cdot p$. 453 454 **Claim 3.** For a prime $p$ and an odd integer $x$, $p$ is a generator of $x$ if and only if $x - \operatorname{mind}(x)\ge 2\cdot p$. 455 456 **Proof.** First, $x-\operatorname{mind}(x)$ is the largest integer other than $x$ itself that can generate $x$. Moreover, only even numbers $\ge 2\cdot p$ can be generated by $p$ ($x-\operatorname{mind}(x)$ is even). That ends the proof. 457 458 Thus, we have found a good way to check if a certain number can be generated from $p$. We can use the linear sieve to pre-calculate all the $\operatorname{mind}(i)$-s. 459 460 Time complexity: $\mathcal{O}(\sum n+V)$, where $V=\max a_i$. 461 462 Some other solutions with worse time complexity can also pass, such as $\mathcal{O}(V\log V)$ and $\mathcal{O}(t\sqrt{V})$. 463 464 **Code (C++)** 465 466 ``` 467 #include <bits/stdc++.h> 468 #define all(s) s.begin(), s.end() 469 using namespace std; 470 using ll = long long; 471 using ull = unsigned long long; 472 473 const int _N = 4e5 + 5; 474 475 int vis[_N], pr[_N], cnt = 0; 476 477 void init(int n) { 478 vis[1] = 1; 479 for (int i = 2; i <= n; i++) { 480 if (!vis[i]) { 481 pr[++cnt] = i; 482 } 483 for (int j = 1; j <= cnt && i * pr[j] <= n; j++) { 484 vis[i * pr[j]] = pr[j]; 485 if (i % pr[j] == 0) continue; 486 } 487 } 488 } 489 490 int T; 491 492 void solve() { 493 int n; cin >> n; 494 vector<int> a(n + 1); 495 for (int i = 1; i <= n; i++) cin >> a[i]; 496 int p = 0; 497 for (int i = 1; i <= n; i++) { 498 if (!vis[a[i]]) p = a[i]; 499 } 500 if (!p) { 501 cout << 2 << '\n'; 502 return; 503 } 504 for (int i = 1; i <= n; i++) { 505 if (a[i] == p) continue; 506 if (vis[a[i]] == 0) { 507 cout << -1 << '\n'; 508 return; 509 } 510 if (a[i] & 1) { 511 if (a[i] - vis[a[i]] < 2 * p) { 512 cout << -1 << '\n'; 513 return; 514 } 515 } else { 516 if (a[i] < 2 * p) { 517 cout << -1 << '\n'; 518 return; 519 } 520 } 521 } 522 cout << p << '\n'; 523 return; 524 } 525 526 int main() { 527 ios::sync_with_stdio(false), cin.tie(0), cout.tie(0); 528 init(400000); 529 cin >> T; 530 while (T--) { 531 solve(); 532 } 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 [2029F - Palindrome Everywhere](/contest/2029/problem/F "Refact.ai Match 1 (Codeforces Round 985)") 545 546 Author: [sszcdjr](/profile/sszcdjr "Master sszcdjr") 547 First Blood: [taeyeon_ss](/profile/taeyeon_ss "International Grandmaster taeyeon_ss") at 00:16:50 548 549 **Hint 1** 550 551 If there are both consecutive $\texttt{R}$-s and $\texttt{B}$-s, does the condition hold for all $(i,j)$? Why? 552 553 **Hint 2** 554 555 Suppose that there are only consecutive $\texttt{R}$-s, check the parity of the number of $\texttt{R}$-s in each consecutive segment of $\texttt{R}$-s. 556 557 **Hint 3** 558 559 If for each consecutive segment of $\texttt{R}$-s, the parity of the number of $\texttt{R}$-s is odd, does the condition hold for all $(i,j)$? Why? 560 561 **Hint 4** 562 563 If for at least two of the consecutive segments of $\texttt{R}$-s, the parity of the number of $\texttt{R}$-s is even, does the condition hold for all $(i,j)$? Why? 564 565 **Hint 5** 566 567 Is this the necessary and sufficient condition? Why? 568 569 **Hint 6** 570 571 Don't forget some trivial cases like $\texttt{RRR...RB}$ and $\texttt{RRR...R}$. 572 573 **Solution** 574 575 For each $k \gt n$ or $k\leq0$, let $c_k$ be $c_{k\bmod n}$. 576 577 **Lemma 1**: If there are both consecutive $\texttt{R}$-s and $\texttt{B}$-s, the answer is `NO`. 578 579 **Proof 1**: Suppose that $c_{i-1}=c_i=\texttt{R}$ and $c_{j-1}=c_j=\texttt{B}$, it's obvious that there doesn't exist a palindrome route between $i$ and $j$. 580 581 Imagine there are two persons on vertex $i$ and $j$. They want to meet each other (they are on the same vertex or adjacent vertex) and can only travel through an edge of the same color. 582 583 **Lemma 2**: Suppose that there are only consecutive $\texttt{R}$-s, if for each consecutive segment of $\texttt{R}$-s, the parity of the number of $\texttt{R}$-s is odd, the answer is `NO`. 584 585 **Proof 2**: Suppose that $c_i=c_j=\texttt{B}$, $i\not\equiv j\pmod n$ and $c_{i+1}=c_{i+2}=\dots=c_{j-1}=\texttt{R}$. The two persons on $i$ and $j$ have to "cross" $\texttt{B}$ simultaneously. As for each consecutive segment of $\texttt{R}$-s, the parity of the number of $\texttt{R}$-s is odd, they can only get to the same side of their current consecutive segment of $\texttt{R}$-s. After "crossing" $\texttt{B}$, they will still be on different consecutive segments of $\texttt{R}$-s separated by exactly one $\texttt{B}$ and can only get to the same side. Thus, they will never meet. 586 587 **Lemma 3**: Suppose that there are only consecutive $\texttt{R}$-s, if, for at least two of the consecutive segments of $\texttt{R}$-s, the parity of the number of $\texttt{R}$-s is even, the answer is `NO`. 588 589 **Proof 3**: Suppose that $c_i=c_j=\texttt{B}$, $i\not\equiv j \pmod n$ and vertex $i$ and $j$ are both in a consecutive segment of $\texttt{R}$-s with even number of $\texttt{R}$-s. Let the starting point of two persons be $i$ and $j-1$ and they won't be able to "cross" and $\texttt{B}$. Thus, they will never meet. 590 591 The only case left is that there is exactly one consecutive segment of $\texttt{R}$-s with an even number of $\texttt{R}$-s. 592 593 **Lemma 4**: Suppose that there are only consecutive $\texttt{R}$-s, if, for exactly one of the consecutive segments of $\texttt{R}$-s, the parity of the number of $\texttt{R}$-s is even, the answer is `YES`. 594 595 **Proof 4**: Let the starting point of the two persons be $i,j$. Consider the following cases: 596 597 **Case 1**: If vertex $i$ and $j$ are in the same consecutive segment of $\texttt{R}$-s, the two persons can meet each other by traveling through the $\texttt{R}$-s between them. 598 599 **Case 2**: If vertex $i$ and $j$ are in the different consecutive segment of $\texttt{R}$-s and there are odd numbers of $\texttt{R}$-s in both segments, the two person may cross $\texttt{B}$-s in the way talked about in **Proof 2**. However, when one of them reaches a consecutive segment with an even number of $\texttt{R}$-s, the only thing they can do is let the one in an even segment cross the whole segment and "cross" the next $\texttt{B}$ in the front, while letting the other one traveling back and forth and "cross" the $\texttt{B}$ he just "crossed". Thus, unlike the situation in **Proof 2**, we successfully changed the side they can both get to and thus they will be able to meet each other as they are traveling toward each other and there are only odd segments between them. 600 601 **Case 3**: If vertex $i$ and $j$ are in the different consecutive segment of $\texttt{R}$-s and there are an odd number of $\texttt{R}$-s in exactly one of the segments, we can let both of them be in one side of there segments and change the situation to the one we've discussed about in **Case 2** (when one of them reached a consecutive segment with even number of $\texttt{R}$-s). 602 603 As a result, the answer is `YES` if: 604 605 * At least $n-1$ of $c_1,c_2,\dots,c_n$ are the same (Hint 6), or 606 * Suppose that there are only consecutive $\texttt{R}$-s, there's exactly one of the consecutive segments of $\texttt{R}$-s such that the parity of the number of $\texttt{R}$-s is even. 607 608 And we can judge them in $\mathcal{O}(n)$ time complexity. 609 610 **Code (C++)** 611 612 ``` 613 #include <bits/stdc++.h> 614 using namespace std; 615 void solve(){ 616 int n; cin>>n; 617 string s; cin>>s; 618 int visr=0,visb=0,ok=0; 619 for(int i=0;i<n;i++){ 620 if(s[i]==s[(i+1)%n]){ 621 if(s[i]=='R') visr=1; 622 else visb=1; 623 ok++; 624 } 625 } 626 if(visr&visb){ 627 cout<<"NO\n"; 628 return ; 629 } 630 if(ok==n){ 631 cout<<"YES\n"; 632 return ; 633 } 634 if(visb) for(int i=0;i<n;i++) s[i]='R'+'B'-s[i]; 635 int st=0; 636 for(int i=0;i<n;i++) if(s[i]=='B') st=(i+1)%n; 637 vector<int> vc; 638 int ntot=0,cnt=0; 639 for(int i=0,j=st;i<n;i++,j=(j+1)%n){ 640 if(s[j]=='B') vc.push_back(ntot),cnt+=(ntot&1)^1,ntot=0; 641 else ntot++; 642 } 643 if(vc.size()==1||cnt==1){ 644 cout<<"YES\n"; 645 return ; 646 } 647 cout<<"NO\n"; 648 return ; 649 } 650 signed main(){ 651 int t; cin>>t; 652 while(t--) solve(); 653 return 0; 654 } 655 ``` 656 657 **Bonus 1** 658 659 Count the number of strings of length $n$ satisfying the condition. 660 661 **Bonus 2** 662 663 Solve the problem for $c_i\in\{\texttt{A},\texttt{B},\dots,\texttt{Z}\}$, and solve the counting version. 664 665 **Rate the Problem** 666 667 * Amazing problem: 668 * Good problem: 669 * Average problem: 670 * Bad problem: 671 * Didn't solve: 672 673 [2029G - Balanced Problem](/contest/2029/problem/G "Refact.ai Match 1 (Codeforces Round 985)") 674 675 Author: [_istil](/profile/_istil "International Grandmaster _istil"), [Error_Yuan](/profile/Error_Yuan "Master Error_Yuan") 676 First Blood: [taeyeon_ss](/profile/taeyeon_ss "International Grandmaster taeyeon_ss") at 00:56:22 677 678 This problem has two approaches. The first one is the authors' solution, and the second one was found during testing. 679 680 **Solution 1 (with hints)** 681 682 **Hint 1** 683 684 The array $a$ is constructed with the operations. How can we use this property? 685 686 **Hint 2** 687 688 If we want to make all $a_i=x$, what is the minimum value of $x$? Use the property mentioned in Hint 1. 689 690 **Hint 3** 691 692 (For the subproblem in Hint 2), try to find an algorithm related to the positions of $\texttt{L/R}$-s directly. 693 694 **Hint 4** 695 696 (For the subproblem in Hint 2), the conclusion is that, the minimum $x$ equals $\text{# of }\texttt{L}\text{-s} + \text{# of }\texttt{R}\text{-s} - \text{# of adjacent }\texttt{LR}\text{-s}$. Think why. 697 698 **Hint 5** 699 700 Go for DP. 701 702 **Solution** 703 704 Read the hints first. 705 706 Then, note that there are only $\mathcal{O}(V)$ useful positions: If (after the initial operations) $a_i \gt V$ or $a_{i}=a_{i-1}$, we can simply ignore $a_i$, or merge $c_i$ into $c_{i-1}$. 707 708 Now let $dp(i,s)$ denote the answer when we consider the prefix of length $i$, and we have "saved" $s$ pairs of $\texttt{LR}$. 709 710 Then, 711 712 $ dp(i,s)=\displaystyle\max_{j \lt i} dp(j,s-|\mathrm{cntL}(j,i-1)-\mathrm{cntR}(j+1,i)|)+c_i $ 713 714 Write $\mathrm{cntL}$ and $\mathrm{cntR}$ as prefix sums: 715 716 $ dp(i,s)=\displaystyle\max_{j \lt i} dp(j,s-|\mathrm{preL}(i-1)-\mathrm{preR}(i)+\mathrm{preR}(j)-\mathrm{preL}(j-1)|)+c_i $ 717 718 Do casework on the sign of the things inside the $\mathrm{abs}$, and you can maintain both cases with 1D Fenwick trees. 719 720 Thus, you solved the problem in $\mathcal{O}(V^2\log V)$. 721 722 **Solution 2 (with hints)** 723 724 **Hint 1** 725 726 Solve the problem for a single $v$ first. 727 728 **Hint 2** 729 730 Don't think too much, just go straight for a DP solution. 731 732 **Hint 3** 733 734 Does your time complexity in DP contain $n$ or $m$? In fact, both $n$ and $m$ are useless. There are only $\mathcal{O}(V)$ useful positions. 735 736 **Hint 4** 737 738 Use some data structures to optimize your DP. Even $\mathcal{O}(v^2\log^2 v)$ is acceptable. 739 740 **Hint 5** 741 742 Here is the final step: take a look at your DP carefully. Can you change the definition of states a little, so that it can get the answer for each $1\le v\le V$? 743 744 **Solution** 745 746 First, note that there are only $\mathcal{O}(V)$ useful positions: If (after the initial operations) $a_i \gt V$ or $a_{i}=a_{i-1}$, we can simply ignore $a_i$, or merge $c_i$ into $c_{i-1}$. 747 748 Now, let's solve the problem for a single $v$. 749 750 Denote $dp(i,j,k)$ as the maximum answer when considering the prefix of length $i$, and there are $j$ prefix additions covering $i$, $k$ suffix additions covering $i$. 751 752 Enumerate on $i$, and it is easy to show that the state changes if and only if $j+k+a_i=v$, and 753 754 $ dp(i,j,k)=\displaystyle\max_{p\le j,q\ge k} dp(i-1,p,q) + c_i $ 755 756 You can use a 2D Fenwick tree to get the 2D prefix max. Thus, you solved the single $v$ case in $\mathcal{O}(v^2\log^2 v)$. 757 758 In fact, we can process the DP in $\mathcal{O}(v^2 \log v)$ by further optimization: 759 760 $ dp(i,j,k)=\displaystyle\max_{p\le i-1,q\ge j,v-a_p-q\le k} dp(p,q,v-a_p-q) + c_i $ 761 762 This only requires $a_p+q\ge a_i+j$ when $a_p\le a_i$, and $q\le j$ when $a_p\ge a_i$. So you can use 1D Fenwick trees to process the dp in $\mathcal{O}(v^2 \log v)$. 763 764 Now, let's go for the whole solution. 765 766 Let's modify the DP state a bit: now $dp(i,j,k)$ is the state when using $v-k$ suffix operations (note that $v$ is not a constant here). The transformation is similar. 767 768 Then the answer for $v=i$ will be $\max dp(*,*,i)$. 769 770 **Code (Solution 1, C++)** 771 772 ``` 773 #include <bits/stdc++.h> 774 #define all(s) s.begin(), s.end() 775 using namespace std; 776 using ll = long long; 777 using ull = unsigned long long; 778 using ld = double; 779 780 const int _N = 4105; 781 const ld inf = 1e15; 782 783 int T; 784 785 struct fenwick { 786 ll c[_N]; int N; 787 int lowbit(int x) { return x & (-x); } 788 void init(int n) { 789 N = n; 790 for (int i = 1; i <= N; i++) c[i] = -1e18; 791 } 792 void update(int x, ll v) { 793 // assert(x != 0); 794 while (x < N) { 795 c[x] = max(c[x], v); 796 x += lowbit(x); 797 } 798 } 799 ll getmx(int x) { 800 // assert(x != 0); 801 ll res = -1e18; 802 while (x > 0) { 803 res = max(res, c[x]); 804 x -= lowbit(x); 805 } 806 return res; 807 } 808 } pre[4105], suf[4105]; 809 810 void solve() { 811 int n, o, m, k; cin >> n >> o >> m; 812 k = 0; 813 vector<ll> a(n + 3), c(n + 3), d(n + 3), L(n + 3), R(n + 3), L2(n + 3), R2(n + 3); 814 for (int i = 1; i <= n; i++) cin >> c[i]; 815 for (int i = 1; i <= o; i++) { 816 char op; int x; cin >> op >> x; 817 if (op == 'L') L[x]++; 818 else R[x]++; 819 } 820 vector<int> tL(n + 3), tR(n + 3); 821 for (int i = 1; i <= n; i++) tR[i] = tR[i - 1] + R[i]; 822 for (int i = n; i >= 1; i--) tL[i] = tL[i + 1] + L[i]; 823 int q = 0, curL = 0, curR = 0; 824 for (int i = 1; i <= n; i++) { 825 a[i] = tL[i] + tR[i]; 826 if (a[i] <= m + k) { 827 if (a[i] == a[i - 1] && L[i] == 0 && R[i] == 0) { 828 if (q == 0) q++; 829 d[q] += c[i]; 830 continue; 831 } 832 q++; 833 L2[q] += L[i]; 834 R2[q] += R[i] + curR; 835 L2[q - 1] += curL; 836 d[q] += c[i]; 837 curL = curR = 0; 838 } else { 839 curL += L[i]; 840 curR += R[i]; 841 } 842 } 843 L2[0] = 0; L2[q] += curL; 844 for (int i = 1; i <= q; i++) L2[i] += L2[i - 1], R2[i] += R2[i - 1]; 845 m += k; 846 vector<ll> dp(2 * m + 2, -1e18); 847 for (int i = 0; i <= 2 * m; i++) { 848 pre[i].init(2 * m + 2); 849 suf[i].init(2 * m + 2); 850 } 851 vector<ll> ans(m + 1); 852 for (int i = 1; i <= q; i++) { 853 dp.resize(2 * m + 2, -1e18); 854 dp[L2[i - 1]] = d[i]; 855 for (int s = 0; s <= m; s++) { 856 ll res1 = pre[s - L2[i - 1] + m].getmx(R2[i] - L2[i - 1] + m + 1); 857 ll res2 = suf[s - R2[i] + m].getmx(m + 1 - R2[i] + L2[i - 1]); 858 dp[s] = max({ dp[s], res1 + d[i], res2 + d[i] }); 859 if (L2[q] + R2[i] - s >= 0 && L2[q] + R2[i] - s <= m) ans[L2[q] + R2[i] - s] = max(ans[L2[q] + R2[i] - s], dp[s]); 860 } 861 for (int s = 0; s <= m; s++) { 862 if (dp[s] <= -1e12) continue; 863 pre[s - L2[i - 1] + m].update(R2[i] - L2[i - 1] + m + 1, dp[s]); 864 suf[s - R2[i] + m].update(m + 1 - R2[i] + L2[i - 1], dp[s]); 865 } 866 } 867 for (int i = 1; i <= m; i++) { 868 ans[i] = max(ans[i - 1], ans[i]); 869 cout << ans[i] << " \n"[i == m]; 870 } 871 return; 872 } 873 874 int main() { 875 ios::sync_with_stdio(false), cin.tie(0), cout.tie(0); 876 cin >> T; 877 while (T--) { 878 solve(); 879 } 880 } 881 ``` 882 883 **Code (Solution 2, C++)** 884 885 ``` 886 #include <bits/stdc++.h> 887 using namespace std; 888 typedef long long ll; 889 #define pb push_back 890 #define pii pair<int, int> 891 #define all(a) a.begin(), a.end() 892 const int mod = 1e9 + 7, N = 5005; 893 894 void solve() { 895 int n, m, V; 896 cin >> n >> m >> V; 897 vector <int> c(n); 898 for (int i = 0; i < n; ++i) { 899 cin >> c[i]; 900 } 901 vector <int> pre(n + 1); 902 for (int i = 0; i < m; ++i) { 903 char x; int v; cin >> x >> v, --v; 904 if (x == 'L') { 905 pre[0]++, pre[v + 1]--; 906 } else { 907 pre[v]++; 908 } 909 } 910 for (int i = 0; i < n; ++i) { 911 pre[i + 1] += pre[i]; 912 } 913 vector <pair <ll, int>> vec; 914 for (int i = 0, j = 0; i < n; i = j) { 915 ll tot = 0; 916 while (j < n && pre[i] == pre[j]) { 917 tot += c[j], j++; 918 } 919 if (pre[i] <= V) { 920 vec.emplace_back(tot, pre[i]); 921 } 922 } 923 924 vector bit(V + 5, vector <ll>(V + 5, -1ll << 60)); 925 auto upd = [&](int x, int y, ll v) { 926 for (int i = x + 1; i < V + 5; i += i & (-i)) { 927 for (int j = y + 1; j < V + 5; j += j & (-j)) { 928 bit[i][j] = max(bit[i][j], v); 929 } 930 } 931 }; 932 auto query = [&](int x, int y) { 933 ll ans = -1ll << 60; 934 for (int i = x + 1; i > 0; i -= i & (-i)) { 935 for (int j = y + 1; j > 0; j -= j & (-j)) { 936 ans = max(ans, bit[i][j]); 937 } 938 } 939 return ans; 940 }; 941 942 upd(0, 0, 0); 943 vector <ll> tmp(V + 1); 944 for (auto [val, diff] : vec) { 945 for (int i = 0; i + diff <= V; ++i) { 946 tmp[i] = query(i, i + diff); 947 } 948 for (int i = 0; i + diff <= V; ++i) { 949 upd(i, i + diff, tmp[i] + val); 950 } 951 } 952 953 for (int i = 1; i <= V; ++i) { 954 cout << query(i, i) << " \n"[i == V]; 955 } 956 } 957 958 int main() { 959 ios::sync_with_stdio(false), cin.tie(0); 960 int t; 961 cin >> t; 962 while (t--) { 963 solve(); 964 } 965 } 966 ``` 967 968 **Rate the Problem** 969 970 * Amazing problem: 971 * Good problem: 972 * Average problem: 973 * Bad problem: 974 * Didn't solve: 975 976 **Bonus** 977 978 Solve the problem in $\mathcal{O}(V^2)$. 979 980 [2029H - Message Spread](/contest/2029/problem/H "Refact.ai Match 1 (Codeforces Round 985)") 981 982 Author: [sszcdjr](/profile/sszcdjr "Master sszcdjr") 983 First Blood: [Benq](/profile/Benq "Legendary Grandmaster Benq") at 02:04:40 (though unintended brute force), [jiangly](/profile/jiangly "Legendary Grandmaster jiangly") at 02:55:12 (intended, orz!) 984 985 **Hint 1** 986 987 It's hard to calculate the expected number. Try to change it to the probability. 988 989 **Hint 2** 990 991 Consider a $\mathcal{O}(3^n)$ dp first. 992 993 **Hint 3** 994 995 Use inclusion and exclusion. 996 997 **Hint 4** 998 999 Write out the transformation. Try to optimize it. 1000 1001 **Solution** 1002 1003 Let $dp_S$ be the probability such that exactly the points in $S$ have the message. 1004 1005 The answer is $\sum dp_S\cdot tr_S$, where $tr_S$ is the expected number of days before at least one vertex out of $S$ to have the message (counting from the day that exactly the points in $S$ have the message). 1006 1007 For transformation, enumerate $S,T$ such that $S\cap T=\varnothing$. Transfer $dp_S$ to $dp_{S\cup T}$. It's easy to precalculate the coefficient, and the time complexity differs from $\mathcal{O}(3^n)$, $\mathcal{O}(n\cdot 3^n)$ to $\mathcal{O}(n^2\cdot 3^n)$, according to the implementation. 1008 1009 The transformation is hard to optimize. Enumerate $T$ and calculate the probability such that vertices in $S$ is only connected with vertices in $T$, which means that the real status $R$ satisfies $S\subseteq R\subseteq (S\cup T)$. Use inclusion and exclusion to calculate the real probability. 1010 1011 List out the coefficient: 1012 1013 $\frac{\displaystyle\prod_{e\in\{1,2,3,\dots,n\}}(1-w_e)\cdot\prod_{e\in(S\cup T)}\frac{1}{1-w_e}\cdot\prod_{e\in \{1,2,\dots,n\}\setminus S}\frac{1}{1-w_e}\cdot\prod_{e\in T}(1-w_e)}{\displaystyle1-\prod_{e\in\{1,2,3,\dots,n\}}(1-w_e)\cdot\prod_{e\in S}\frac{1}{1-w_e}\cdot\prod_{e\in\{1,2,3,\dots,n\}\setminus S}\frac{1}{1-w_e}}$ 1014 1015 (Note that $w_e$ denotes the probability of the appearance of the edge $e$) 1016 1017 We can express it as $\mathrm{Const}\cdot f_{S\cup T}\cdot g_S\cdot h_T$. Use a subset convolution to optimize it. The total time complexity is $\mathcal{O}(2^n\cdot n^2)$. 1018 1019 It's easy to see that all $dp_S\neq0$ satisfies $1\in S$, so the time complexity can be $\mathcal{O}(2^{n-1}\cdot n^2)$ if well implemented. 1020 1021 **Code (C++)** 1022 1023 ``` 1024 #include <bits/stdc++.h> 1025 #define int long long 1026 using namespace std; 1027 const int N=(1<<21),mod=998244353; 1028 const int Lim=8e18; 1029 inline void add(signed &i,int j){ 1030 i+=j; 1031 if(i>=mod) i-=mod; 1032 } 1033 int qp(int a,int b){ 1034 int ans=1; 1035 while(b){ 1036 if(b&1) (ans*=a)%=mod; 1037 (a*=a)%=mod; 1038 b>>=1; 1039 } 1040 return ans; 1041 } 1042 int dp[N],f[N],g[N],h[N]; 1043 int s1[N],s2[N]; 1044 signed pre[22][N/2],t[22][N/2],pdp[N][22]; 1045 int p[N],q[N],totp,totq; 1046 signed main(){ 1047 int n,m; cin>>n>>m; 1048 int totprod=1; 1049 for(int i=0;i<(1<<n);i++) s1[i]=s2[i]=1; 1050 for(int i=1;i<=m;i++){ 1051 int u,v,p,q; cin>>u>>v>>p>>q; 1052 int w=p*qp(q,mod-2)%mod; 1053 (s1[(1<<(u-1))+(1<<(v-1))]*=(mod+1-w))%=mod; 1054 (s2[(1<<(u-1))+(1<<(v-1))]*=qp(mod+1-w,mod-2))%=mod; 1055 (totprod*=(mod+1-w))%=mod; 1056 } 1057 for(int j=1;j<=n;j++) for(int i=0;i<(1<<n);i++) if((i>>(j-1))&1) (s1[i]*=s1[i^(1<<(j-1))])%=mod,(s2[i]*=s2[i^(1<<(j-1))])%=mod; 1058 for(int i=0;i<(1<<n);i++) f[i]=s2[i],g[i]=totprod*s2[((1<<n)-1)^i]%mod*qp(mod+1-totprod*s2[i]%mod*s2[((1<<n)-1)^i]%mod,mod-2)%mod,h[i]=s1[i]; 1059 for(int i=1;i<(1<<n);i++) pre[__builtin_popcount(i)][i>>1]=h[i]; 1060 dp[1]=1; 1061 for(int j=1;j<=n;j++){ 1062 if(!((1>>(j-1))&1)) add(pdp[1|(1<<(j-1))][j],mod-(dp[1]*g[1]%mod*f[1]%mod)); 1063 } 1064 t[0][0]=dp[1]*g[1]%mod; 1065 for(int k=1;k<=n;k++) for(int j=1;j<n;j++) for(int i=0;i<(1<<(n-1));i++) if((i>>(j-1))&1) add(pre[k][i],pre[k][i^(1<<(j-1))]); 1066 for(int j=1;j<n;j++) for(int i=0;i<(1<<(n-1));i++) if((i>>(j-1))&1) add(t[0][i],t[0][i^(1<<(j-1))]); 1067 for(int k=1;k<n;k++){ 1068 totp=totq=0; 1069 for(int i=0;i<(1<<(n-1));i++) if(__builtin_popcount(i)<=k) p[++totp]=i; else q[++totq]=i; 1070 for(int l=1,i=p[l];l<=totp;l++,i=p[l]) for(int j=0;j<k;j++) add(t[k][i],1ll*t[j][i]*pre[k-j][i]%mod); 1071 for(int i=0;i<(1<<(n-1));i++) t[k][i]%=mod; 1072 for(int j=1;j<n;j++) for(int l=1,i=p[l];l<=totp;l++,i=p[l]) if((i>>(j-1))&1) add(t[k][i],mod-t[k][i^(1<<(j-1))]); 1073 for(int i=0;i<(1<<(n-1));i++){ 1074 if(__builtin_popcount(i)==k){ 1075 add(pdp[(i<<1)|1][0],t[k][i]*f[(i<<1)|1]%mod); 1076 int pre=0; 1077 for(int j=1;j<=n;j++){ 1078 (pre+=pdp[(i<<1)|1][j-1])%=mod; 1079 if(!((((i<<1)|1)>>(j-1))&1)) add(pdp[(i<<1)|1|(1<<(j-1))][j],mod-pre); 1080 } 1081 (pre+=pdp[(i<<1)|1][n])%=mod; 1082 dp[(i<<1)|1]=pre; 1083 for(int j=1;j<=n;j++){ 1084 if(!((((i<<1)|1)>>(j-1))&1)) add(pdp[(i<<1)|1|(1<<(j-1))][j],mod-(dp[(i<<1)|1]*g[(i<<1)|1]%mod*f[(i<<1)|1]%mod)); 1085 } 1086 t[k][i]=pre*g[(i<<1)|1]%mod; 1087 } 1088 else t[k][i]=0; 1089 } 1090 for(int j=1;j<n;j++) for(int l=1,i=q[l];l<=totq;l++,i=q[l]) if((i>>(j-1))&1) add(t[k][i],t[k][i^(1<<(j-1))]); 1091 } 1092 int ans=0; 1093 for(int i=1;i<(1<<n)-1;i+=2) (ans+=dp[i]*qp(mod+1-totprod*s2[i]%mod*s2[((1<<n)-1)^i]%mod,mod-2)%mod)%=mod; 1094 cout<<ans; 1095 return 0; 1096 } 1097 ``` 1098 1099 **Rate the Problem** 1100 1101 * Amazing problem: 1102 * Good problem: 1103 * Average problem: 1104 * Bad problem: 1105 * Didn't solve: 1106 1107 [2029I - Variance Challenge](/contest/2029/problem/I "Refact.ai Match 1 (Codeforces Round 985)") 1108 1109 Author: [Error_Yuan](/profile/Error_Yuan "Master Error_Yuan") 1110 First Blood: [rainboy](/profile/rainboy "Master rainboy") at 01:33:40 (intended, the only solve in contest, orz!) 1111 1112 **Hint 1** 1113 1114 The intended solution has nothing to do with dynamic programming. 1115 1116 **Hint 2** 1117 1118 This is the key observation of the problem. Suppose we have an array $b$ and a function $f(x)=\sum (b_i-x)^2$, then the minimum value of $f(x)$ is the variance of $b$. 1119 1120 **Hint 3** 1121 1122 Using the observation mentioned in Hint 2, we can reduce the problem to minimizing $\sum(a_i-x)^2$ for a **given** $x$. There are only $\mathcal{O}(n\cdot m)$ possible $x$-s. 1123 1124 **Hint 4** 1125 1126 The rest of the problem is somehow easy. Try flows, or just find a greedy algorithm! 1127 1128 **Hint 5** 1129 1130 If you are trying flows: the quadratic function is always convex. 1131 1132 **Solution** 1133 1134 **Key Observation.** Suppose we have an array $b$ and a function $f(x)=\sum (b_i-x)^2$, then the minimum value of $f(x)$ is the variance of $b$. 1135 1136 **Proof.** This is a quadratic function of $x$, and the its symmetry axis is $x=\frac{1}{n}\sum b_i$. So the minimum value is $f\left(\frac{1}{n}\sum b_i\right)$. That is exactly the definition of variance. 1137 1138 Thus, we can enumerate all possible $x$-s, and find the minimum $\sum (a_i-x)^2$ after the operations, then take the minimum across them. That will give the correct answer to the original problem. Note that there are only $\mathcal{O}(n\cdot m)$ possible $x$-s. 1139 1140 More formally, let $k_{x,c}$ be the minimum value of $\sum (a_i-x)^2$ after exactly $c$ operations. Then $\mathrm{ans}_i=\displaystyle\min_{\text{any possible }x} k_{x,i}$. 1141 1142 So we only need to solve the following (reduced) problem: 1143 1144 * Given a (maybe non-integer) number $x$. For each $1\le i\le m$, find the minimum value of $\sum (a_i-x)^2$ after exactly $i$ operations. 1145 1146 To solve this, we can use the MCMF model: 1147 1148 * Set a source node $s$ and a target node $t$. 1149 * For each $1\le i\le n$, add an edge from $s$ to $i$ with cost $0$. 1150 * For each $1\le i\le n$, add an edge from $i$ to $t$ with cost $0$. 1151 * For each $1\le i \lt n$, add an edge from $i$ to $i+1$ with cost being a function $\mathrm{cost}(f)=(a_i+f-x)^2-(a_i-x)^2$, where $f$ is the flow on this edge. 1152 * Note that the $\mathrm{cost}$ function is convex, so this model is correct, as you can split an edge into some edges with cost of $\mathrm{cost}(1)$, $\mathrm{cost}(2)-\mathrm{cost}(1)$, $\mathrm{cost}(3)-\mathrm{cost}(2)$, and so on. 1153 1154 Take a look at the model again. We don't need to run MCMF. We can see that it is just a process of regret greedy. So you only need to find the LIS (Largest Interval Sum :) ) for each operation. 1155 1156 Thus, we solved the reduced problem in $\mathcal{O(n\cdot m)}$. 1157 1158 Overall time complexity: $\mathcal{O}((n\cdot m)^2)$ per test case. 1159 1160 Reminder: don't forget to use `__int128` if you didn't handle the numbers carefully! 1161 1162 **Code (C++)** 1163 1164 ``` 1165 #include <bits/stdc++.h> 1166 #define all(s) s.begin(), s.end() 1167 using namespace std; 1168 using ll = long long; 1169 using ull = unsigned long long; 1170 1171 const int _N = 1e5 + 5; 1172 1173 int T; 1174 1175 void solve() { 1176 ll n, m, k; cin >> n >> m >> k; 1177 vector<ll> a(n + 1); 1178 for (int i = 1; i <= n; i++) cin >> a[i]; 1179 vector<ll> kans(m + 1, LLONG_MAX); 1180 vector<__int128> f(n + 1), g(n + 1), v(n + 1); 1181 vector<int> vis(n + 1), L(n + 1), L2(n + 1); 1182 ll sum = 0; 1183 for (int i = 1; i <= n; i++) sum += a[i]; 1184 __int128 pans = 0; 1185 for (int i = 1; i <= n; i++) pans += n * a[i] * a[i]; 1186 auto work = [&](ll s) { 1187 __int128 ans = pans; 1188 ans += s * s - 2ll * sum * s; 1189 f.assign(n + 1, LLONG_MAX); 1190 g.assign(n + 1, LLONG_MAX); 1191 for (int i = 1; i <= n; i++) { 1192 v[i] = n * (2 * a[i] * k + k * k) - 2ll * s * k; 1193 vis[i] = 0; 1194 } 1195 for (int i = 1; i <= m; i++) { 1196 for (int j = 1; j <= n; j++) { 1197 L[j] = L2[j] = j; 1198 if (f[j - 1] < 0) f[j] = f[j - 1] + v[j], L[j] = L[j - 1]; 1199 else f[j] = v[j]; 1200 if (!vis[j]) { 1201 g[j] = LLONG_MAX; 1202 continue; 1203 } 1204 if (g[j - 1] < 0) g[j] = g[j - 1] + 2ll * n * k * k - v[j], L2[j] = L2[j - 1]; 1205 else g[j] = 2ll * n * k * k - v[j]; 1206 } 1207 __int128 min_sum = LLONG_MAX; 1208 int l = 1, r = n, type = 0; 1209 for (int j = 1; j <= n; j++) { 1210 if (f[j] < min_sum) { 1211 min_sum = f[j], r = j, l = L[j]; 1212 } 1213 } 1214 for (int j = 1; j <= n; j++) { 1215 if (g[j] < min_sum) { 1216 min_sum = g[j], r = j, l = L2[j]; 1217 type = 1; 1218 } 1219 } 1220 ans += min_sum; 1221 if (type == 0) { 1222 for (int j = l; j <= r; j++) vis[j]++, v[j] += 2 * n * k * k; 1223 } else { 1224 for (int j = l; j <= r; j++) vis[j]--, v[j] -= 2 * n * k * k; 1225 } 1226 kans[i] = min((__int128)kans[i], ans); 1227 } 1228 }; 1229 1230 for (ll x = sum; x <= sum + n * m * k; x += k) { 1231 work(x); 1232 } 1233 for (int i = 1; i <= m; i++) cout << kans[i] << " \n"[i == m]; 1234 return; 1235 } 1236 1237 int main() { 1238 ios::sync_with_stdio(false), cin.tie(0), cout.tie(0); 1239 cin >> T; 1240 while (T--) { 1241 solve(); 1242 } 1243 } 1244 ``` 1245 1246 **Rate the Problem** 1247 1248 * Amazing problem: 1249 * Good problem: 1250 * Average problem: 1251 * Bad problem: 1252 * Didn't solve: