2228.md (28617B)
1 Source: https://codeforces.com/blog/entry/153619 2 3 Thank you for helping Marisa, Reimu, Cirno, Sanae, Amanojaku and Momoyo! 4 5 **Leave a comment!** 6 7 Excellent contest 8 9 Good contest 10 11 Average contest 12 13 Bad contest 14 15 Terrible contest 16 17 #### [2228A - Marisa Steals Reimu's Takeout](/contest/2228/problem/A "Codeforces Round 1098 (Div. 2)") 18 19 Author: [Sanae](/profile/Sanae "International Master Sanae") 20 21 Solution: [Sanae](/profile/Sanae "International Master Sanae") 22 23 **Step 1** 24 25 **Lemma 1.** There exists an optimal solution in which each zero is divided separately. 26 27 *Proof.* Suppose in some optimal solution, a zero is grouped with other elements. Separating it into a singleton group does not decrease the total score. Hence, we can transform any optimal solution into one where all zeros are divided separately without worsening the objective. $\blacksquare$ 28 29 Therefore, we can restrict our attention to the subsequence consisting only of $1$s and $2$s. 30 31 **Step 2** 32 33 **Lemma 2.** There exists an optimal solution in which any group containing both $1$ and $2$ is exactly either $[1,2]$ or $[2,1]$. 34 35 *Proof.* Consider a group that contains $1$, $2$, and possibly other elements. Splitting it into $[1,2]$ (or $[2,1]$) and the remaining part does not decrease the total score. Consequently, we can transform any optimal solution into the desired form. $\blacksquare$ 36 37 By Lemma 2, we can greedily extract all $[1,2]$ or $[2,1]$ pairs from the remaining sequence. 38 39 **Step 3** 40 41 Finally, for the leftover elements, the best strategy is clearly to take triplets $[1,1,1]$ and $[2,2,2]$ whenever possible. 42 43 #### [2228B - Remilia Plays Soku](/contest/2228/problem/B "Codeforces Round 1098 (Div. 2)") 44 45 Author: [Sanae](/profile/Sanae "International Master Sanae") 46 47 Solution: [Sanae](/profile/Sanae "International Master Sanae") 48 49 **Solution** 50 51 We assume $n\geq 4$ in what follows. 52 53 Let us analyze the strategies of both players. Reimu aims to get as close to Remilia as possible, while Remilia aims to get as far away from Reimu as possible. Remilia will use her moves to increase the distance without being caught, and indeed it is optimal for her to use as many moves as possible. 54 55 The distance on the circle can be measured with $d=min(|x_1-x_2|,n-|x_1-x_2|)$. Once $d=1$, Remilia can increase $d$ by $1$ since the circle is large enough ($n\geq 4$). Similarly, Reimu can decrease $d$ by $1$ each turn. 56 57 Therefore, we can calculate the outcome directly. The answer is the initial distance plus the extra time gained by Remilia's moves, $min(|x_1-x_2|,n-|x_1-x_2|)+k$. 58 59 Note that when $n\leq 3$, the answer is always $1$, because Reimu can always catch Remilia in one step. 60 61 #### [2228C1 - Cirno and Number (Easy Version)](/contest/2228/problem/C1 "Codeforces Round 1098 (Div. 2)") and [2228C2 - Cirno and Number (Hard Version)](/contest/2228/problem/C2 "Codeforces Round 1098 (Div. 2)") 62 63 Author: [Sanae](/profile/Sanae "International Master Sanae"), [Sugar_fan](/profile/Sugar_fan "International Grandmaster Sugar_fan") 64 65 Solution: [Sanae](/profile/Sanae "International Master Sanae"), [Sugar_fan](/profile/Sugar_fan "International Grandmaster Sugar_fan") 66 67 **Solution** 68 69 The case $a=b$ is trivial. We consider two cases separately: $a \gt b$ and $a \lt b$. 70 71 We first discuss $a \lt b$ in what follows. Consider the longest common prefix of $a$ and $b$, scanning from the highest digit to the lowest significant digit. Let $x$ be the digit of $a$ be at that position and $y$ be the digit of $b$ be at that position. If $d_n \gt x$, choose $y$ as the smallest $d_i$ such that $d_i \gt x$. Then set the digits beneath in $b$ to $d_1$. This guarantees that $b$ is the smallest number greater than $a$ and the decimal representation of $b$ contains only digits from $d$. Otherwise, if $d_n \lt x$,we should change an earlier digit to satisfy the inequality. Note that **we can make the number of digits in $b$ more than $a$.** 72 73 Similarly, we assume $a \gt b$. Consider the longest common prefix of $a$ and $b$, scanning from the highest digit to the lowest significant digit. Let $x$ be the digit of $a$ be at that position and $y$ be the digit of $b$ be at that position. If $d_1 \lt x$, choose $y$ as the largest $d_i$ such that $d_i \lt x$. Then set the digits beneath in $b$ to $d_n$. This guarantees that $b$ is the largest number smaller than $a$ and the decimal representation of $b$ contains only digits from $d$. Otherwise, if $d_1 \gt x$,we should change an earlier digit to satisfy the inequality. Note that **if $d=[1,2,3]$, then $b=0$ is invalid, because $0$ dosn't belongs to $d$.** 74 75 Depending on the implementation, the time complexity can be $O(10n\log a)$, $O(10n\log^2 a)$, $O(n\log a)$ or $O(n\log^2 a)$. 76 77 #### [2228D - Sanae, Cross and Color](/contest/2228/problem/D "Codeforces Round 1098 (Div. 2)") 78 79 Author: [Sanae](/profile/Sanae "International Master Sanae") 80 81 Solution: [Sanae](/profile/Sanae "International Master Sanae"), [fanhuaxingyu](/profile/fanhuaxingyu "Candidate Master fanhuaxingyu") 82 83 **Solution 1** 84 85 We can apply the principle of inclusion--exclusion to compute the answer. First, enumerate a vertical dividing line at integer coordinate $x$ from $1$ to $n$; the contribution is recalculated only when the set of points on the left side changes ~---otherwise, we skip redundant computations. 86 87 For each such $x$, we then enumerate a horizontal dividing line at integer $y$ from $1$ to $n$, while carefully excluding overlapping cases to avoid double-counting. Let the y-coordinates of the points on the left side be ${y_1,y_2,\dots,y_k}$, sorted in increasing order. For consecutive y-values $y_i$ and $y_{i+1}$, all values in the form $k+0.5$ in the interval $(y_i+0.5,\;y_{i+1}-0.5)$ give the same left-side point set. Thus, the left side produces a set of y-intervals, and similarly, the right side also forms a set of y-intervals. To count all valid configurations, we need to count the number of interval-pairs (one interval from the left, one from the right) that intersect in at least one point. This can be computed efficiently using a Fenwick tree (Binary Indexed Tree) and a set data structure. 88 89 The overall time complexity is $O(n\log n)$. 90 91 **Solution 2** 92 93 An observation is that any valid dividing line must cross at least one of the two groups determined by the smaller y-coordinate. 94 95 Suppose the line crosses the group with smaller $x$ and smaller $y$. Enumerate the point whose $y$-coordinate is maximal within this group (and among those with the same maximal $y$, take the one with the larger $x$). Using appropriate pre-computation, we can efficiently determine the feasible vertical dividing position $x$. 96 97 The case where the line crosses the group with larger $x$ but smaller $y$ is symmetric to the above. 98 99 The overall time complexity is $O(n)$. 100 101 #### [2228E1 - Amanojaku and Sequence (Easy Version)](/contest/2228/problem/E1 "Codeforces Round 1098 (Div. 2)") and [2228E2 - Amanojaku and Sequence (Hard Version)](/contest/2228/problem/E2 "Codeforces Round 1098 (Div. 2)") 102 103 Author: [Sanae](/profile/Sanae "International Master Sanae") 104 105 Solution: [Sanae](/profile/Sanae "International Master Sanae") 106 107 Tutorial: [CirnoNine](/profile/CirnoNine "International Master CirnoNine"), [fanhuaxingyu](/profile/fanhuaxingyu "Candidate Master fanhuaxingyu") 108 109 **Sanae's Solution** 110 111 First, consider solving the whole array. We can first compute the total number of possible configurations of $a$ using stars and bars. Let this number be $tot$. The remaining sum to be freely distributed is $sum= m - \sum_{i} a_i[a_i\neq -1]$, and the number of undetermined positions is $cnt=\sum_{i} [a_i = -1]$. It is obvious $tot=\binom{sum+cnt-1}{cnt-1}$. We adopt the convention $\binom{-1}{-1}=1$ to simplify boundary cases. 112 113 $ \begin{aligned} g(a,m)= {} & \sum_{b \text{ is valid}}\sum_{1\leq i \leq n}(\sum_{1\leq j\leq i}b_j)^2\\ = & \sum_{b \text{ is valid}}\sum_{1\leq i \leq n}\sum_{1\leq j\leq n}b_ib_j (n+1-\max(i,j))\\ = & 2\sum_{b \text{ is valid}}\sum_{1\leq i \lt j\leq n}b_ib_j (n+1-j)\\ &\quad + \sum_{b \text{ is valid}}\sum_{1\leq i \leq n}b_i^2 (n+1-i))\\ \end{aligned} $ 114 115 Denote $S_1=2\sum_{b \text{ is valid}}\sum_{1\leq i \lt j\leq n}b_ib_j (n+1-j)$ and $S_2=\sum_{b \text{ is valid}}\sum_{1\leq i \leq n}b_i^2 (n+1-i))$. We should compute each part individually. 116 117 To do the computation, we need to first introduce some useful math conclusions. We give the $T_0,T_1,T_2$. 118 119 We recall the following standard combinatorial identities: \begin{enumerate} \item If $n\geq 0$, then $\binom{n}{m}=\binom{n}{n-m}$ 120 121 \item For any $n,m$,then $m\binom{n}{m}=n\binom{n-1}{m-1}$ 122 123 \item If $n,m\geq 0$, then $n\binom{n+m}{n}=(m+1)\binom{n+m}{m+1}$ \end{enumerate} 124 125 The $T_0$ is classic,while $T_1,T_2$ need some work. 126 127 $ \begin{aligned} T_0(n,m) = &\sum_{x=0}^n \binom{x+m}{m}\\ = & \binom{n+m+1}{m+1} \end{aligned} $ 128 129 The computation of $T_1$ is straightforward. 130 131 $ \begin{equation} \begin{aligned} T_1(n,m) = & \sum_{x=0}^n x\binom{x+m}{m}\\ = & \sum_{x=0}^n x\binom{x+m}{m}\\ = & \sum_{x=0}^n x\binom{x+m}{x}\\ = & \sum_{x=0}^n (m+1)\binom{x+m}{m+1}\\ = & (m+1)\binom{n+m+1}{m+2}\\ \end{aligned} \end{equation} $ 132 133 Similarly, we compute $T_2$: 134 135 $ \begin{equation} \begin{aligned} T_2(n,m) = {}&\sum_{x=0}^n x^2\binom{x+m}{m}\\ = & \sum_{x=1}^n (m+1)x\binom{x+m}{m+1}\\ = & (m+1)\sum_{x=0}^{n-1} (x+1)\binom{x+m+1}{m+1}\\ = & (m+1)(m+2)\binom{n+m+1}{m+3}+(m+1)\binom{n+m+1}{m+2}\\ \end{aligned} \end{equation} $ 136 137 We now derive $T_3$: 138 139 $ \begin{aligned} T_3(n,m) &= {}\sum_{x=0}^n x^3\binom{x+m}{m}\\ &= \sum_{x=1}^n (m+1)x^2\binom{x+m}{m+1}\\ &= (m+1)\sum_{x=0}^{n-1} (x+1)^2\binom{x+m+1}{m+1}\\ 140 141 &= (m+1)(\sum_{x=0}^{n-1} x^2\binom{x+m+1}{m+1}+2\sum_{x=0}^{n-1} x\binom{x+m+1}{m+1}+\sum_{x=0}^{n-1} \binom{x+m+1}{m+1})\\ &= (m+1)(T_2(n-1,m+1)+2T_1(n-1,m+1)+T_0(n-1,m+1)) \\\\ &\quad \text{Note: It can be further simplified, but we can just stop here.} \end{aligned} $ 142 143 We first deal with $S_2$.$S_2=\sum_{1\leq i \leq n}\sum_{b \text{ is valid}}b_i^2 (n+1-i))$.If $a_i\geq 0$, $b_i=a_i$, so the formula can be written like $a_i^2(n+1-i) tot$. If $a_i=-1$,the formula can be written like 144 145 $ \begin{aligned} &(n-i+1)\sum_{x=0}^{sum}x^2\binom{sum-x+cnt-2}{cnt-2}\\ =&(n-i+1)\sum_{x=0}^{sum} (sum-x)^2\binom{x+cnt-2}{cnt-2}\\ =&(n-i+1)(T_2(sum,cnt-2)-2sum\cdot T_1(sum,cnt-2)+sum^2\cdot T_0(sum,cnt-2)) \end{aligned} $ 146 147 Second, we cope with $S_1$. 148 149 $S_1=2\sum_{b \text{ is valid}}\sum_{1\leq i \lt j\leq n}b_ib_j (n+1-j)$ 150 151 After selecting $i,j$, we only need to compute $\sum_{b \text{ is valid}}b_ib_j$. 152 153 There are three cases: 154 155 \begin{enumerate} \item $a_i\neq -1 \text{ and } a_j\neq -1$. 156 157 $\sum_{b \text{ is valid}}b_ib_j=tot\cdot a_ia_j$ 158 159 \item $a_i\neq -1 \text{ and } a_j = -1$, $a_i\neq -1 \text{ and } a_j = -1$. 160 161 It remains to consider $a_i\neq -1 \text{ and } a_j = -1$, because another case is similar. 162 163 $ \begin{aligned} &\sum_{b \text{ is valid}}b_ib_j\\ =&\sum_{b_j=0}^{sum}a_ib_j\binom{sum-b_j+cnt-2}{cnt-2}\\ =&a_i\sum_{b_j=0}^{sum}(sum-b_j)\binom{b_j+cnt-2}{cnt-2}\\ =&a_i(sum\binom{sum+cnt-1}{cnt-1}-\sum_{b_j=0}^{sum}b_j\binom{b_j+cnt-2}{cnt-2})\\ =&a_i(sum\binom{sum+cnt-1}{cnt-1}-(cnt-1)\binom{sum+cnt-1}{cnt})\\ =&a_i\frac{sum\binom{sum+cnt-1}{cnt-1}}{cnt}\\ \end{aligned} $ 164 165 It can also be computed by the expectation of each position. 166 167 \item $a_i = -1 \text{ and } a_j = -1$. 168 169 It is the trickiest part of the solution. We analyze this case carefully. 170 171 $ \begin{aligned} &\sum_{b \text{ is valid}}b_ib_j\\ =&\sum_{b_i=0}^{sum}\sum_{b_j=0}^{sum}[b_i+b_j\leq sum]b_ib_j\binom{sum-b_i-b_j+cnt-3}{cnt-3}\\ =&\sum_{s=b_i+b_j=0}^{sum}(\sum_{b_j=0}^{s}b_i(s-b_i))\binom{sum-s+cnt-3}{cnt-3}\\ =&\sum_{s=b_i+b_j=0}^{sum}\frac{s^3-s}{6}\binom{sum-s+cnt-3}{cnt-3}\\ =&\frac{1}{6}(\sum_{s=0}^{sum}s^3\binom{sum-s+cnt-3}{cnt-3}-\sum_{s=0}^{sum}s\binom{sum-s+cnt-3}{cnt-3})\\ =&\frac{1}{6}(\sum_{s=0}^{sum}(sum-s)^3\binom{s+cnt-3}{cnt-3}-\sum_{s=0}^{sum}(sum-s)\binom{s+cnt-3}{cnt-3})\\ =&\frac{1}{6}(\sum_{s=0}^{sum}(sum^3-3s\cdot sum^2+3s^2\cdot sum - s^3)\binom{s+cnt-3}{cnt-3}\\ &\quad -sum\cdot T_0(sum,cnt-3)+T_1(sum,cnt-3))\\ =&\frac{1}{6}(sum^3\cdot T_0(sum,cnt-3)-3sum^2\cdot T_1(sum,cnt-3)+3sum\cdot T_2(sum,cnt-3)-T_3(sum,cnt-3)\\ &\quad -sum\cdot T_0(sum,cnt-3)+T_1(sum,cnt-3))\\ \end{aligned} $ 172 173 It is just a constant, which is easy to compute. 174 175 \end{enumerate} 176 177 Then, it is time to cope with $S_1$. 178 179 $S_1=2\sum_{b \text{ is valid}}\sum_{1\leq i \lt j\leq n}b_ib_j (n+1-j)$ 180 181 For type $1$, it suffices to compute 182 183 $\sum_{1\leq i \lt j\leq n}a_ia_j[a_i\neq -1 \text{ and } a_j\neq -1](n-j+1)$ 184 185 . 186 187 For type $2$, it suffices to compute 188 189 $\sum_{1\leq i \lt j\leq n}a_i[a_i\neq -1 \text{ and } a_j = -1](n-j+1)+a_j[a_i= -1 \text{ and } a_j \neq -1](n-j+1)$ 190 191 . 192 193 For type $3$, it suffices to compute 194 195 $\sum_{1\leq i \lt j\leq n}[a_i= -1 \text{ and } a_j = -1](n-j+1)$ 196 197 . 198 199 All required quantities can be maintained using a segment tree, and the interval queries and modifications can be processed easily. Note that $n-j+1=(n+1)-j$. So process $X \cdot(n+1)$ and $X \cdot j$ in two data structures. Implementation details are omitted for brevity; see the accompanying code. 200 201 By querying on the tree, we can get the answer. And the information can also be modified efficiently. 202 203 After all, we can solve the problem in the total time complexity $O(1\ 000\ 000)-O((n+q)\log n)$ and total space complexity $O(1\ 000\ 000+n)$. 204 205 Note $\binom{-1}{-1}=1$ in the code. 206 207 **CirnoNine's Solution** 208 209 For a fixed query interval, denote it by $b_1,b_2,\ldots,b_L$. 210 211 Define 212 213 $A_i=\sum_{j=1}^{i} b_j[b_j\ge 0]$ 214 215 and 216 217 $T_i=\sum_{j=1}^{i} [b_j=-1]$ 218 219 Here, $A_i$ is the prefix sum contributed by fixed positions, and $T_i$ is the number of free positions in the first $i$ elements. 220 221 Let 222 223 $S=\sum_{i:b_i\ge 0} b_i,\qquad k=\#\{i\mid b_i=-1\}$ 224 225 The total value that must be assigned to all free positions is 226 227 $N=m-S$ 228 229 If $N \lt 0$, there is no valid sequence, so the answer is $0$. 230 231 If $k=0$, there is only one possible sequence. The answer is $\sum_i A_i^2$ if $N=0$, and $0$ otherwise. 232 233 Now assume $k \gt 0$ and $N\ge 0$. 234 235 Let the values assigned to the $k$ free positions be 236 237 $x_1,x_2,\ldots,x_k$ 238 239 where 240 241 $x_1+x_2+\cdots+x_k=N,\qquad x_i\ge 0$ 242 243 The number of such assignments is 244 245 $C=\binom{N+k-1}{k-1}$ 246 247 For prefix $i$, there are exactly $T_i$ free positions inside it. Therefore, the contribution of assigned values to this prefix is 248 249 $X_{T_i}=x_1+x_2+\cdots+x_{T_i}$ 250 251 So the real prefix sum at position $i$ is 252 253 $A_i+X_{T_i}$ 254 255 Therefore, we need to calculate 256 257 $\sum_{\text{valid }x}\sum_{i=1}^{L}(A_i+X_{T_i})^2$ 258 259 Expanding the square gives 260 261 $(A_i+X_{T_i})^2=A_i^2+2A_iX_{T_i}+X_{T_i}^2$ 262 263 Now we calculate these three parts separately. 264 265 First, consider the $A_i^2$ part. 266 267 Since $A_i$ does not depend on the assignment, every valid assignment contributes the same value. Hence this part contributes 268 269 $C\sum_i A_i^2$ 270 271 Second, consider the $2A_iX_{T_i}$ part. 272 273 By symmetry, among all weak compositions of $N$ into $k$ parts, every variable has the same total contribution. Thus 274 275 $\sum_{\text{valid }x}x_j=C\cdot\frac{N}{k}$ 276 277 Therefore, 278 279 $\sum_{\text{valid }x}X_t=C\cdot\frac{Nt}{k}$ 280 281 Substituting $t=T_i$, we get 282 283 $\sum_{\text{valid }x}2A_iX_{T_i}=C\cdot\frac{2N}{k}A_iT_i$ 284 285 After summing over all $i$, this part contributes 286 287 $C\cdot\frac{2N}{k}\sum_i A_iT_i$ 288 289 Third, consider the $X_{T_i}^2$ part. 290 291 We need the second moment of 292 293 $X_t=x_1+x_2+\cdots+x_t$ 294 295 For all weak compositions of $N$ into $k$ parts, we have 296 297 $\sum_{\text{valid }x}x_p(x_p-1)=C\cdot\frac{2N(N-1)}{k(k+1)}$ 298 299 and for $p\ne q$, 300 301 $\sum_{\text{valid }x}x_px_q=C\cdot\frac{N(N-1)}{k(k+1)}$ 302 303 Since 304 305 $X_t^2=\sum_{p=1}^{t}x_p^2+2\sum_{1\le p \lt q\le t}x_px_q$ 306 307 we get 308 309 $\sum_{\text{valid }x}X_t^2=C\left(\frac{N}{k}t+\frac{N(N-1)}{k(k+1)}(t^2+t)\right)$ 310 311 Equivalently, 312 313 $\sum_{\text{valid }x}X_t^2=C\left(\left(\frac{N}{k}+\frac{N(N-1)}{k(k+1)}\right)t+\frac{N(N-1)}{k(k+1)}t^2\right)$ 314 315 Substituting $t=T_i$ and summing over all positions, the final formula is 316 317 $g(b,m)=\binom{N+k-1}{k-1}\left(\sum_i A_i^2+\frac{2N}{k}\sum_i A_iT_i+\left(\frac{N}{k}+\frac{N(N-1)}{k(k+1)}\right)\sum_i T_i+\frac{N(N-1)}{k(k+1)}\sum_i T_i^2\right)$ 318 319 All divisions are done modulo $998244353$ using modular inverses. 320 321 Now we explain why this can be maintained by a segment tree. 322 323 For every interval, the formula only needs the following values: 324 325 $S,\quad k,\quad \sum A_i,\quad \sum T_i,\quad \sum A_i^2,\quad \sum A_iT_i,\quad \sum T_i^2$ 326 327 Therefore, each segment tree node maintains: 328 329 $len,\quad sum,\quad cnt,\quad sumA,\quad sumT,\quad sumA2,\quad sumAT,\quad sumT2$ 330 331 Here, $len$ is the length of the segment, $sum$ is the total fixed value in the segment, and $cnt$ is the number of $-1$ positions in the segment. 332 333 The other values are: 334 335 $sumA=\sum_i A_i$ $sumT=\sum_i T_i$ $sumA2=\sum_i A_i^2$ $sumAT=\sum_i A_iT_i$ $sumT2=\sum_i T_i^2$ 336 337 All prefix values are defined relative to the left end of the current segment. 338 339 When merging two adjacent segments $L$ and $R$, every prefix inside $L$ remains unchanged. 340 341 For a prefix inside $R$, the entire left segment is already before it. Therefore, 342 343 $A'_i=L.sum+A_i$ 344 345 and 346 347 $T'_i=L.cnt+T_i$ 348 349 So the merge formulas are: 350 351 $sum=sum_L+sum_R$ $cnt=cnt_L+cnt_R$ $sumA=sumA_L+sumA_R+len_R\cdot sum_L$ $sumT=sumT_L+sumT_R+len_R\cdot cnt_L$ $sumA2=sumA2_L+sumA2_R+2sum_L\cdot sumA_R+len_R\cdot sum_L^2$ $sumAT=sumAT_L+sumAT_R+sum_L\cdot sumT_R+cnt_L\cdot sumA_R+len_R\cdot sum_L\cdot cnt_L$ $sumT2=sumT2_L+sumT2_R+2cnt_L\cdot sumT_R+len_R\cdot cnt_L^2$ 352 353 Thus, the maintained information is closed under concatenation, so it is suitable for a segment tree. 354 355 A point update only changes one leaf, and then all nodes on the path to the root are recomputed. 356 357 For a range query, we merge $O(\log n)$ segment tree nodes in left-to-right order. This gives all values required by the formula above. 358 359 After precomputing factorials and inverse factorials for combinations, the total complexity is 360 361 $O((n+q)\log n)$ 362 363 **fanhuaxingyu's Solution** 364 365 ## Solution 366 367 Let `sum` be the sum of all fixed values in the interval, and let `cnt` be the number of `-1`'s. 368 369 If: 370 371 * `sum > m`; or 372 * `cnt = 0` and `sum ≠ m`; 373 374 then no valid sequence exists, and the answer is `0`. 375 376 The following discussion focuses only on valid cases. 377 378 For a single query, we have a simple brute-force approach with complexity $O(nm)$. 379 380 Let: 381 382 * $A_i$: The sum of fixed values among the first $i$ positions; 383 * $C_i$: The count of `-1`'s among the first $i$ positions; 384 * $rem = m - sum$. 385 386 Then: 387 388 $ \begin{aligned} f(c) &=\sum_{i=1}^n(A_i+x_i)^2 \\ &=\sum_{i=1}^n \sum_{j=0}^{rem}\binom{j+C_i-1}{C_i-1} \binom{rem-j+cnt-C_i-1}{cnt-C_i-1}(A_i+j)^2 \end{aligned} $ 389 390 Here, $x_i$ represents the total sum distributed to the first $C_i$ unknown variables (the `-1`'s). 391 392 Fixing a prefix $i$, if the unknowns in this prefix are assigned a sum of $j$, then the suffix unknowns must be assigned $rem-j$. 393 394 The number of ways is given by the classic Stars and Bars method: 395 396 $ W_i(j)= \binom{j+C_i-1}{C_i-1} \binom{rem-j+cnt-C_i-1}{cnt-C_i-1}. $ 397 398 However, this approach still has excessive complexity. We consider further optimization. 399 400 $ \begin{aligned} f(c) &=\sum_{i=1}^n \sum_{j=0}^{rem}W_i(j)(A_i+j)^2 \\ &=\sum_{i=1}^nA_i^2\sum_{j=0}^{rem}W_i(j) +\sum_{i=1}^n2A_i\sum_{j=0}^{rem}jW_i(j) +\sum_{i=1}^n\sum_{j=0}^{rem}jW_i(j) +\sum_{i=1}^n\sum_{j=0}^{rem}j(j-1)W_i(j) \\ &=\binom{rem-1+cnt}{cnt-1}\sum_{i=1}^nA_i^2 +\binom{rem-1+cnt}{cnt}\sum_{i=1}^n(2A_i+1)C_i +\binom{rem-1+cnt}{cnt+1}\sum_{i=1}^nC_i(C_i+1) \end{aligned} $ 401 402 This recurrence uses identity transformations: - $n\binom{n+k-1}{k-1}= k\binom{n+k-1}{k}$, - $n(n-1)\binom{n+k-1}{k-1}= k(k+1)\binom{n+k-1}{k+1}$, - $\sum_{k=0}^{n} \binom{k}{a}\binom{n-k}{m-a}=\binom{n+1}{m+1}$. 403 404 Thus, we obtain an $O(n)$ solution for the problem, which corresponds to the solution for **E1**. 405 406 How can we optimize further? 407 408 Observing the formula above, it becomes clear that if we can quickly maintain interval information such as: 409 410 * $sum$, 411 * $cnt$, 412 * $\sum_{i=1}^nA_i^2$, 413 * $\sum_{i=1}^nA_iC_i$, 414 * $\sum_{i=1}^nC_i$, 415 * $\sum_{i=1}^nC_i^2$, 416 417 a Segment Tree can handle these operations within $O(\log n)$ time complexity. 418 Therefore, the solution for **E2** is to use a Segment Tree to optimize the recurrence formula, achieving a total time complexity of $O(M+(n+q)\log n)$. 419 420 #### [2228F - Momoyo and the Network](/contest/2228/problem/F "Codeforces Round 1098 (Div. 2)") 421 422 Author: [Sanae](/profile/Sanae "International Master Sanae") 423 424 Solution: [Sanae](/profile/Sanae "International Master Sanae"), [juan_123](/profile/juan_123 "Grandmaster juan_123"), [SDSXC](/profile/SDSXC "Grandmaster SDSXC") 425 426 **Sanae's Solution** 427 428 **First Solution** 429 430 We binary-search the answer $V$. The monotonicity is clear: a larger $V$ is harder to achieve, and as $k$ increases, the feasible $V$ decreases. 431 432 Root the tree arbitrarily at $1$. For a node $x$, define $dp(x)$ as the maximum length (in edges) of a downward-only path starting at $x$ such that every vertex on the path satisfies: the weight of the component containing that vertex (after cutting the path) is at least $V$. 433 434 During DFS, at node $x$, we have the $dp$-values of its children. We need to check whether we can form a path of length $k$ that passes through $x$ (or starts at $x$). This reduces to finding two distinct children $y_1$, $y_2$ such that $dp(y_1) + dp(y_2) + 2 \ge k$ (or a single child with $dp(y) + 1 \ge k$ if the path starts downward from $x$). 435 436 Sorting the $dp$-values of the children allows an $O(\text{deg}(x)\log \text{deg}(x))$ check per node via two-pointers. 437 438 The overall time complexity is: $O(n\log V\log n)$. 439 440 **Second Solution** 441 442 Instead of computing $dp$ by length, we can pre-compute the total weight of each subtree and sort the children of each vertex accordingly. For a candidate $V$, we can check feasibility by sorting children according to their subtree weights (or the weight of the ``outside-the-path'' component) and using a two-pointer scan to see if a $k$-edge path exists that meets the $V$ threshold everywhere. 443 444 This eliminates the $\log n$ factor from sorting $dp$-values inside the binary search. 445 446 The overall time complexity is: $O(n\log n+n \log V)$. 447 448 **Third Solution** 449 450 It's the same as the juan_123's, just for reference. 451 452 Apply centroid decomposition. For a centroid $rt$, any $k$-edge path either lies entirely within one of $rt$'s subtrees (handled recursively) or passes through $rt$. In the latter case, the path consists of two legs, one in each of two different subtrees of $rt$. 453 454 For each vertex $u$ in a subtree, compute the minimum component weight along the path from $u$ to $rt$ (this is the minimum of the ``remaining component weights'' for vertices on that segment). Now, choosing two vertices $u$, $v$ in different subtrees gives a path through $rt$; the overall value is the minimum of the two minima from $u$ and $v$ and the components attached to other children of $rt$. 455 456 A key observation: if the largest component (by total weight) attached to $rt$ is not included in the path, it cannot be the minimum component. We only need to consider the possibility that the path touches the largest component, or handle the case where the largest component is excluded, which simplifies the check. 457 458 Carefully pruning with this observation, and using appropriate data structures to query for pairs of legs whose total length is $k$, leads to an $O(n \log n)$ solution. 459 460 Pruning cases where $k$ exceeds the size of the current component yields improved performance. 461 462 The overall time complexity is: $O(n\log n)$. 463 464 **juan_123's Solution** 465 466 First, we consider how to characterize the connected components formed after deleting the edges along a path, specifically focusing on the component containing a vertex $x$ on the path. 467 468 Let the root of the tree be $r$. Define $sz_x$ as the sum of weights in the subtree of $x$, $fa_x$ as the parent of $x$, and $tot$ as the sum of all $a_i$. Let LCA denote the lowest common ancestor of all points on the path. We analyze the position of $x$ on the path: 469 470 1. If $x$ is an endpoint of the path but not the LCA, the edge connecting $x$ to its parent $fa_x$ is deleted, while the edges to its children remain. The size of the resulting component is 471 472 $sz_x$ 473 474 . 2. If $x$ is neither the LCA nor an endpoint, the edges to $fa_x$ and to one specific child (say $y$) are deleted. The component size is 475 476 $sz_x - sz_y$ 477 478 . 3. If $x$ is the LCA, then 1 or 2 edges to its children (say $y$ and $z$) are deleted. The component size is 479 480 $tot - sz_y - sz_z$ 481 482 . 483 484 We employ **Centroid Decomposition**. At each step, we fix a centroid $r_0$ as the root and consider the contribution of all paths passing through $r_0$. For any such path, the LCA is $r_0$. Let $son_{r_0}$ be the set of children of $r_0$. 485 486 For contributions of type 1 and 2, we DFS the subtrees rooted at the children of $r_0$. We compute $val_{u,d}$, representing the maximum possible minimum component size if we select a path of length $d$ within the subtree of $u$ ($u \in son_{r_0}$), without yet considering the component containing the root $r_0$. 487 488 Now, consider a pair $(x, y, d_0, d_1)$ where $d_0 + d_1 = k$, $x, y \in son_{r_0}$, and $x \neq y$. This represents a path with endpoints in the subtrees of $x$ and $y$ at depths $d_0$ and $d_1$, respectively. The minimum component size for this configuration is: 489 490 $ \min(val_{x,d_0}, val_{y,d_1}, tot - sz_x - sz_y) $ 491 492 Next, we handle the term $tot - sz_x - sz_y$ associated with the root component. 493 494 Note that for any $u$ and $d$, 495 496 $val_{u,d} \le sz_u$ 497 498 . This is because $a_i > 0$, and $val$ represents splitting a subtree into parts, which cannot exceed the sum of the whole subtree. 499 500 Let $v$ be the child of $r_0$ with the largest subtree size ($sz_v$). If $x \neq v$ and $y \neq v$, the size of the root's component $s = tot - sz_x - sz_y$ satisfies 501 502 $s \gt sz_v \gt sz_x \ge val_{x,d}$ 503 504 . Since this component fully contains the large subtree of $v$, it will never be the minimum. Thus, we can ignore the root's contribution in this case and use prefix/suffix minimums to calculate the contribution efficiently. 505 506 Otherwise, one endpoint lies in the subtree of $v$. We can enumerate the other endpoint's subtree, making the calculation straightforward. 507 508 The total time complexity is $O(n \log n)$. 509 510 A crucial detail is that during the DFS for subtree sizes, if we encounter a node that was previously a centroid root, we must add the size of the subtree blocked by that centroid to the current subtree size. 511 512 **SDSXC's solution** 513 514 Root the tree arbitrarily at $1$. 515 516 For a node $u$, define $dp(u)$ as the maximum length (in edges) of a downward-only path starting at $u$ such that every vertex on the path satisfies: the weight of the component containing that vertex (after cutting the path) is at least $V$. 517 518 Define $f(u,x)$ as the maximum $V$ satisfies: $dep(u)+dp(u)\geq x$. 519 520 Define $b(u)$ as $\sum\limits_{v\in subtree(u)}a(v)$. 521 522 According to the solution above, we could easily write a $O(n^2)$ brute force to calculate $f(u,x)$ and the answer. Try to optimize it by using long path decomposition. 523 524 First we should calculate $f(u,x)$. The transition is: $f(u,x)=\max\limits_{fa_v=u}(\min(b(u)-b(v),f(v,x)))$ for $x \gt dep(u)$ and $f(u,x)=b(u)$ for $x=dep(u)$. 525 526 The most difficult part is the $\min(b(u)-b(v),f(v,x))$. Note that, $f(v,x)\geq f(v,x+1)$, so every time we set a prefix of $f(v)$ to $b(u)-b(v)$, we use something similar to ODT to solve this. Instead of maintain $(x,val)$ to represent $f(u,x)=val$, we maintain $(l,r,val)$ to represent $f(u,x)=val$ for all $x\in [l,r]$. The other part is easy to solve. 527 528 Then we should calculate the answer. We calculate the answer at the lca of the path. Assume that the lca is node $u$. 529 530 If $u$ is one of the endpoint, then the answer is $\max\limits_{fa_v=u}(\min(f(v,dep(u)+k),b(1)-b(v)))$. It seems that we should binerary search for the position where $f(u,dep(u)+k)$ store. But note that $f(v,x)$ is useless while $x \gt dep(u)+k$, so we erase them. And the $f(u,dep(u)+k)$ is at the end of $f(u)$. 531 532 If $u$ is not a endpoint, then the answer is $\max\limits_{fa_v=fa_w=u,x+y\geq 2dep(u)+k}(\min(f(v,x),f(w,y),b(1)-b(v)-b(w)))$. It is easy to solve if there is no $b(1)-b(v)-b(w)$. 533 534 Define $son(u)$ as $v$ with the maximum $b(v)$ satisfies: v is the son of $u$. Note that $\min(f(v,x),f(w,y))\leq b(1)-b(v)-b(w)$ while neither $v$ or $w$ is equal to $son(u)$. So we use brute force while $v=son(u)$ and $w=son(u)$. 535 536 The overall time complexity is: $O(n)$. 537 538 [code](https://codeforces.com/contest/2228/submission/374869458) 539 540 **code** 541 542 [374853549](/contest/2228/submission/374853549 "Submission 374853549 by loveax")