codeforces-scrape

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

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 ```