codeforces-scrape

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

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 ![ ](/predownloaded/b2/7d/b27d3cabf78bcf22253eefb09759f982e2361e65.jpg)
    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 ![ ](/predownloaded/12/25/1225a57aa1738c9aa56efd6428416125af687e45.jpg)
    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: