2150.md (23589B)
1 Source: https://codeforces.com/blog/entry/146651 2 3 [2151A - Incremental Subarray](/contest/2151/problem/A "Codeforces Round 1053 (Div. 2)") 4 5 Author: [TheScrasse](/profile/TheScrasse "Grandmaster TheScrasse") 6 Preparation: [TheScrasse](/profile/TheScrasse "Grandmaster TheScrasse") 7 8 **Hint 1** 9 10 There are two types of subarrays. 11 12 **Hint 2** 13 14 If there exists $a_i \geq a_{i+1}$, how many times can the subarray appear? 15 16 **Solution** 17 18 * If there exists an $i$ such that $a_i \geq a_{i+1}$, we have $a_i = k$ for some $k$, $a_{i+1} = 1$. The subarray $[k, 1]$ appears only once on the blackboard (when James writes $1, \ldots, k$ and then $1, \ldots, k+1$). Since $a_1, a_2, \ldots, a_m$ contains $[k, 1]$, it must appear at most once as well, but the statement guarantees that it appears at least once, so the answer is $1$. 19 * Otherwise, the array $a_1, a_2, \ldots, a_m$ can be rewritten as $l, l+1, \ldots, r$, and it appears when James writes $1, \ldots, r$, then when James writes $1, \ldots, r+1$, ..., then when James writes $1, \ldots, n$ (so $n-r+1$ times in total). 20 21 Complexity: $O(n)$ 22 23 **Code** 24 25 [340224512](/contest/2151/submission/340224512 "Submission 340224512 by Dominater069") 26 27 [2150A - Incremental Path](/contest/2150/problem/A "Codeforces Round 1053 (Div. 1)") 28 29 Author: [TheScrasse](/profile/TheScrasse "International Grandmaster TheScrasse") 30 Preparation: [TheScrasse](/profile/TheScrasse "International Grandmaster TheScrasse") 31 32 **Hint 1** 33 34 Suppose you have already calculated where person $i-1$ goes. Can you calculate fast where person $i$ goes? 35 36 **Hint 2** 37 38 The first $i-2$ cells visited by people $i-1$ and $i$ coincide. 39 40 **Solution** 41 42 Person $i$ performs the same commands as person $i-1$, with the addition of the $i$-th command. 43 44 Now we wonder whether performing the same $i-1$ commands means that the first $i-1$ cells visited are the same. This is actually false in general, because after person $i-1$ performs his commands, he colors a new cell black, and this can change the outcome of the $(i-1)$-th operation. However, the outcome of the first $i-2$ commands remains the same, because the new black cell is too far from the positions visited in the first $i-2$ commands. 45 46 So the position visited by person $i$ after $i-2$ commands is the same position visited by person $i-1$ after $i-2$ commands, and it's enough to simulate the last two commands naively. 47 48 Complexity: $O(n \log n)$ or $O(n)$ 49 50 **Code** 51 52 [340224365](/contest/2150/submission/340224365 "Submission 340224365 by Dominater069") 53 54 [2151C - Incremental Stay](/contest/2151/problem/C "Codeforces Round 1053 (Div. 2)") 55 56 Author: [TheScrasse](/profile/TheScrasse "International Grandmaster TheScrasse") 57 Preparation: [TheScrasse](/profile/TheScrasse "International Grandmaster TheScrasse") 58 59 **Hint 1** 60 61 For a fixed $k$, find a greedy strategy. 62 63 **Hint 2** 64 65 You can calculate the answer with prefix sums. 66 67 **Solution** 68 69 Consider the following strategy: 70 71 * Iterate over events in increasing order. 72 * In the first $k$ events, people enter the museum. In the last $k$ events, people exit. For the other events, if the current number of people is $k$ a person exits, otherwise a person enters. 73 74 This strategy is optimal, because it maximizes the number of people present at any time in the museum. 75 76 * After the $i$-th event with $i \leq k$, at most $i$ people can be inside the museum, and in fact we have exactly $i$. 77 * A similar argument works for the last $k$ events (you have to use that at the end the museum is empty). 78 * For the other events, after the $i$-th event we know that the parity of the number of people is equal to the parity of $i$. In fact, the number of people is either $k$ or $k-1$, which is the maximum possible number of people $\leq k$ with the correct parity. 79 80 Now we have to calculate the following terms: 81 82 * $1 \cdot a_1 + 2 \cdot a_2 + \ldots + k \cdot a_k$: can be done with prefix sums of $i \cdot a_i$. 83 * $k \cdot a_{2n-k+1} + (k-1) \cdot a_{2n-k+2} + \ldots + 1 \cdot a_{2n}$: can be done with prefix sums of $(2n-i+1) \cdot a_i$: 84 * $k \cdot (a_{k+2} + a_{k+4} + \ldots + a_{2n-k})$, $k \cdot (a_{k+2} + a_{k+4} + \ldots + a_{2n-k-1})$ and similar: can be done with prefix sums of $a_{2i}$, and prefix sums of $a_{2i+1}$. 85 86 Alternatively, we can calculate the answer for some $k$ fast using the answer for $k-2$ and changing a few terms. 87 88 Complexity: $O(n)$ 89 90 **Code** 91 92 [340224635](/contest/2151/submission/340224635 "Submission 340224635 by Dominater069") 93 94 [2150B - Grid Counting](/contest/2150/problem/B "Codeforces Round 1053 (Div. 1)") 95 96 Author: [TheScrasse](/profile/TheScrasse "International Grandmaster TheScrasse") 97 Preparation: [Dominater069](/profile/Dominater069 "International Grandmaster Dominater069") 98 99 **Hint 1** 100 101 Let's ignore the first condition for now. 102 103 **Hint 2** 104 105 Some cells are necessarily black. 106 107 **Hint 3** 108 109 Then, some cells are necessarily white. 110 111 **Hint 4** 112 113 Now what happens with $k = 2$? You can conclude that some cells in column $2$ are necessarily white. 114 115 **Hint 5** 116 117 Repeat with $k = 3$, etc. 118 119 **Hint 6** 120 121 Once you find all the grids which satisfy the second and the third conditions, iterate over rows in decreasing order. 122 123 **Solution** 124 125 * $(1, 1)$ is black, because of the second condition with $k = 1$. 126 * Then, $(i, 1)$ is white for $i \geq 2$, because of the third condition with $k = n$. 127 * Then, either $(1, 2)$ or $(2, 2)$ is black, because of the second condition with $k = 2$. 128 * Then, $(i, 2)$ is white for $i \geq 3$, because of the third condition with $k = n-1$. 129 * $\ldots$ 130 131 In general, only $(i, j)$ with $i \leq j$ can be black. If you repeat the same process starting from $(1, n)$, you can conclude that only $(i, j)$ with $i \leq n-j+1$ can be black. 132 133 So, for each column $j$, there is exactly one black cell $(i, j)$, with $i \leq \min(j, n-j+1)$. 134 135 Now you can iterate over rows in decreasing order. For each row, you have some number $c_i$ of available columns, and $a_i$ columns you must fill, and this can be done in $\binom{c_i}{a_i}$ ways. You can calculate $c_i$ from $c_{i+1}$ by calculating the number of new available columns, and subtracting the $a_{i+1}$ columns you must fill. 136 137 Complexity: $O(n \log n)$ or $O(n)$ 138 139 **Code** 140 141 [340224711](/contest/2150/submission/340224711 "Submission 340224711 by Dominater069") 142 143 [2150C - Limited Edition Shop](/contest/2150/problem/C "Codeforces Round 1053 (Div. 1)") 144 145 Author: [TheScrasse](/profile/TheScrasse "International Grandmaster TheScrasse") 146 Preparation: [TheScrasse](/profile/TheScrasse "International Grandmaster TheScrasse") 147 148 **Hint 1** 149 150 Try to come up with a condition for when Alice can choose some subset of items. 151 152 **Hint 2** 153 154 Write a dynamic programming $O(n^2)$ solution based on the condition. 155 156 **Hint 3** 157 158 Optimize the solution with data structures like segment trees. 159 160 **Solution** 161 162 We can assume $a_i = i$ for all $i$. Now, if Alice wants to take some subset $S$, we have the following condition: 163 164 * For all $x \notin S$, $y \in S$, if $x \lt y$, then $pos_x \lt pos_y$, where $pos = b^{-1}$ 165 166 **Proof:** If $pos_x \gt pos_y$, the item $y$ cannot be taken before $x$ because $x$ comes first in Alice's priority order. And item $x$ cannot be taken before $y$ because $y$ comes first in Bob's priority order. 167 168 Now, if the condition is satisfied, infact all subsets are valid. A simple algorithm works, just make Alice take all items in $S$ in increasing order, and when Alice wants to take some item but it is not the first remaining item according to her priority order, Bob takes items till it becomes first in her priority order. 169 170 Now, we can write our dynamic programming solution: $dp_{(i, j)} =$ maximum sum of items taken by Alice within the first $i$ items such that $max(pos_x)$ among Bob's items is $j$. 171 172 Transitions are: 173 174 * We are allowed to let Alice take item $i + 1$ if and only if $pos_i \gt j$. 175 * Bob can take item $i + 1$ without restrictions, and $j$ gets updated to $\max(j, pos_{i + 1})$ 176 177 We then optimize this with storing a segment tree over the states $j$. The first type of transition is a range add query, the second type of transition can be split into $j \lt pos_{i + 1}$ and $j \gt pos_{i + 1}$, in the first case we do nothing, and in the second case we need a range max query. 178 179 All of the above operations can be handled with a lazy segment tree. The time complexity is $O(n \cdot log(n))$. 180 181 **Code** 182 183 [340224797](/contest/2150/submission/340224797 "Submission 340224797 by Dominater069") 184 185 [2150D - Attraction Theory](/contest/2150/problem/D "Codeforces Round 1053 (Div. 1)") 186 187 Author: [Dominater069](/profile/Dominater069 "International Grandmaster Dominater069") 188 Preparation: [Dominater069](/profile/Dominater069 "International Grandmaster Dominater069") 189 190 **Hint 1** 191 192 Find a characterization for when a position array $p$ is possible. It helps to think in terms of $f_x =$ the number of people at coordinate $x$ instead. 193 194 **Hint 2** 195 196 Essentially, an attraction at $x$ combines the people standing at $x - 1, x$ and $x + 1$. Each update unites $3$ components into one, except for updates at the edge. 197 198 **Solution Part 1** 199 200 Read the hints. We are trying to find a characterization for valid sequences $p$. 201 202 We can prove the following necessary conditions easily by considering what happens when an attraction is placed in different positions, 203 204 * There exists $1 \le L \le R \le n$ such that $f_i \ge 1$ if and only if $L \le i \le R$. 205 * $f_i$ is odd for all $L \lt i \lt R$. 206 207 Further, these conditions are sufficient, and a simple construction is to do $\frac{f_i}{2}$ attractions at the position of the centre of the group of people finally at $i$ (The edges are handled easily). Also, you may have to do some translations at the end, which can be done by attracting at $1$ or $n$. 208 209 **Hint 3** 210 211 Try to fix $L$ and $R - L + 1$, and then calculate the sum under these restrictions. 212 213 **Hint 4** 214 215 The middle $R - L - 1$ variables have to be odd, and the outer $2$ variables can have any parity. Fix the parity of the outer elements. 216 217 **Hint 5** 218 219 Use expected value symmetry arguments to calculate the sum fast. 220 221 **Solution Part 2** 222 223 Assume $L = 1$ and $R = K$ ($K \gt 1$) for now. We have the equation $f_1 + f_2 + f_3 + \ldots + f_k = n$, and $f_i \ge 1$ and $f_i$ odd for $i \ne 1$ and $i \ne k$, where $f_i =$ the number of people finally at $i$. We want $\sum f_i \cdot a_i$ over all ways. 224 225 Fix parity of $f_1, f_k$ say $x$ and $y$ (let $1 \le x, y \le 2$), and then let 226 227 * $f_i = 2 \cdot g_i + 1$ for all $i \ne 1, i \ne k$ 228 * $f_1 = 2 \cdot g_1 + x$ 229 * $f_k = 2 \cdot g_k + y$ 230 231 Let $S = n - x - y - (k - 2)$. Now, the equation becomes $\sum g_i = \frac{S}{2}$, and we want $\sum 2 \cdot g_i \cdot a_i$ over all ways ($+$ a few more terms arising from the constants $1$, $x$ and $y$). 232 233 If $S$ is odd, no solution. Assume $S$ even. 234 235 Since all $g_i$ variables are symmetric, we can just say the expected value of $g_i$ is $\frac{S}{2 \cdot k}$, and then calculate $\sum ways \cdot EV(g_i) \cdot a_i$, where $ways$ is the number of solutions (simple stars and bars). 236 237 To solve the full problem, note that it essentially requires you to optimize finding sum of subarrays of size of length $k$, and this can be done (cleanly) with prefix sums on prefix sums. Also, you need to handle $L = R$ separately. The final solution is $O(n)$. 238 239 **Code** 240 241 [340224836](/contest/2150/submission/340224836 "Submission 340224836 by Dominater069") 242 243 [2150E1 - Hidden Single (Version 1)](/contest/2150/problem/E1 "Codeforces Round 1053 (Div. 1)") 244 245 Author: [TheScrasse](/profile/TheScrasse "International Grandmaster TheScrasse") 246 Preparation: [TheScrasse](/profile/TheScrasse "International Grandmaster TheScrasse"), [Dominater069](/profile/Dominater069 "International Grandmaster Dominater069") 247 248 **Hint 1** 249 250 Assume all elements appear twice, and look for a contradiction. 251 252 **Hint 2** 253 254 Split the array into two. 255 256 **Hint 3** 257 258 Determine whether each value appear on the left, on the right, or in both. 259 260 **Hint 4** 261 262 Continue recursively. 263 264 **Solution** 265 266 Write a recursive function `solve(tl, tr, vals, waste)`, which means that 267 268 * you are looking for the special value in the interval `[tl, tr]`; 269 * the vector `vals` contains the values which only appear in `[tl, tr]`; 270 * the vector `waste` contains the value which appear both in `[tl, tr]` and outside it. 271 272 At the beginning, call `solve(1, 2n - 1, {1, 2, ..., n}, {})`. In every call, 273 274 * let `tm = (tl + tr) / 2`, and split the interval `[tl, tr]` into two intervals `[tl, tm]` and `[tm+1, tr]`; 275 * for each value in `waste` determine the sub-interval containing it (spending $1$ query); 276 * for each value in `vals` determine the sub-intervals containing it (spending at most $2$ queries). 277 278 Now pretend every element appears twice, and calculate the length of `[tl, tm]` and `[tm+1, tr]` according to the values they contain. One of the lengths turns out to be wrong, because the interval contains a single element which was counted twice, so you can recurse there. 279 280 You visit at most $\lceil \log_2 n \rceil$ intervals. The total length of the visited intervals is at most $4n + \lceil \log_2 n \rceil$ (the starting interval has length $2n-1$ and is halved every time). 281 282 For an interval of length $l$, you ask at most $l+1$ queries. So you ask at most $4n + \lceil 2 \log_2 n \rceil$ queries in total. 283 284 **Code** 285 286 [340224890](/contest/2150/submission/340224890 "Submission 340224890 by Dominater069") 287 288 [2150E2 - Hidden Single (Version 2)](/contest/2150/problem/E2 "Codeforces Round 1053 (Div. 1)") 289 290 Author: [TheScrasse](/profile/TheScrasse "International Grandmaster TheScrasse") 291 Preparation: [TheScrasse](/profile/TheScrasse "International Grandmaster TheScrasse"), [Dominater069](/profile/Dominater069 "International Grandmaster Dominater069") 292 293 **Hint 1** 294 295 For a single value, if it appears twice, how many queries can you spend on average to detect that? 296 297 **Hint 2** 298 299 Combine a randomized solution with the solution to [2150E1 - Hidden Single (Version 1)](/contest/2150/problem/E1 "Codeforces Round 1053 (Div. 1)"). 300 301 **Solution** 302 303 After the first layer of recursion in the solution to [2150E1 - Hidden Single (Version 1)](/contest/2150/problem/E1 "Codeforces Round 1053 (Div. 1)"), you have spent around $7n/4$ queries, and there are around $n/4$ candidate values which can be the special value. 304 305 Consider the following procedure to approximately halve the number of candidates: 306 307 * split the array randomly into two halves (subsets); 308 * for each candidate, determine whether it appears in both halves. 309 310 With probability around $1/2$, the candidate appears in both halves and you use $2$ queries to detect it. Otherwise, you spend $3/2$ queries on average. So the average number of queries is approximately the solution to $x = 2/2 + (x+3/2)/2$, which is $7/2$. So you spend around $21n/8$ queries in total. Because of variance, you might end up asking significantly more queries, but with high probability you ask at most $900$ queries. 311 312 Bonus: you can further reduce the number of queries using some minor optimizations. For example, instead of splitting randomly, you can shuffle the array randomly at the beginning, and binary search every candidate. This is better because: 313 314 * there is an upper bound on the number of queries you make for each candidate; 315 * you ask queries on smaller subsets, so the probability of a candidate appearing twice in the same subset is slightly lower; 316 * you can break earlier if you find the special value. 317 318 The model solution based on this approach takes only $863$ queries on worst case with $10^4$ tests of size $n = 300$. 319 320 **Code** 321 322 [340224967](/contest/2150/submission/340224967 "Submission 340224967 by Dominater069") 323 324 [2150F - Cycle Closing](/contest/2150/problem/F "Codeforces Round 1053 (Div. 1)") 325 326 Author: [TheScrasse](/profile/TheScrasse "International Grandmaster TheScrasse") 327 Preparation: [TheScrasse](/profile/TheScrasse "International Grandmaster TheScrasse"), [Dominater069](/profile/Dominater069 "International Grandmaster Dominater069") 328 329 **Hint 1** 330 331 Use $k = 3$ for the first operation. Now, you have edges between all vertices at distance $1$ and $2$. 332 333 **Hint 2** 334 335 Use $\frac{D}{2} + 1$ for your second operation, where $D$ is the diameter. 336 337 **Solution** 338 339 Assume the graph is a tree, otherwise take an arbitrary spanning tree. First operation is $k = 3$, because that adds edges between all vertices at distance $2$, and we already have edges of vertices at distance $1$. 340 341 The second operation needs to be at least $\frac{D}{2} + 1$, where $D$ is diameter, because otherwise it is impossible to construct a path between the farthest nodes. And infact, it is possible to construct paths of length exactly $\frac{D}{2} + 1$ between all pairs of vertices, so we choose second operation as this. 342 343 The construction is as follows, suppose we want a path between nodes $u$ and $v$ (there are simpler constructions, the editorialist describes his). Let $c_x$ denote the closest node in the diameter to node $x$. 344 345 * $dist(u, v) \ge k$ : Just take a direct path between $u$ and $v$, and skip appropriate number of vertices. 346 347 * $c_u \ne c_v$ : First construct a path from $u$ to $c_u$ and similarly, $v$ to $c_v$. Now, we need to waste some operations because $dist(u, v) \lt k$. Assume the diameter is $1, 2, \ldots, D$ WLOG. Then, we can do the following operation: $(c_u, c_u - 2, c_u - 4, c_u - 3, c_u - 1, c_u + 1)$ and we successfully wasted $4$ steps. 348 349 This can be easily generalized to all lengths. Because $dist(u, v) \lt k$ implies $dist(c_u, c_v) \lt k$, and thus, $dist(1, c_u) + dist(c_v, D) \ge k$, so it is always possible to waste sufficient number of steps on the paths $1$ to $c_u$ and $c_v$ to $D$. 350 351 * $c_u = c_v$ : Root the tree at $c_u$. Assume that $u$ is an ancestor of $v$ (if it is not, make it an ancestor by jumping to parent). Either $dist(1, u) \ge k$ or $dist(D, u) \ge k$ [due to property of diameter, $k = \frac{D}{2} + 1$]. Then we can waste the sufficient number of steps on the path from $1$ to $u$, or $L$ to $u$ whichever one is larger. ($1$ and $D$ are diameter endpoints). 352 353 The entire solution runs in $O(n^3)$. 354 355 **Code** 356 357 [340225230](/contest/2150/submission/340225230 "Submission 340225230 by Dominater069") 358 359 [2150G - Counting Is Fun: The Finale](/contest/2150/problem/G "Codeforces Round 1053 (Div. 1)") 360 361 Author: [satyam343](/profile/satyam343 "Master satyam343") 362 Preparation: [satyam343](/profile/satyam343 "Master satyam343") 363 364 **Solution** 365 366 Let's first solve the following subproblem: given $x, y, k,$ how can we find the number of binary strings with Longest Nondecreasing Subsequence $\geq k$? 367 368 The answer is if $max(x,y)\geq k$, the answer is $\binom{x+y}{x}$. Otherwise, it is $\binom{x+y}{k}$. The proof for the first case is obvious. In the second case, we can approach it by bijecting it to paths on a grid. We start at the point $(0,0)$ and we want to get to the point $(x,y)$ through going East ($+1$ on $x$-coordinate) or North ($+1$ on $y$-coordinate). We claim that any path $p_0=(0,0), p_1,p_2,\ldots,p_{x+y}=(x,y)$, where there exists an index $i$ such that $(p_i).x-(p_i).y=y-k$ can be bijected to a good binary string. To prove that this is sufficient, note that by taking every occurrence of North on our path in the future, we have a subsequence of size $k$. To prove that this is necessary, note that if the longest nondecreasing subsequence in the binary string is $a$ $0$'s followed by $b$ $1$'s, then we can map the point right after $a$ $0$'s to the index $i$. Now, why is this mapping helpful? We can use the reflection technique to count the number of good paths. Let $i$ be the first occurrence where $(p_i).x-(p_i).y=y-k$. Now, reflect the remaining part of the path across the line $y-x=y-k$. Now we have mapped the number of good paths to the number of paths that arrive to the point $(x+y-k, k)$. This is similar to the proof of the closed form of Catalan numbers. Let this function be $f(x,y,k)$. 369 370 Now, let's solve the above problem again, but we are given a prefix of the binary string. Let $Z$ be the number of zeroes, $L$ be the length of the longest nondecreasing subsequence, $x$ and $y$ be the number of zeroes and ones to concatenate, and let $k$ be the target length of longest nondecreasing subsequence. I claim that the number of ways to finish the binary string is $\binom{x+y}{x}$ if $L+y \geq k$ or $Z+x \geq k$, $0$ if $Z+x+y \lt k$, and $\binom{x+y}{k-Z}$ otherwise. The first two cases are relatively simple to show. We can show the last case because the longest nondecreasing subsequence of the entire string must compose entirely of $0$'s in the prefix (or else $L+y\geq k$ would be true), so we can simplify this problem to the above problem as we only need a longest nondecreasing subsequence of $k-Z$ now. Let this function be $g(x,y,k,Z)$. 371 372 Now, to solve the problem, let's enumerate the length of the common prefix of $s$ and $t$, and then the index where the first half **first** has a longest nondecreasing subsequence length of exactly $k$ (call this index $i$). If this point is within the prefix, then we can complete the second half of the sequence directly using the formula we obtained above. There are two cases: either $t_i=0$ or $t_i=1$. If $t_i=0$ and $i$ is the first index where the longest nondecreasing subsequence has length $k$, then the longest nondecreasing subsequence must compose of only $0$'s. In this case, the length of the longest nondecreasing subsequence up to index $i-1$ must be $k-1$, and the number of zeroes are also fixed — this is also a direct application of the original formula. Otherwise (that is, if $t_i=1$), let $x'$ and $y'$ be the number of zeroes and ones in this half. At index $i-1$, the length of the longest nondecreasing subsequence should be exactly $k-1$. We can calculate this by taking the number of binary strings with LNDS length at least $k-1$, and subtract the number of binary strings with LNDS length at least $k$. Note that the number of $0$'s and $1$'s in the second half is also fixed (call them $x"$ and $y"$ respectively), so we can multiply the previous result by the number of binary strings with LNDS at least $k$. We can write this as getting the sum $(g(x',y',k-1,Z)-g(x',y',k,Z))\cdot f(x",y",k)$. 373 374 This looks like the solution will become $O(n^3)$ since we have to loop through all possible $x'$ values. However, let's look at $g(x,y,k,Z)$ again. It is $\binom{x+y}{x}$ if $y \geq k-C_1$ or $x \geq k-C_2$ (call this case $1$) for some constants $C_1$ and $C_2$, and $\binom{x+y}{k-Z}$ otherwise (call this case $2$). Consider $g(x',y',k-1,Z)$ and $g(x',y',k,Z)$. When both functions are in case $1$, we have $g(x',y',k-1,Z)-g(x',y',k,Z)=0$. When both functions are in case $2$, the difference is a constant. The only case we have to worry about is when one function is in case $1$ and the other is in case $2$. But note the conditions for case $1$ — it is either if $y$ is larger than some constant or if $x$ is larger than some constant. Thus, when $g(x',y',k-1,Z)$ leaves case $1$, $g(x',y',k-1,Z)$ will also leave case $1$. Similarly, when $g(x',y',k,Z)$ enters case $1$ (when $y$ becomes too large), $g(x',y',k-1,Z)$ will also enter case $1$ in the next iteration. So, we only have to calculate these cases for $2$ values of $X$. Combining this with some prefix sums of binomial factors (to deal with the $f(x",y",k)$ portion when $g(x',y',k-1,Z)-g(x',y',k,Z)$ is constant), we actually avoid running the loop entirely. Thus, we can calculate the answer in $O(n^2)$. 375 376 **Code** 377 378 [340578210](/contest/2150/submission/340578210 "Submission 340578210 by Dominater069")