1842.md (32159B)
1 Source: https://codeforces.com/blog/entry/117606 2 3 ### [1842A - Tenzing and Tsondu](/contest/1842/problem/A) 4 5 **Tutorial** 6 7 Let's view it as when monsters $x$ and $y$ fight, their health changes into $\max(x-y,0)$ and $\max(y-x,0)$ respectively. So any monster with $0$ health is considered dead. Therefore, a player loses when the health of his monsters are all $0$. 8 9 Notice that $\max(x-y,0)=x-\min(x,y)$ and $\max(y-x,0)=y-\min(x,y)$. Therefore, after each step, the sum of the health of monsters decrease by the same amount for both players. 10 11 Therefore, we only need to know $\sum a_i$ and $\sum b_i$ to determine who wins. If $\sum a_i \gt \sum b_i$, Tsondu wins. Else if $\sum a_i \lt \sum b_i$, Tenzing wins. Else, it is a draw. 12 13 **Code** 14 15 ``` 16 #include <iostream> 17 18 using namespace std; 19 20 int main() { 21 ios::sync_with_stdio(false), cin.tie(nullptr); 22 int T; 23 cin >> T; 24 while (T--) { 25 int n, m, a[50], b[50]; 26 long long sumA = 0, sumB = 0; 27 cin >> n >> m; 28 for (int i = 0; i < n; i++) 29 cin >> a[i], sumA += a[i]; 30 for (int i = 0; i < m; i++) 31 cin >> b[i], sumB += b[i]; 32 if (sumA > sumB) cout << "Tsondu\n"; 33 if (sumA < sumB) cout << "Tenzing\n"; 34 if (sumA == sumB) cout << "Draw\n"; 35 } 36 } 37 ``` 38 39 ### [1842B - Tenzing and Books](/contest/1842/problem/B) 40 41 **Tutorial** 42 43 Observe the bitwise OR: if a bit of the *knowledge* changes to $1$, it will never become $0$. 44 45 It tells us, if a book has difficulty rating $y$, and $x|y \neq x$, Tenzing will never read this book because it will change a $0$ bit in $x$ to $1$. 46 47 We called a number $y$ valid if $x|y=x$. For each sequence, we can find a longest prefix of it such that all numbers in this prefix are valid. Find the bitwise OR of the three prefix and check whether it equals to $x$. 48 49 Time complexity: $O(n)$ per test case. 50 51 **Alternative Solution** 52 53 A naive approach is to enumerate the prefixes of the three stacks, which is an enumeration of $n^3$. For each stack, the bitwise OR of the prefix has at most $31$ different values (including empty prefix), because the bitwise OR of the prefix is non-decreasing, and each change will increase the number of 1s in binary. Since the number of 1s in binary cannot exceed $30$, it can be changed at most 30 times. Therefore, the enumeration is reduced to $\min(n,31)^3$. In the worst case, the time complexity is $O(\sum n * 31^2)$. 54 55 **Code** 56 57 ``` 58 #include <iostream> 59 60 using namespace std; 61 62 int main() { 63 ios::sync_with_stdio(false), cin.tie(nullptr); 64 int T; 65 cin >> T; 66 while (T--) { 67 int n, x, a[100000]; 68 cin >> n >> x; 69 int s = 0; 70 for (int i = 0; i < 3; i++) { 71 for (int j = 0; j < n; j++) cin >> a[j]; 72 for (int j = 0; j < n; j++) { 73 if ((x | a[j]) != x) break; 74 s |= a[j]; 75 } 76 } 77 if (s == x) cout << "YES\n"; 78 else cout << "NO\n"; 79 } 80 } 81 ``` 82 83 **Alternative Code** 84 85 ``` 86 #include <bits/stdc++.h> 87 88 using namespace std; 89 90 int main() { 91 ios::sync_with_stdio(false), cin.tie(nullptr); 92 int T; 93 cin >> T; 94 while (T--) { 95 int n, x, ai; 96 cin >> n >> x; 97 vector<int> pre[3]; 98 for (int i = 0; i < 3; i++) { 99 int s = 0; 100 pre[i].push_back(s); 101 for (int j = 0; j < n; j++) { 102 cin >> ai; 103 if ((s | ai) != s) 104 s |= ai, pre[i].push_back(s); 105 } 106 } 107 bool ans = 0; 108 for (int A : pre[0]) for (int B : pre[1]) for (int C : pre[2]) 109 ans |= (A | B | C) == x; 110 cout << (ans ? "YES\n" : "NO\n"); 111 } 112 } 113 ``` 114 115 ### [1842C - Tenzing and Balls](/contest/1842/problem/C) 116 117 **Tutorial** 118 119 Let us write down the original index of each range we delete. 120 121 Firstly, it is impossible to delete ranges $(a,c)$ and $(b,d)$ where $a \lt b \lt c \lt d$. 122 123 Secondly, if we delete ranges $(a,d)$ and $(b,c)$ where $a \lt b \lt c \lt d$, we must have deleted range $(b,c)$ before deleting range $(a,d)$. Yet, the effect of deleting range $(b,c)$ and then $(a,d)$ is the same as only deleting $(a,d)$. 124 125 Therefore, we can assume that in an optimal solution, the ranges we delete are all disjoint. Therefore, we want to find some disjoint range $[l_1,r_1],[l_2,r_2],...,[l_m,r_m]$ such that $a_{l_i}=a_{r_i}$ and $\sum (r_i-l_i+1)$ is maximized. 126 127 We can write a DP. $dp_i$ denotes the minimum number of points we do not delete when considering the subarray $a[1\ldots i]$. We have $dp_i=\min(dp_{i-1}+1,\min\{dp_j|a_{j+1}=a_i,j+1 \lt i\})$. 128 129 This dp can be calculated in $O(n)$ since we can store for each $x$ what the minimum $dp_j$ which satisfy $a_{j+1}=x$. 130 131 **Code** 132 133 ``` 134 #include <bits/stdc++.h> 135 136 using namespace std; 137 138 int main() { 139 ios::sync_with_stdio(false), cin.tie(nullptr); 140 int T; 141 cin >> T; 142 while (T--) { 143 const int N = 200000 + 5; 144 int n, a[N], dp[N], buc[N]; 145 cin >> n; 146 dp[0] = 0; 147 for (int i = 1; i <= n; i++) buc[i] = 0x3f3f3f3f; 148 for (int i = 1; i <= n; i++) { 149 cin >> a[i]; 150 dp[i] = min(dp[i - 1] + 1, buc[a[i]]); 151 buc[a[i]] = min(buc[a[i]], dp[i - 1]); 152 } 153 cout << n - dp[n] << '\n'; 154 } 155 } 156 ``` 157 158 ### [1842D - Tenzing and His Animal Friends](/contest/1842/problem/D) 159 160 **Tutorial** 161 162 Consider the restrictions on $u$, $v$, and $y$ as a weighted edge between $u$ and $v$ with weight $y$. Obviously, the final answer will not exceed the shortest path from $1$ to $n$. 163 164 One possible approach to construct the solution is to start with the set ${1}$ and add vertices one by one. If $i$ is added to the set at time $T_i$, then we need to ensure that $|T_u-T_v|\leq y$ for any edge between $u$ and $v$ in the set. This can be modeled as a system of difference constraints problem and solved using shortest path algorithms. 165 166 To be more specific, we can add vertices in increasing order of their distances from $1$. The time for each set can be calculated as the difference between the distances from $1$ to the two adjacent vertices in the sorted order. 167 168 **Code** 169 170 ``` 171 #include <bits/stdc++.h> 172 173 using namespace std; 174 175 int n, m; 176 long long dis[100][100]; 177 178 int main() { 179 ios::sync_with_stdio(false), cin.tie(nullptr); 180 cin >> n >> m; 181 memset(dis, 0x3f, sizeof dis); 182 while (m--) { 183 int u, v, w; 184 cin >> u >> v >> w, u--, v--; 185 dis[u][v] = dis[v][u] = w; 186 } 187 for (int i = 0; i < n; i++) dis[i][i] = 0; 188 for (int k = 0; k < n; k++) 189 for (int i = 0; i < n; i++) 190 for (int j = 0; j < n; j++) 191 dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]); 192 if (dis[0][n - 1] > 1e18) 193 cout << "inf", exit(0); 194 int ord[100]; 195 iota(ord, ord + n, 0); 196 sort(ord + 1, ord + n, [](int a, int b) { 197 return dis[0][a] < dis[0][b]; 198 }); 199 string s(n, '0'); 200 vector<pair<string, int>> ans; 201 for (int i = 0; i < n - 1; i++) { 202 int u = ord[i], v = ord[i + 1]; 203 s[u] = '1'; 204 ans.emplace_back(s, dis[0][v] - dis[0][u]); 205 if (v == n - 1) break; 206 } 207 cout << dis[0][n - 1] << ' ' << ans.size() << '\n'; 208 for (auto [s, t] : ans) 209 cout << s << ' ' << t << '\n'; 210 } 211 ``` 212 213 ### [1842E - Tenzing and Triangle](/contest/1842/problem/E) 214 215 **Tutorial** 216 217 Observe that all triangles will be disjoint, if two triangle were not disjoint, we can merge them together to such that the cost used is less. Therefore, we can consider doing DP. 218 219 The oblique side of the triangle is a segment on the line $y=k-x$. Therefore, we use the interval $[L,R]$ to represent the triangle with the upper left corner at $(L,k-L)$ and the lower right corner at $(R,k-R)$. 220 221 First, suppose that all points will generate costs. After covering points with a triangle, the costs can be reduced. Let $f(L,R)$ represent the sum of costs of points covered by triangle $[L,R]$ minus $A\times (R-L)$. We need to find several intervals $[l_1,r_1],[l_2,r_2],\cdots,[l_m,r_m]$ without common parts and maximize $\sum f(l_i,r_i)$. 222 223 Let $dp_i$ represent the maximum value of $\sum f(l_i,r_i)$ when considering the prefix $[1,i]$. There are two transitions: 224 225 * If $i$ is not covered by any interval, then $dp_i\leftarrow dp_{i-1}$. 226 * If $i$ is covered by interval $[j+1,i]$, then $dp_i\leftarrow dp_j+f(j+1,i)$. 227 228 Enumerate from small to large for $i$, maintain $g_j=dp_j+f(j+1,i)$. When $i-1\rightarrow i$, $g$ will change as follows: 229 230 * Subtract $A$ from $g_{0\dots i-1}$. 231 * For each point $(x,k-i)$, add the cost of the point to $g_{0\dots x}$. 232 233 $g$ needs to support interval addition and global maximum value (assuming that illegal positions are 0), which can be achieved using a segment tree. 234 235 Time complexity is $O((n+k)\log k)$. 236 237 **Alternative Solution** 238 239 Please first understand the approach in the tutorial. A triangle $[L, R]$ can cover a point $(x, y)$ iff $L\le x$ and $k-y\le R$. Therefore, point $(x,y)$ can be regarded as interval $[x,k-y]$. Now the problem is transformed into one where some intervals $[l,r]$ have a cost of $w$, and you can place some non-overlapping intervals. If $[l,r]$ is not included in any placed interval, then you need to pay a cost of $w$. Further transformation: you can pay a cost of $A$ to cover $[i,i+1]$, and for an interval $[l,r]$ with a cost of $w$, if interval $[l,r]$ is not completely covered, then you need to pay a cost of $w$. Try to use minimum cut to solve this problem: 240 241 * First establish a bipartite graph with $n$ left nodes representing the points in the original problem and $k$ right nodes representing intervals $[i,i+1]$. 242 * The source node is connected to each left node with an edge capacity equal to the node's cost. 243 * Each right node is connected to the sink node with an edge capacity of $A$. 244 * For each left node representing interval $[l,r]$, it is connected to right nodes $l,l+1,l+2,...,r-1$ with an edge capacity of infinity. 245 246 According to the maximum flow minimum cut theorem, let's consider how to find the maximum flow of this graph. 247 248 This is basically a maximum matching problem of a bipartite graph. Each left node can match an interval on the right side, and each node has matching frequency restriction. A greedy algorithm: First sort all intervals in increasing order of the right endpoint, then consider each interval in turn and match it with positions within the interval from left to right. Specifically, let $cnt_i$ represent how many times the $i$-th point on the right side can still be matched. Initially, $cnt_{0\dots k-1}=A$. For each interval $[l,r]$ that can be matched at most $w$ times, each time find the smallest $i$ in $[l,r-1]$ such that $cnt_i\ne 0$, and match $\min(cnt_i,w)$ times with $i$. 249 250 Use a Disjoint Set Union to query the smallest $i\ge l$ such that $cnt_i\ne 0$. The time complexity is $O(n\alpha(n))$. 251 252 The Method of Four Russians can also be used to achieve $O(n)$ time complexity. Divide the sequence into blocks of $64$, use bit operations and `__builtin_ctzll` for searching within the block, and use Disjoint Set Union to skip blocks where $cnt_i$ is all $0$. In this way, the union operation only needs $O(\frac n{\log n})$ times and the find operation only needs $O(n)$ times. It can be proved that in this case, the time complexity of Disjoint Set Union is $O(n)$ instead of $O(n\alpha(n))$. 253 254 **Code** 255 256 ``` 257 #include <bits/stdc++.h> 258 259 using namespace std; 260 261 const int N = 2e5 + 8, M = 1 << 18; 262 263 int n, k, A, c[M << 1][2], dp[N]; 264 vector<pair<int, int>> p[N]; 265 266 void insert(int i, int v) { 267 for (i += M; i; i >>= 1) c[i][0] = v, v = max(v, c[i ^ 1][0]); 268 } 269 void add(int i, int v) { 270 for (i += M + 1; i > 1; i >>= 1) { 271 int v1 = i & 1 ? v : 0; 272 c[i ^ 1][0] += v1, c[i ^ 1][1] += v1; 273 c[i >> 1][0] = max(c[i][0], c[i ^ 1][0]) + c[i >> 1][1]; 274 } 275 } 276 int main() { 277 ios::sync_with_stdio(false), cin.tie(nullptr); 278 cin >> n >> k >> A; 279 int sum = 0; 280 while (n--) { 281 int x, y, w; 282 cin >> x >> y >> w; 283 p[k - y].emplace_back(x, w); 284 sum += w; 285 } 286 for (int i = 1; i <= k; i++) { 287 add(i - 1, -A); 288 for (auto [x, w] : p[i]) add(x, w); 289 dp[i] = max(dp[i - 1], c[1][0]); 290 insert(i, dp[i]); 291 } 292 cout << sum - dp[k] << '\n'; 293 } 294 ``` 295 296 **Alternative Code O(n alpha n)** 297 298 ``` 299 #include <bits/stdc++.h> 300 301 using namespace std; 302 303 const int N = 2e5 + 8; 304 305 int n, k, A, cnt[N], pa[N]; 306 vector<pair<int, int>> v[N]; 307 308 int find(int x) { 309 return !pa[x] ? x : pa[x] = find(pa[x]); 310 } 311 int main() { 312 ios::sync_with_stdio(false), cin.tie(nullptr); 313 cin >> n >> k >> A; 314 while (n--) { 315 int x, y, w; 316 cin >> x >> y >> w; 317 v[k - y].emplace_back(x, w); 318 } 319 for (int i = 0; i < k; i++) cnt[i] = A; 320 int ans = 0; 321 for (int r = 1; r <= k; r++) 322 for (auto [l, w] : v[r]) 323 while (l < r) { 324 int tmp = min(w, cnt[l]); 325 ans += tmp, cnt[l] -= tmp, w -= tmp; 326 if (!cnt[l]) l = pa[l] = find(l + 1); 327 if (!w) break; 328 } 329 cout << ans << '\n'; 330 } 331 ``` 332 333 **Alternative Code O(n)** 334 335 ``` 336 #include <bits/stdc++.h> 337 338 struct IO { 339 static const int inSZ = 1 << 17; 340 char inBuf[inSZ], *in1, *in2; 341 inline __attribute((always_inline)) 342 int read() { 343 if(__builtin_expect(in1 > inBuf + inSZ - 32, 0)) { 344 auto len = in2 - in1; 345 memcpy(inBuf, in1, len); 346 in1 = inBuf, in2 = inBuf + len; 347 in2 += fread(in2, 1, inSZ - len, stdin); 348 if(in2 != inBuf + inSZ) *in2 = 0; 349 } 350 int res = 0; 351 unsigned char c = *in1++; 352 while(res = res * 10 + (c - 48), (c = *in1++) >= 48); 353 return res; 354 } 355 IO() { 356 in1 = inBuf; 357 in2 = in1 + fread(in1, 1, inSZ, stdin); 358 } 359 } IO; 360 inline int read() { return IO.read(); } 361 362 using namespace std; 363 364 const int N = 2e5 + 8, N2 = N / 64 + 8; 365 366 int n, k, A, pts[N][3], buc[N], LW[N][2]; 367 int cnt[N], pa[N2], Rp[N]; 368 uint64_t mask[N2]; 369 370 int find(int x) { 371 return pa[x] < 0 ? x : pa[x] = find(pa[x]); 372 } 373 374 int main() { 375 n = read(), k = read(), A = read(); 376 for (int i = 0; i < n; i++) { 377 pts[i][1] = read(); 378 pts[i][0] = k - read(); 379 pts[i][2] = read(); 380 buc[pts[i][0]]++; 381 } 382 for (int i = 1; i <= k; i++) buc[i + 1] += buc[i]; 383 for (int i = 0; i < n; i++) { 384 int t = --buc[pts[i][0]]; 385 memcpy(LW[t], pts[i] + 1, 8); 386 } 387 for (int i = 0; i < k; i++) cnt[i] = A; 388 memset(mask, 0xff, sizeof mask); 389 memset(pa, -1, sizeof pa); 390 iota(Rp, Rp + N2, 0); 391 int ans = 0; 392 for (int r = 1; r <= k; r++) 393 for (int i = buc[r]; i < buc[r + 1]; i++) { 394 int l = LW[i][0], w = LW[i][1]; 395 ans += w; 396 int lb = Rp[find(l >> 6)], rb = r >> 6; 397 auto S0 = mask[lb]; 398 if (lb == l >> 6) S0 &= ~0ULL << (l & 63); 399 while (lb < rb) { 400 auto S = S0; 401 for (; S; S &= S - 1) { 402 int p = lb * 64 + __builtin_ctzll(S); 403 int tmp = min(w, cnt[p]); 404 cnt[p] -= tmp, w -= tmp; 405 if (!w) break; 406 } 407 mask[lb] ^= S0 ^ S; 408 if (!w) break; 409 int nxt = find(lb + 1); 410 if (!mask[lb]) { 411 lb = find(lb); 412 if (pa[nxt] > pa[lb]) swap(nxt, lb), Rp[nxt] = Rp[lb]; 413 pa[nxt] += pa[lb], pa[lb] = nxt; 414 } 415 lb = Rp[nxt], S0 = mask[lb]; 416 } 417 if (w != 0 & lb == rb) { 418 S0 &= (1ULL << (r & 63)) - 1; 419 auto S = S0; 420 for (; S; S &= S - 1) { 421 int p = lb * 64 + __builtin_ctzll(S); 422 int tmp = min(w, cnt[p]); 423 cnt[p] -= tmp, w -= tmp; 424 if (!w) break; 425 } 426 mask[lb] ^= S0 ^ S; 427 } 428 ans -= w; 429 } 430 cout << ans << '\n'; 431 } 432 ``` 433 434 ### [1842F - Tenzing and Tree](/contest/1842/problem/F) 435 436 **Tutorial** 437 438 Let $root$ be the centroid of all black vertices and $size_i$ be the number of black vertices in the subtree of node $i$. 439 440 Then the value is $\sum_{i\neq root} k-2\cdot size_i=(n-1)\cdot k-2\cdot\sum_{i\neq root} size_i$. 441 442 Consider painting node $i$ black, the total contributio to all of its ancestors is $2\cdot depth_i$, where $depth_i$ is the distance from $root$ to $i$. 443 444 Since we want to maximize the value, we can greedily select the node with the smallest $depth_i$. 445 446 But how do we ensure that $root$ is the centroid after selecting other black vertices? We can simply take the maximum of all possible $root$ because if a node is not the centroid, some edges will have a negative weight, making it worse than the optimal answer. 447 448 Enumerate all possible $root$ and use BFS to add vertices based on their distance to $root$. The complexity is $O(n^2)$. 449 450 **Code** 451 452 ``` 453 #include <bits/stdc++.h> 454 455 using namespace std; 456 457 const int N = 5000 + 8; 458 459 int n, ans[N]; 460 vector<int> G[N]; 461 462 void bfs(int u) { 463 static int q[N], dis[N]; 464 memset(dis, -1, sizeof dis); 465 q[1] = u, dis[u] = 0; 466 for (int l = 1, r = 2; l < r; l++) { 467 u = q[l]; 468 for (int v : G[u]) if (dis[v] < 0) 469 dis[v] = dis[u] + 1, q[r++] = v; 470 } 471 int sum = 0; 472 for (int i = 1; i <= n; i++) { 473 sum += dis[q[i]]; 474 ans[i] = max(ans[i], (n - 1) * i - sum * 2); 475 } 476 } 477 int main() { 478 ios::sync_with_stdio(false), cin.tie(nullptr); 479 cin >> n; 480 for (int i = 0; i < n - 1; i++) { 481 int u, v; 482 cin >> u >> v, u--, v--; 483 G[u].push_back(v), G[v].push_back(u); 484 } 485 for (int i = 0; i < n; i++) bfs(i); 486 for (int i = 0; i <= n; i++) 487 cout << ans[i] << ' '; 488 } 489 ``` 490 491 ### [1842G - Tenzing and Random Operations](/contest/1842/problem/G) 492 493 **Tutorial** 494 495 Before starting to solve this problem, let's establish two basic properties: 496 497 * For two completely independent random variables $x_1,x_2$, we have $E(x_1x_2) = E(x_1)E(x_2)$. 498 * For $(a+b)\times (c+d)$, we have $E((a+b)\times (c+d)) = E(ac) + E(ad) + E(bc) + E(bd)$. 499 500 Returning to this problem, let $x_{i,j}$ be a random variable: its value is $v$ when the $i$-th operation sets $a_j$ to $a_j + v$, otherwise it is $0$. 501 502 Then note that the answer is the expected value of $\prod_{i=1}^{n}(a_i+\sum_{j=1}^{m}x_{j,i})$. 503 504 Applying the second property above to split the product, each term is a product of some $a_i$ and $x$. 505 506 Specifically, each term has $n$ factors, and for each $i\in [1,n]$, either $a_i$ is one of its factors, or some $x_{j,i}$ is one of its factors. 507 508 Let's investigate the expectation of a specific term. Note that if $i_1\lt i_2$, then $E(x_{j,i_1}\times x_{j,i_2}) = E(x_{j,i_1})\times v$, that is, if $x_{j,i_1}$ is $0$ then the whole product is $0$, and if $x_{j,i_1}$ is $v$ then $x_{j,i_2}$ must be $v$. 509 510 Therefore, for all the $x$ factors in a term, we categorize them by the first index, i.e. we group all $x_{j,...}$ into category $j$. For each category, we only need to focus on the first variable. If it's $v$, then the remaining variables take value $v$, otherwise the result is $0$. Note that the variables in different categories are completely independent (because their values are determined by operations in two different rounds), so the expected product of the variables in two categories can be split into the product of the expected products of the variables within each category. 511 512 Our goal is to compute the expected sum of all the terms, which can be nicely combined with DP: 513 514 Let $dp(i,j)$ be the value that we have determined the first $i$ factors of each term and there are $j$ categories that have appeared at least once (if adding the variable at position $i+1$ brings contribution $v$, otherwise the contribution is $\frac{i+1}{n}\times v$). The transition can be easily calculated with $O(1)$, depending on whether to append $a_{i+1}$ or $x_{...,i+1}$ to each term, and if it's the latter, we discuss whether the variable belongs to one of the $j$ categories that have appeared or the other $m-j$ categories. The time complexity is $O(n\times \min(n,m))$. 515 516 **Code** 517 518 ``` 519 #include <bits/stdc++.h> 520 521 using namespace std; 522 523 const int N = 5000 + 8, P = 1e9 + 7; 524 525 int n, m, v, a[N], coef[N], dp[N][N]; 526 527 long long Pow(long long a, int n) { 528 long long r = 1; 529 while (n) { 530 if (n & 1) r = r * a % P; 531 a = a * a % P, n >>= 1; 532 } 533 return r; 534 } 535 536 int main() { 537 ios::sync_with_stdio(false), cin.tie(nullptr); 538 cin >> n >> m >> v; 539 for (int i = 1; i <= n; i++) cin >> a[i]; 540 dp[0][0] = 1; 541 for (int i = 1; i <= n; i++) { 542 auto coef = i * Pow(n, P - 2) % P * v % P; 543 for (int j = 0; j < i; j++) { 544 dp[i][j + 1] = dp[i - 1][j] * coef % P * (m - j) % P; 545 dp[i][j] = (dp[i][j] + dp[i - 1][j] * (a[i] + 1LL * j * v % P)) % P; 546 } 547 } 548 int ans = 0; 549 for (int i = 0; i <= n; i++) 550 (ans += dp[n][i]) %= P; 551 cout << ans << '\n'; 552 } 553 ``` 554 555 ### [1842H - Tenzing and Random Real Numbers](/contest/1842/problem/H) 556 557 **Hint 1** 558 559 Ignoring time complexity for now, how do we calculate the answer? The first step is to enumerate which variables are $ \lt 0.5$ and which variables are $ \gt 0.5$. 560 561 **Hint 2** 562 563 Sort all variables $x_i$ by $\min(x_i,1-x_i)$ and enumerate the sorted result (referring to the permutation). 564 565 **Tutorial** 566 567 Suppose no variable equals $0.5$, because the probability of being equal to $0.5$ is $0$, variables less than $0.5$ are called white vertices, and those greater than $0.5$ are called black vertices. Each black and white coloring is equiprobable, so we can calculate the probability that satisfies all conditions for each black and white coloring, and then take the average. 568 569 For two variables less than $0.5$, the condition of $\le 1$ is always satisfied, and the condition of $\ge 1$ is never satisfied. Therefore, we do not need to consider the conditions between same-colored points. The condition between white vertex $u$ and black vertex $v$, $x_u+x_v\le 1$, is satisfied only when $x_u\le 1-x_v$. Let $y_u=\min(x_u,1-x_u)=\begin{cases}x_u&(u\text{ is white})\\1-x_u&(u\text{ is black})\end{cases}$, then $y_u$ can be regarded as a random variable in $[0,0.5)$, for $\le 1$ condition, the white vertex's $y$ must be less than or equal to the black vertex's $y$, so we add an edge from the white vertex to the black vertex; for $\ge 1$ condition, we add an edge from the black vertex to the white vertex. 570 571 We get a directed graph that restricts the size relationship of $y_{1\cdots n}$. Suppose that sorting $y_{1\cdots n}$ from small to large is $y_{p_1},y_{p_2},\cdots,y_{p_n}$, then each permutation $p$ is equiprobable, and this $p$ contributes if and only if it is a topological sort, so the probability that satisfies all conditions is the number of topological sorts divided by $n!$. 572 573 Now the problem has been transformed into a counting problem. For each coloring, count the total number of topological sorts. Now we do not enumerate coloring directly but enumerate topological sorts directly by enumerating a permutation $p$ such that $y_{p_1} \lt y_{p_2} \lt \cdots \lt y_{p_n}$ and count the number of colorings that satisfy the conditions. It can be found that $\le 1$ condition limits variablesin in the front position of $p$ to be less than $0.5$, and $\ge 1$ condition limits variables in the front position of $p$ to be greater than $0.5$. 574 575 Then we can use bit-mask DP. Let $dp_{mask}$ represent that we have added all vertices in mask into topological sort. We enumerate new added vertex u for transition. If all variables with $\le 1$ conditions between it are included in mask, it can be colored black; if all variables with $\ge 1$ conditions between it are included in mask, it can be colored white. 576 577 Time complexit is $O(2^nn)$. 578 579 **Code** 580 581 ``` 582 #include <iostream> 583 584 const int P = 998244353; 585 586 long long Pow(long long a, int n) { 587 long long r = 1; 588 while (n) { 589 if (n & 1) r = r * a % P; 590 a = a * a % P, n >>= 1; 591 } 592 return r; 593 } 594 inline void inc(int& a, int b) { 595 if((a += b) >= P) a -= P; 596 } 597 598 int n, m, G[20][2], f[1 << 20]; 599 600 int main() { 601 std::cin >> n >> m; 602 while (m--) { 603 int t, i, j; 604 std::cin >> t >> i >> j; 605 i--, j--; 606 G[i][t] |= 1 << j; 607 G[j][t] |= 1 << i; 608 } 609 f[0] = 1; 610 for (int S = 0; S < 1 << n; S++) 611 for (int i = 0; i < n; i++) if (~S >> i & 1) { 612 if ((G[i][0] | S) == S) inc(f[S | 1 << i], f[S]); 613 if ((G[i][1] | S) == S) inc(f[S | 1 << i], f[S]); 614 } 615 long long t = 1; 616 for (int i = 1; i <= n; i++) t = t * i * 2 % P; 617 std::cout << f[(1 << n) - 1] * Pow(t, P - 2) % P << '\n'; 618 } 619 ``` 620 621 ### [1842I - Tenzing and Necklace](/contest/1842/problem/I) 622 623 **Hint 1** 624 625 How to solve it if you want to cut exactly $m$ edges ? 626 627 **Hint 2** 628 629 DP+divide and conquer 630 631 **Tutorial** 632 633 Add a constraint: "you must cut off $m$ edges". 634 635 Consider enumerating the minimum cut edges from small to large. 636 637 Suppose the minimum cut edge chosen is $a_1$, and the subsequent optimal solution is $a_2, a_3, ..., a_m$. 638 639 If another minimum cut edge is selected: $b_1$, and the subsequent optimal solution is $b_2, b_3, ..., b_m$. 640 641 Assume that $a_i \lt a_{i+1}, b_i \lt b_{i+1}, b_1 \gt a_1$. 642 643 #### 1. It is possible to only adjust $b_2,b_3, ..., b_m$, so that $\forall_{1\leq i\leq m} b_i\geq a_i$, and the total cost after adjustment remains unchanged. 644 645 The adjustment method is as follows: 646 647 Find the smallest $i$ such that $b_i \lt a_i$, and find the first $j$ such that $b_j\geq a_j$ after $i$, if it does not exist, let $j=m+1$. 648 649 It can be observed that $(b_i,b_{i+1},b_{i+2},...,b_{j-1})$ can be replaced with $(a_i,a_{i+1},a_{i+2},...,a_{j-1})$, which is still a valid solution. Moreover, the solution $(a_i,a_{i+1},a_{i+2},...,a_{j-1})$ can also be replaced with $(b_i,b_{i+1},b_{i+2},...,b_{j-1})$, because $b_{i-1}\geq a_{i-1}$ and $b_j\geq a_j$. 650 651 Since $a$ and $b$ are both optimal solutions with fixed $a_1$ and $b_1$, $w_{b_i}+w_{b_{i+1}}+...+w_{b_{j-1}}=w_{a_i}+w_{a_{i+1}}+...+w_{a_{j-1}}$. Therefore, replacing $(b_i,b_{i+1},b_{i+2},...,b_{j-1})$ with $(a_i,a_{i+1},a_{i+2},...,a_{j-1})$ does not increase the total cost. 652 653 Repeat the above adjustment until there is no $b_i \lt a_i$. 654 655 Similarly, it can be proven that only adjusting $a_2,a_3,...,a_m$ is feasible, so that $\forall_{1\leq i\leq m} b_i\geq a_i$, and the total cost after adjustment remains unchanged. 656 657 #### 2. If $\forall_{1\leq i\leq m} b_i\geq a_i$ is already satisfied, it is possible to only adjust $b_2,b_3, ..., b_m$, so that $\forall_{1\leq i \lt m}a_i\leq b_i\leq a_{i+1}$, and the total cost after adjustment remains unchanged. Assume that $a_1 \lt b_1\leq a_2$. 658 659 The adjustment method is as follows: 660 661 Find the smallest $i$ such that $b_i \gt a_{i+1}$, and find the first $j$ such that $b_j\leq a_{j+1}$ after $i$ (let $a_{m+1}=+\infty$). 662 663 $(b_i,b_{i+1},b_{i+2},...,b_{j-1})$ can be replaced with $(a_{i+1},a_{i+2},a_{i+3},...,a_{j})$, which is still a valid solution. Moreover, the solution $(a_{i+1},a_{i+2},a_{i+3},...,a_{j})$ can also be replaced with $(b_i,b_{i+1},b_{i+2},...,b_{j-1})$, because $b_{i-1}\leq a_{i}$ and $b_j\leq a_{j+1}$. 664 665 Since $a$ and $b$ are both optimal solutions with fixed $a_1$ and $b_1$, $w_{b_i}+w_{b_{i+1}}+...+w_{b_{j-1}}=w_{a_{i+1}}+w_{a_{i+2}}+...+w_{a_j}$. Therefore, replacing $(b_i,b_{i+1},b_{i+2},...,b_{j-1})$ with $(a_{i+1},a_{i+2},a_{i+3},...,a_{j})$ does not increase the total cost. 666 667 Similarly, it can be proven that only adjusting $a_2,a_3,...,a_m$ is feasible, so that $\forall_{1\leq i \lt m}a_i\leq b_i\leq a_{i+1}$, and the total cost after adjustment remains unchanged. 668 669 #### 3. If $b_1 \gt a_2$, it is possible to adjust $b_1,b_2,...,b_m$, so that $b_1\leq a_2$, and the total cost does not increase. 670 671 The adjustment method is as follows: 672 673 Find the smallest $j$ such that $b_j\leq a_{j+1}$ (let $a_{m+1}=+\infty$). 674 675 It can be observed that $(a_{2},a_{3},a_{4},...,a_{j})$ can be replaced with $(b_1,b_{2},b_{3},...,b_{j-1})$, which is still a valid solution. Moreover, the solution $(b_1,b_{2},b_{3},...,b_{j-1})$ can also be replaced with $(a_{2},a_{3},a_{4},...,a_{j})$, because $b_j\leq a_{j+1}$. 676 677 Since $a$ is the optimal solution with fixed $a_1$ and $b_1$, $w_{b_1}+w_{b_{2}}+...+w_{b_{j-1}}\geq w_{a_{2}}+w_{a_{3}}+...+w_{a_j}$. Therefore, replacing $(b_1,b_{2},b_{3},...,b_{j-1})$ with $(a_{2},a_{3},a_{4},...,a_{j})$ does not increase the total cost. 678 679 --- 680 681 Combining the above conclusions, we can obtain a solution that must cut off $m$ edges: 682 683 Let $a_1=1$, find the optimal solution $a_1,a_2,a_3,...,a_m$. 684 685 Then, it can be assumed that all $b_i$ satisfy $a_i\leq b_i\leq a_{i+1}$. 686 687 A divide-and-conquer algorithm can be used. Let $solve((l_1,r_1),(l_2,r_2),(l_3,r_3),...,(l_m,r_m))$ represent the optimal solution for all $l_i\leq b_i\leq r_i$. 688 689 If $l_1 \gt r_1$, then we are done. Otherwise, let $x=\lfloor\frac{l_1+r_1}{2}\rfloor$, we can use DP to calculate the cost and solution for $b_1=x$ in $O(\sum r_i-l_i+1)$ time complexity. Then, recursively calculate $solve((l_1,b_1-1),(l_2,b_2),(l_3,b_3),...,(l_m,b_m))$ and $solve((b_1+1,r_1),(b_2,r_2),(b_3,r_3),...,(b_m,r_m))$. 690 691 Time complexity analysis: $\sum r_i-l_i+1=(\sum r_i-l_i)+m$. If the sum of adjacent parts is $\leq k$, it can be merged, but it is definitely not the optimal solution. Therefore, $m\leq 2\lceil\frac{n}{k}\rceil$. Assuming that the length of the first segment is $r_1-l_1+1=O(k)$, the time complexity is $O(n\log k+mk)=O(n\log k)$. 692 693 Finally, we need to calculate the solution for all possible $m$ and take the $\min$ as the final answer. After pruning the first edge, if the optimal solution requires cutting off $m'$ edges, similar to the previous proof, other solutions can be adjusted to satisfy $|m-m'|\leq 1$ and the total cost does not increase. 694 695 **Code** 696 697 ``` 698 #include <bits/stdc++.h> 699 700 using namespace std; 701 702 const int N = 5e5 + 8; 703 704 int n, K, a[N], pre[N * 2]; 705 long long dp[N * 2], ans; 706 707 vector<int> trim(vector<int> a, int L, int R) { 708 return vector(a.begin() + L, a.end() - R); 709 } 710 vector<int> init() { 711 static int q[N]; 712 q[1] = 0; 713 for (int i = 1, l = 1, r = 1; i <= n; i++) { 714 if (q[l] < i - K) l++; 715 dp[i] = dp[q[l]] + a[i], pre[i] = q[l]; 716 while (l <= r && dp[i] < dp[q[r]]) r--; 717 q[++r] = i; 718 } 719 ans = dp[n]; 720 vector<int> res; 721 for (int i = n; i; i = pre[i]) res.push_back(i); 722 res.push_back(0), reverse(res.begin(), res.end()); 723 return res; 724 } 725 vector<int> solve(int first, vector<int> L, vector<int> R) { 726 dp[first] = a[first]; 727 int l = first, r = first; 728 long long val; int p; 729 auto checkMin = [&](int i) { 730 if (dp[i] < val) val = dp[i], p = i; 731 }; 732 for (int i = 0; i < L.size(); i++) { 733 val = 1e18, p = 0; 734 for (int j = R[i]; j >= L[i]; j--) { 735 for (; r >= max(l, j - K); r--) checkMin(r + i); 736 dp[j + i + 1] = val + a[j]; 737 pre[j + i + 1] = p; 738 } 739 l = L[i], r = R[i]; 740 } 741 val = 1e18, p = 0; 742 for (int i = max(L.back(), n - K + first); i <= R.back(); i++) 743 checkMin(i + L.size()); 744 ans = min(ans, val); 745 vector<int> res; 746 for (int i = L.size(); i; i--) res.push_back(p - i), p = pre[p]; 747 reverse(res.begin(), res.end()); 748 return res; 749 } 750 void divide(int l, int r, vector<int> L, vector<int> R) { 751 if (l > r) return; 752 int mid = (l + r) >> 1; 753 auto M = solve(mid, L, R); 754 divide(l, mid - 1, L, M), divide(mid + 1, r, M, R); 755 } 756 void divide(vector<int> p) { 757 p.push_back(n), divide(1, p[0], trim(p, 0, 1), trim(p, 1, 0)); 758 } 759 int main() { 760 ios::sync_with_stdio(false), cin.tie(nullptr); 761 int T; 762 cin >> T; 763 while (T--) { 764 cin >> n >> K; 765 for (int i = 1; i <= n; i++) cin >> a[i]; 766 a[0] = a[n]; 767 auto p = init(); 768 divide(trim(p, 1, 1)); 769 divide(solve(0, trim(p, 0, 1), trim(p, 1, 0))); 770 if ((p.size() - 2) * K >= n) 771 divide(solve(0, trim(p, 1, 2), trim(p, 2, 1))); 772 cout << ans << '\n'; 773 } 774 } 775 ```