codeforces-scrape

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

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")