codeforces-scrape

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

2157.md (21177B)


      1 Source: https://codeforces.com/blog/entry/148631
      2 
      3 [2157A - Dungeon Equilibrium](/contest/2157/problem/A)
      4 
      5 Author: [TheScrasse](/profile/TheScrasse "Grandmaster TheScrasse")  
      6  Preparation: [TheScrasse](/profile/TheScrasse "Grandmaster TheScrasse")
      7 
      8 **Hint 1**
      9 
     10 Each value $x$ is independent of the others; only its own frequency matters.
     11 
     12 **Hint 2**
     13 
     14 In a balanced array, value $x$ must appear either $0$ times or **exactly** $x$ times.
     15 
     16 **Solution**
     17 
     18 * Each value $x$ is independent of the others; only its own frequency matters. In particular, for each value, find its frequency $f[x]$.
     19 * In a balanced array, value $x$ must appear either $0$ times or **exactly** $x$ times. Specifically, if it appears $ \lt x$ times at the beginning, you have to delete all its occurrences, otherwise you should keep $x$ occurrences. Specifically, for each $x$, add $f[x]$ to the answer if $f[x] \lt x$, else add $f[x] - x$.
     20 
     21 Complexity: $O(n)$ time. Slower solutions (e.g., $O(n^2)$) are allowed.
     22 
     23 **Code**
     24 
     25 [350380351](/contest/2157/submission/350380351 "Submission 350380351 by Dominater069")
     26 
     27 [2157B - Expansion Plan 2](/contest/2157/problem/B)
     28 
     29 Author: [TheScrasse](/profile/TheScrasse "Grandmaster TheScrasse")  
     30  Preparation: [TheScrasse](/profile/TheScrasse "Grandmaster TheScrasse")
     31 
     32 **Hint 1**
     33 
     34 The order of operations does not matter. Only the number of $\texttt{4}s$ and $\texttt{8}s$ in the substring matters.
     35 
     36 **Hint 2**
     37 
     38 The black cells are the positions we can reach starting from $(0, 0)$, if we can move orthogonally (using a $\texttt{4}$) and diagonally (using an $\texttt{8}$).
     39 
     40 **Hint 3**
     41 
     42 A move with an $\texttt{8}$ is equivalent to two moves with a $\texttt{4}$, in different directions.
     43 
     44 **Solution**
     45 
     46 * The order of operations does not matter. So count the number of $\texttt{4}s$ and $\texttt{8}s$, and assume there are $a$ $\texttt{4}$s and $b$ $\texttt{8}s$.
     47 * The grid is symmetrical. We can assume $x, y \geq 0$ (by making $x := |x|$, $y := |y|$).
     48 * The black cells are the positions we can reach starting from $(0, 0)$, if we can move orthogonally (using a $\texttt{4}$) and diagonally (using an $\texttt{8}$).
     49 * In particular, since $x, y \geq 0$, a $\texttt{4}$ is a step either up or right while an $\texttt{8}$ consists of two steps, one up and one right.
     50 * So you make $a+2b$ steps in total, and only $a+b$ of them can be in the same direction.
     51 * The necessary and sufficient conditions are
     52 * + $a+2b \geq x+y$ (you need to be able to perform $x+y$ steps, either up or right, to reach $(x, y)$);
     53 * + $a+b \geq \max(x, y)$ (you need to be able to perform $y$ steps up and $x$ steps right).
     54 
     55 **Code**
     56 
     57 [350380442](/contest/2157/submission/350380442 "Submission 350380442 by Dominater069")
     58 
     59 [2157C - Meximum Array 2](/contest/2157/problem/C)
     60 
     61 Author: [TheScrasse](/profile/TheScrasse "Grandmaster TheScrasse")  
     62  Preparation: [TheScrasse](/profile/TheScrasse "Grandmaster TheScrasse")
     63 
     64 **Hint 1**
     65 
     66 For each element, determine whether it belongs to a $\texttt{MEX}$ constraint, a $\min$ constraint, both, or none.
     67 
     68 **Hint 2**
     69 
     70 If an element belongs to both a $\texttt{MEX}$ constraint and a $\min$ constraint, it is useless for both constraints.
     71 
     72 **Hint 3**
     73 
     74 If an element only belongs to a $\min$ constraint, you can set it to $k$ for convenience.
     75 
     76 **Hint 4**
     77 
     78 What's the "fastest" way to satisfy a $\texttt{MEX}$ constraint? What about several constraints simultaneously?
     79 
     80 **Solution**
     81 
     82 For each element, determine whether it belongs to a $\texttt{MEX}$ constraint, a $\min$ constraint, both, or none.
     83 
     84 * If an element is covered by a $\min$ constraint, it must be $\geq k$, and ideally it should be $= k$ (so that the constraint is immediately satisfied).
     85 * If an element is covered by a $\texttt{MEX}$ constraint, it must be $\neq k$, and ideally it should be $ \lt k$ (to make the constraint easier to satisfy).
     86 
     87 Then
     88 
     89 * If an element is not covered by any constraints, it does not matter, and you can set it to any value.
     90 * If an element belongs to both a $\texttt{MEX}$ constraint and a $\min$ constraint, it is useless for both constraints, but you must set it to something both $\neq k$ and $\geq k$. For example, you can set it to $k+1$.
     91 * If an element only belongs to a $\min$ constraint, it is optimal to set it to $k$.
     92 * The remaining elements are the ones which are only covered by a $\texttt{MEX}$ constraint. In order to be satisfied, a $\texttt{MEX}$ constraint must contain at least $k$ such elements (because it must contain all the elements between $0$ and $k-1$, which would violate a $\min$ constraint). In particular, assigning $i \text{ mod } k$ at the $i$-th such element works (if a $\texttt{MEX}$ constraint contains $k$ such elements, their values are $[0, 1, \ldots, k-1]$, possibly shifted).
     93 
     94 Complexity: $O(nq)$ or $O(n+q)$ per test case.
     95 
     96 Bonus: in the above solution, we assign $i \text{ mod } k$ to the $i$-th element only covered by $\texttt{MEX}$ constraints. However, assigning $a_i = i \text{ mod } k$ to such elements (where $i$ is the position in the whole array, instead of the position only considering such elements) also works. Can you prove it?
     97 
     98 **Code**
     99 
    100 [350380521](/contest/2157/submission/350380521 "Submission 350380521 by Dominater069")
    101 
    102 [2157D - Billion Players Game](/contest/2157/problem/D)
    103 
    104 Author: [TheScrasse](/profile/TheScrasse "Grandmaster TheScrasse")  
    105  Preparation: [TheScrasse](/profile/TheScrasse "Grandmaster TheScrasse")
    106 
    107 **Hint 1**
    108 
    109 The worst case is either $x = l$ or $x = r$. So you can assume that $x$ is either $l$ or $r$, but you don't know which one.
    110 
    111 **Hint 2**
    112 
    113 There exists an optimal strategy where a prefix of offers (after sorting) is accepted using the third option, and a suffix of elements is accepted using the second option.
    114 
    115 **Hint 3**
    116 
    117 There exists an optimal strategy where (in addition to the previous properties) at most one offer is rejected.
    118 
    119 **Solution**
    120 
    121 The worst case is either $x = l$ or $x = r$.  
    122  **Sketch of proof.** After fixing the strategy, the number of coins as a function of $x$ is a straight line.  
    123  Then, in order to test a strategy, it is enough to evaluate it at $x = l$ and $x = r$ and pick the minimum.
    124 
    125 There exists an optimal strategy where a prefix of elements (after sorting) is red, and a suffix of elements is blue.  
    126  **Sketch of proof.** Use exchange argument. For example, if $y \leq z$, $y$ is white and $z$ is red, then we get $x-z$ coins. If we make $y$ red and $z$ white, we make $x-y$ coins instead.
    127 
    128 There exists an optimal strategy where (in addition to the previous properties) at most one element is white.  
    129  **Sketch of proof.** If $x \leq y$, and they are both white, we can make $x$ red and $y$ blue instead.
    130 
    131 * Try all possibilities for the white element. So there are $O(n)$ candidate strategies.
    132 * We can test a strategy in $O(1)$: find the number of coins as a function of $x$ using prefix sums, and evaluate it in $l$ and $r$ to check the actual worst case.
    133 
    134 Complexity: $O(n \log n)$
    135 
    136 **Code**
    137 
    138 [350380713](/contest/2157/submission/350380713 "Submission 350380713 by Dominater069")
    139 
    140 [2157E - Adjusting Drones](/contest/2157/problem/E)
    141 
    142 Author: [TheScrasse](/profile/TheScrasse "Grandmaster TheScrasse")  
    143  Preparation: [TheScrasse](/profile/TheScrasse "Grandmaster TheScrasse")
    144 
    145 **Hint 1**
    146 
    147 The order of the elements does not matter.
    148 
    149 **Hint 2**
    150 
    151 Solve the problem with $k = 1$.
    152 
    153 **Hint 3**
    154 
    155 Iterate over elements from right to left and find their final value if $k = 1$.
    156 
    157 **Hint 4**
    158 
    159 Find the value of each element over time. Can you calculate the value of some element after a fixed number $m$ of operations?
    160 
    161 **Hint 5**
    162 
    163 Binary search the answer.
    164 
    165 **Solution**
    166 
    167 The order of the elements does not matter. So let's sort the elements in increasing order. Also, we have the freedom to choose the tiebreaker rule (i.e., which elements are increased by $1$).
    168 
    169 * Assume the process stops when all the elements are distinct (i.e., $k = 1$). Let's find the configuration $b_1, b_2, \ldots, b_n$ at that point. If some elements are equal, the **rightmost** does not increase.
    170 * From right to left, if the initial value is $a_i$, then $b_i$ is the smallest $x \geq a_i$ not present in $b$ yet.
    171 * If we look at a single element over time, it has values $a_i, a_i + 1, \ldots, b_i, b_i, \ldots, b_i$.
    172 
    173 ![ ](/predownloaded/ee/e5/eee59b099df564239ceb8b5d7c9232e526c43436.png)
    174 
    175 * The maximum number of occurences of one element does not increase after one operation (if value $x$ appeared $\leq k$ times, it produces $\leq k-1$ copies of $x+1$, and at most one other copy of $x+1$ survives).
    176 * So we can binary search the answer. Using the process described earlier, we can retrieve the configuration after $m$ moves in $O(n)$.
    177 
    178 Complexity: $O(n \log n)$ time (there also exist "magical" $O(n)$ solutions!)
    179 
    180 **Code**
    181 
    182 [350380783](/contest/2157/submission/350380783 "Submission 350380783 by Dominater069")
    183 
    184 [2157F - Git Gud](/contest/2157/problem/F)
    185 
    186 Author: [TheScrasse](/profile/TheScrasse "Grandmaster TheScrasse")  
    187  Preparation: [TheScrasse](/profile/TheScrasse "Grandmaster TheScrasse")
    188 
    189 **Hint 1**
    190 
    191 How would you write the checker for this problem? (How to check efficiently whether a submission gets AC or WA)?
    192 
    193 **Hint 2**
    194 
    195 After you choose $y$, calculating the optimal $l$ is easy. From now, let's denote the operations only using $y$.
    196 
    197 **Hint 3**
    198 
    199 Consider some naive strategies: for example, $[1, 2, \ldots, n-1]$, or $[n-1, n-2, \ldots, 1]$. Why are they bad? How to improve them?
    200 
    201 **Hint 4**
    202 
    203 You can fix your skill modulo $2$, then modulo $4$, then modulo $8$, etc., but that's still a bit too inefficient.
    204 
    205 **Hint 5**
    206 
    207 Try with a different modulo.
    208 
    209 **Solution**
    210 
    211 As a warm-up, think about how we would write the checker for this problem.
    212 
    213 We can store the set of all the possible skills (initially, all integers in $[1, n]$), and perform operations in $O(1)$ (we have to remove $y$ and insert $y+l$).
    214 
    215 As a consequence, the optimal value of $l$ is the smallest one such that $y+l$ is already in the set. Since we know how to determine the optimal $l$ for a fixed $y$, let's denote the operations only using $y$.
    216 
    217 * Naive strategy 1: use operations $1, 2, \ldots, n-1$. Unfortunately, they are too "increasing".
    218 * Naive strategy 2: use operations $n-1, n-2, \ldots, 1$. Unfortunately, they are too long.
    219 
    220 Better strategy:
    221 
    222 * Fix our skill modulo $2$ using operations $n-1, n-3, n-5, \ldots$
    223 * Fix our skill modulo $4$ using operations $n-2, n-6, n-10, \ldots$
    224 * $\ldots$
    225 
    226 The cost is $O(n \log n)$ ($\approx \log_2 n$ layers, $O(n)$ per layer). We use very few "increasing" operations ($1$ per layer): we can try to use more (and maybe use less layers).
    227 
    228 Generalization:
    229 
    230 * Fix our skill modulo $3$ using operations $n-2, n-5, n-8, \ldots, n-1, n-4, n-7, \ldots$
    231 * Fix our skill modulo $9$ using operations $n-6, n-18, n-30, \ldots, n-3, n-12, n-21, \ldots$
    232 * $\ldots$
    233 
    234 Now we have $\approx \log_3 n$ layers and $2$ "increasing" operations per layer.
    235 
    236 ![ ](/predownloaded/39/90/399042775cf5848899c7e0b6265cd18bcef28ca5.png)
    237 
    238 ![ ](/predownloaded/c6/81/c6817e014ecd0823c6e5d0cddf84aafa1d6d2425.png)
    239 
    240 ![ ](/predownloaded/a5/2f/a52f8576ecfc2283e88c62fce09025f244f6d4bf.png)
    241 
    242 If we use modulo $m$, we have $\approx \log_m n$ layers, each with cost $\approx n$, and $m-1$ "increasing" operations per layer, each with cost $1000$.
    243 
    244 We should choose $m \approx \sqrt[3]{n}$. So the total cost is around
    245 
    246 $(\log_m n)(n + 1000 m) = 3(n + 1000 \sqrt[3]{n}) \lt 4n$
    247 
    248 if $n = 250\,000$.
    249 
    250 **Code**
    251 
    252 [350380837](/contest/2157/submission/350380837 "Submission 350380837 by Dominater069")
    253 
    254 [2157G - Isaac's Queries](/contest/2157/problem/G)
    255 
    256 Author: [KLPP](/profile/KLPP "International Grandmaster KLPP")  
    257  Preparation: [KLPP](/profile/KLPP "International Grandmaster KLPP")
    258 
    259 **Hint 1**
    260 
    261 Apply prefix XOR. So, instead of information about $a_l \oplus a_{l+1} \oplus \ldots \oplus a_r$, assume you can ask information about $a_l \oplus a_r$.
    262 
    263 **Hint 2**
    264 
    265 Find whether the highest bit of every $a_i$ (viewed as $30$-bit integer) is $0$ or $1$. You can assume that $a_1$ has highest bit $0$.
    266 
    267 **Hint 3**
    268 
    269 You get two blocks. Recurse.
    270 
    271 **Hint 4**
    272 
    273 Solve every block in the most efficient way possible.
    274 
    275 **Solution**
    276 
    277 Apply prefix XOR. So, instead of information about $a_l \oplus a_{l+1} \oplus \ldots \oplus a_r$, we assume we can ask information about $a_l \oplus a_r$.
    278 
    279 Let's build a trie containing the $a_i$. Specifically, each node corresponds to a prefix of the binary representation, and contains positions $i$ such that $a_i$ has that prefix. It is not possible to recover the $a_i$ uniquely, but we can set bits to $0$ without loss of generality if they do not impact any queries. Then, in order to calculate the answer for some $(l, r)$, we have to find the LCA of the corresponding nodes.
    280 
    281 Suppose we are in some node of the trie containing $k$ values. We want to recurse into two children, depending on the next bit. This is possible by asking the query.
    282 
    283 Specifically, suppose that a node contains positions $p_1, p_2, \ldots, p_k$. In order to recurse, we need to ask queries between some pairs. We choose this pairs greedily, by calculating a minimum spanning tree (the edges have cost $\frac{1}{p_j-p_i+1}$). It can be also shown that, in the minimum spanning tree, the picked edges contain either $p_1$ or $p_k$, which makes the implementation easier.
    284 
    285 Empirically, this solution requires around $8$ robocoins per test case with $n = 100$.
    286 
    287 Bonus: prove the asymptotic behavior of the solution (idea: for each $(i, j)$, estimate the probability that the query is performed).
    288 
    289 **Code**
    290 
    291 [350380944](/contest/2157/submission/350380944 "Submission 350380944 by Dominater069")
    292 
    293 [2157H - Keygen 3](/contest/2157/problem/H)
    294 
    295 Author: [TheScrasse](/profile/TheScrasse "Grandmaster TheScrasse")  
    296  Preparation: [TheScrasse](/profile/TheScrasse "Grandmaster TheScrasse"), [Dominater069](/profile/Dominater069 "Legendary Grandmaster Dominater069")
    297 
    298 **Hint 1**
    299 
    300 Start with some "easy" pairs $(n, m)$. Which ones can you solve?
    301 
    302 **Hint 2**
    303 
    304 If you have a solution to $(n, m)$, can you transform it into a solution to $(n+1, m+1)$?
    305 
    306 **Hint 3**
    307 
    308 If you have a solution to $(n, m)$, can you transform it into a solution to $(n+1, m)$?
    309 
    310 **Hint 4**
    311 
    312 Find small $(n, m)$ with at least $2000$ solutions, and propagate these solutions to some bigger pairs.
    313 
    314 **Hint 5**
    315 
    316 Now some pairs are missing. They either have small $n$, or small $n-m$.
    317 
    318 **Hint 6**
    319 
    320 If $n-m$ is small, what can you say about the amount of $p_i = i$?
    321 
    322 **Hint 7**
    323 
    324 If $n-m$ is small, then $p_n$ must be large.
    325 
    326 **Solution**
    327 
    328 For convenience, let's find "anti-bitonic" permutations instead (decreasing, then increasing). There is a bijection between bitonic and anti-bitonic permutations.
    329 
    330 ```
    331 vector<int> f(vector<int> p) {
    332     int n = p.size();
    333     reverse(p.begin(), p.end());
    334     for (auto &u : p) u = n - u + 1;
    335     return p;
    336 }
    337 ```
    338 
    339 We can transform a solution to $(n, m)$ into a solution to $(n+1, m+1)$: just append $n+1$ at the end.
    340 
    341 We can also transform a solution to $(n, m)$ into a solution to $(n+1, m)$: append $n+1$ at the end, and swap $p_1$ with $p_1 + 1$.
    342 
    343 Let's divide into three cases:
    344 
    345 1. $n \le 18$;
    346 2. $n \ge 19$, $n - m \ge 10$;
    347 3. $n \ge 19$, $n - m \le 9$.
    348 
    349 They can be solved as follows.
    350 
    351 1. We can find all the anti-bitonic permutations and test them in $O(n \cdot 2^n)$.
    352 2. First, solve $(18, i)$ for $1 \leq i \leq 8$ (for each $i$, we have $\geq 2000$ solutions). Transform these solutions into solutions to $(n, m)$.
    353 3. $p_1, p_2, \ldots, p_n$ must have at least $n-9$ cycles, so it must have at least $n-18$ fixed points (i.e., $p_i = i$). The permutation structure is $[p_1, \ldots, p_1+1, p_1+2, \ldots, n]$: the highlighted square has at most $1$ fixed point, so there are at most $n-p_1+1$ fixed points. Therefore, $p_1 \leq 19$, and we can iterate over all such permutations.
    354 
    355 ![ ](/predownloaded/9a/5b/9a5b13ce637a2801895d6713af4f07d8e5365e83.png)
    356 
    357 **Code**
    358 
    359 [350381048](/contest/2157/submission/350381048 "Submission 350381048 by Dominater069")
    360 
    361 [2157I - Hyper Smawk Bros](/contest/2157/problem/I)
    362 
    363 Author: [TheScrasse](/profile/TheScrasse "Grandmaster TheScrasse")  
    364  Full solution: [dario2994](/profile/dario2994 "International Grandmaster dario2994")  
    365  Preparation: [TheScrasse](/profile/TheScrasse "Grandmaster TheScrasse"), [Dominater069](/profile/Dominater069 "Legendary Grandmaster Dominater069")
    366 
    367 **Hint 1**
    368 
    369 Solve the problem with even $m$.
    370 
    371 **Hint 2**
    372 
    373 Solve the problem with $t = 1$.
    374 
    375 **Hint 3**
    376 
    377 For a fixed $n$, how do "losing" $m$ look like?
    378 
    379 **Hint 4**
    380 
    381 Let $(n, l)$ ($0 \leq m$) be losing if you lose if it's your turn, the current integer is $n$, and you cannot subtract $l$.  
    382  If $(n, l)$ is losing, then $(n+l, l')$ with $l' \neq l$ is winning. This means that the number of losing $l$ for a fixed $n$ is either $0$, $1$, or $m+1$. Let's call $n$ "good", "neutral", and "evil", respectively.
    383 
    384 **Hint 5**
    385 
    386 How do the losing states $(n, l)$ look like?
    387 
    388 **Hint 6**
    389 
    390 Our goal is to solve $t = 1$ in $O(n/m)$.
    391 
    392 **Hint 7**
    393 
    394 How to determine efficiently whether some $n$ is good or neutral?
    395 
    396 **Hint 8**
    397 
    398 In order to determine whether some $n$ is good or neutral, you can write a recursive function which terminates in $O(1)$ on average.
    399 
    400 **Solution**
    401 
    402 #### Losing positions.
    403 
    404 Let $(n, l)$ ($0 \leq m$) be losing if you lose if it's your turn, the current integer is $n$, and you cannot subtract $l$ (if $l$ is $0$, you can subtract everything).
    405 
    406 #### Evil $n$.
    407 
    408 Let $n$ be evil if $(n, 0)$ is losing (i.e., you lose even without constraints on the number you subtract).
    409 
    410 #### Bound on the evil $n$ (I).
    411 
    412 There are $O(N/m)$ evil $n$. Specifically, let $v_1, v_2, \ldots, v_k$ be the evil $n \leq N$. Then, $v_i - v_{i-1} \geq m+1$ (otherwise you would be able to move from an evil $n$ to another, contradiction).
    413 
    414 #### Structure of losing positions and solution in $O(t(N+m))$.
    415 
    416 If $(n, l)$ is losing, then $(n+l, l')$ with $l' \neq l$ is winning. This means that the number of losing $l$ for a fixed $n$ is either $0$, $1$, or $m+1$. Let's call $n$ "good", "neutral", and "evil", respectively.  
    417  Note that the losing states are $O(N+m)$ in total.
    418 
    419 #### Even $m$.
    420 
    421 For even $m$, only the multiples of $m+1$ are evil. In order to win, you can ensure that the last two moves have sum $m+1$. Since $m+1$ is odd, the last move will never be the same as the second last.
    422 
    423 From now, let's only consider odd $m$.
    424 
    425 #### More structure.
    426 
    427 Let $f(n)$ be the distance from the largest evil $n' \leq n$.
    428 
    429 There are three types of losing states.
    430 
    431 * $(n, l)$ with $f(n) = 0$.
    432 * $(n, f(n))$.
    433 * $(n, f(n)/2)$ with $f(n) = m+1$.
    434 
    435 This is a consequence of the slow solution described above. If $s$ is evil:
    436 
    437 * the losing states $(s, l)$ propagate to $n$ in $[s+1, s+m]$;
    438 * only the losing state $(s + \frac{m+1}{2}, \frac{m+1}{2})$ can propagate to $(s+m+1, \frac{m+1}{2})$, and in that case $s+m+2$ is evil.
    439 
    440 So $s+m+1$ cannot be good (it is either neutral or evil).
    441 
    442 #### Bound on the evil $n$ (II).
    443 
    444 Let $v_1, v_2, \ldots, v_k$ be the evil $n \leq N$. Then, $m+1 \leq v_i - v_{i-1} \leq m+2$.
    445 
    446 ![ ](/predownloaded/07/f4/07f49d33c4a3656d3e15253c3dc8f2005130c4b7.png)
    447 
    448 #### Our goal.
    449 
    450 Let $v_1, v_2, \ldots, v_k$ be the evil $n \leq N$. We want to find them in $O(k) = O(N/m)$. In this way, we can solve the problem for all $m$ in $O(\sum_{1 \leq m \leq M} N/m) = O(N \log M)$.
    451 
    452 #### Finding $v_{i+1}$.
    453 
    454 We have $v_1, v_2, \ldots, v_i$, and we want to find $v_{i+1}$ in $O(1)$. It is enough to check whether $v_i + m + 1$ is evil. It's easier to check whether it is **not** evil, i.e., whether there exists a winning move.  
    455  Let's start from some $n$ which satisfies $v_j \leq n \leq v_{j+1}$. A winning move must ensure that the opponent cannot move to an evil state (necessary condition). So there are three candidate winning moves.
    456 
    457 * Subtracting $n-v_j+1$ (so that the opponent is too far from $v_{j-1}$; this can only work if $v_j-v_{j-1} = m+2$).
    458 * Subtracting $\frac{n-v_j}{2}$ (so that the opponent would have to subtract $\frac{n-v_j}{2}$ again to reach $v_j$).
    459 * Subtracting $\frac{n-v_{j-1}}{2}$ (so that the opponent would have to subtract $\frac{n-v_{j-1}}{2}$ again to reach $v_{j-1}$).
    460 
    461 #### Finding $v_{i+1}$ efficiently.
    462 
    463 The previous observation provides a recursive function which can call itself up to $3$ times.  
    464  The recursive function answers the question "can we win starting from $(n, n-v_j)$?" (i.e., it is forbidden to make the move which would win immediately). This is equivalent to "is $n$ good or neutral?"  
    465  We want to make the average number of recursive calls less than $1$, so that the function terminates in $O(1)$.
    466 
    467 * We do not need the first call, because $v_{j-1}+m+1$ is neutral (proved before).
    468 * The second call happens with probability $\lesssim 1/2$ ($n-v_j$ must be even, and the first case must not apply).
    469 * The third call happens with probability $\lesssim 3/8$ ($n-v_{j-1}$ must be even, the first case must not apply, and the second call must not succeed).
    470 
    471 So the function calls itself $\lesssim 7/8$ times on average. This is fast enough for all $m$ (it can be tested locally).
    472 
    473 **Code**
    474 
    475 [350381246](/contest/2157/submission/350381246 "Submission 350381246 by Dominater069")