codeforces-scrape

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

1854.md (21466B)


      1 Source: https://codeforces.com/blog/entry/118540
      2 
      3 The official implementations of all the problems are [here](https://drive.google.com/file/d/1stkidhN_ftTOzK4qcMYxkUAlwWWb3AqF/view?usp=sharing).
      4 
      5 [1855A - Dalton the Teacher](/contest/1855/problem/A "Codeforces Round 889 (Div. 2)")
      6 
      7 Author: [Kaey](/profile/Kaey "Master Kaey")  
      8  Preparation: [akifpatel](/profile/akifpatel "International Master akifpatel")
      9 
     10 **Hint 1**
     11 
     12 What's the most efficient way to make the sad students happy?
     13 
     14 **Hint 2**
     15 
     16 In most cases, you can make $2$ sad students happy in $1$ move.
     17 
     18 **Solution**
     19 
     20 Let $s$ be the number of sad students at the beginning. The answer is $\lceil \frac{s}{2} \rceil$.
     21 
     22 In one move, you can make at most $2$ sad students happy (because you can change the position of at most two students), so you need at least $\lceil \frac{s}{2} \rceil$ moves.
     23 
     24 In fact, you can make everyone happy in exactly $\lceil \frac{s}{2} \rceil$ moves:
     25 
     26 * while there are at least $2$ sad students, you can swap them and both of them will be happy;
     27 * if there is exactly $1$ sad student left, you can swap it with any other student.
     28 
     29 Complexity: $O(n)$
     30 
     31 [1855B - Longest Divisors Interval](/contest/1855/problem/B "Codeforces Round 889 (Div. 2)")
     32 
     33 Author: [TheScrasse](/profile/TheScrasse "International Grandmaster TheScrasse")  
     34  Preparation: [TheScrasse](/profile/TheScrasse "International Grandmaster TheScrasse")
     35 
     36 **Hint 1**
     37 
     38 What's the answer if $n$ is odd?
     39 
     40 **Hint 2**
     41 
     42 Try to generalize Hint 1.
     43 
     44 **Hint 3**
     45 
     46 What's the answer if $n$ is not a multiple of $3$?
     47 
     48 **Hint 4**
     49 
     50 If the answer is not a multiple of $x$, the answer is $ \lt x$. If the answer is a multiple of $1, \dots, x$, the answer is $\geq x$.
     51 
     52 **Solution**
     53 
     54 Suppose you find a valid interval $[l, r]$. Note that the interval $[l, r]$ contains at least one multiple of $x$ for each $1 \leq x \leq r-l+1$ (you can find it out by looking at the values in $[l, r]$ modulo $x$). Then, the interval $[1, r-l+1]$ is also valid and has the same length.
     55 
     56 So, it's enough to check intervals with $l = 1$, i.e., find the smallest $x$ that does not divide $n$. The answer is $x-1$.
     57 
     58 Complexity: $O(\log(\max n))$
     59 
     60 [1854A1 - Dual (Easy Version)](/contest/1854/problem/A1 "Codeforces Round 889 (Div. 1)")
     61 
     62 Author: [TheScrasse](/profile/TheScrasse "International Grandmaster TheScrasse")  
     63  Preparation: [akifpatel](/profile/akifpatel "International Master akifpatel")
     64 
     65 **Hint 1**
     66 
     67 There are several solutions to the easy version. In any case, how to get $a_i \leq a_{i+1}$?
     68 
     69 **Hint 2**
     70 
     71 For example, you can try making $a_{i+1}$ bigger using a positive element.
     72 
     73 What to do if all the elements are negative?
     74 
     75 **Hint 3**
     76 
     77 If all the elements are negative, you can win in $n-1$ moves.
     78 
     79 If there is a positive element, you can try to make $a_1 \leq a_2$, then $a_2 \leq a_3$, etc.
     80 
     81 **Hint 4**
     82 
     83 Make a big positive element using moves $(i, i)$, then make $a_2$ bigger.
     84 
     85 **Solution**
     86 
     87 If all the elements are negative, you can make suffix sums (they are nondecreasing) with moves $(n-1, n), (n-2, n-1), \dots$
     88 
     89 If there is at least one positive element $a_x$,
     90 
     91 * make $a_x \gt 20$ using $5$ moves $(x, x)$;
     92 * make $a_2$ the biggest element using $2$ moves $(2, x)$;
     93 * make $a_3$ the biggest element using $2$ moves $(3, 2)$;
     94 * ...
     95 
     96 This strategy requires $5 + 2(n-1) \leq 43$ moves.
     97 
     98 Complexity: $O(n)$
     99 
    100 [1854A2 - Dual (Hard Version)](/contest/1854/problem/A2 "Codeforces Round 889 (Div. 1)")
    101 
    102 Author: [TheScrasse](/profile/TheScrasse "International Grandmaster TheScrasse")  
    103  Preparation: [akifpatel](/profile/akifpatel "International Master akifpatel"), [dario2994](/profile/dario2994 "International Grandmaster dario2994")
    104 
    105 The hints and the solution continue from the easy version.
    106 
    107 **Hint 5**
    108 
    109 You can win in $n-1$ moves if all the elements are negative, but also if all the elements are positive.
    110 
    111 **Hint 6**
    112 
    113 Again, make a big positive / negative element, then use it to make everything positive / negative.
    114 
    115 **Hint 7**
    116 
    117 In how many moves can you either make everything positive or make everything negative?
    118 
    119 **Hint 8**
    120 
    121 Assume the positive elements are at least as many as the negative elements. Can you win in $34$ moves?
    122 
    123 **Hint 9**
    124 
    125 The bottleneck is making the big positive element. Is it always necessary? Can you find a better bound on the "best" number of moves?
    126 
    127 **Solution**
    128 
    129 If you either make everything positive or make everything negative, you can win in $n-1 \leq 19$ moves by making prefix sums or suffix sums, respectively. So, you have to reach one of these configurations in $12$ moves.
    130 
    131 How to make everything positive? First, you create a big element with the maximum absolute value (this requires $x_1$ moves), then you add it to every negative element (this requires $x_2$ moves). $y_1$ and $y_2$ are defined similarly in the negative case.
    132 
    133 So,
    134 
    135 * one of $x_1$ and $y_1$ is $0$ (because the element with the maximum absolute value at the beginning is either positive or negative), and the other one is $\leq 5$ (because you can make $|a_i| \geq 32$ in $5$ moves);
    136 * $x_2$ is the number of negative elements, $y_2$ is the number of positive elements. So, $x_2 + y_2 \leq n \leq 20$.
    137 
    138 Therefore, you need additional $\min(x_1 + x_2, y_1 + y_2)$ moves. Since $x_1 + x_2 + y_1 + y_2 \leq 25$, $\min(x_1 + x_2, y_1 + y_2) \leq \lfloor \frac{25}{2} \rfloor = 12$, as we wanted. Now you can simulate the process in both cases (positive and negative), and choose one that requires $\leq 31$ moves in total.
    139 
    140 Complexity: $O(n)$
    141 
    142 [1854B - Earn or Unlock](/contest/1854/problem/B "Codeforces Round 889 (Div. 1)")
    143 
    144 Author: [TheScrasse](/profile/TheScrasse "International Grandmaster TheScrasse")  
    145  Preparation: [akifpatel](/profile/akifpatel "International Master akifpatel")
    146 
    147 **Hint 1**
    148 
    149 The order of used cards doesn't matter. So, you can assume you always use the card on the top.
    150 
    151 **Hint 2**
    152 
    153 Suppose that you unlock $x$ cards in total. How many points can you get?
    154 
    155 **Hint 3**
    156 
    157 If you unlock $x$ cards, it means you end up making moves with the first $x$ cards. So, you know the total number of (cards + points) that you get.
    158 
    159 **Hint 4**
    160 
    161 If you unlock $x$ cards, the number of points is uniquely determined. It's convenient to assume that $x \leq 2n$ and the cards $n+1, \dots, 2n$ have value $0$.
    162 
    163 **Hint 5**
    164 
    165 Now you have to determine the unlockable prefixes of cards (i.e., the values of $x$ you can reach). It looks similar to knapsack.
    166 
    167 **Hint 6**
    168 
    169 You can optimize the solution using a bitset. Be careful not to use locked cards.
    170 
    171 **Solution**
    172 
    173 First, note that the order of used cards doesn't matter. If you use at least once a card that is not on the top on the deck, you can prove that using the cards in order (from the top) would give the same number of victory points.
    174 
    175 Let's add $n$ cards with value $0$ at the end of the deck. Then, it's optimal to unlock $x \leq 2n$ cards, and use cards $1, \dots, x$, getting $a_1 + \dots + a_x - x + 1$ points.
    176 
    177 Let's find the reachable $x$. Let $dp_i$ be a bitset that stores the reachable $x$ after using the first $i$ cards.
    178 
    179 * Base case: $dp_{0,1} = 1$.
    180 * Transitions: first, $dp_{i}$ `|=` $dp_{i-1}$ `<<` $a_i$. If $dp_{i,i} = 1$, you can update the answer with $a_1 + \dots + a_i - i + 1$, but you can't unlock any other card, so you have to set $dp_{i,i} = 0$ before transitioning to $i+1$.
    181 
    182 Complexity: $O(n^2/w)$
    183 
    184 [1854C - Expected Destruction](/contest/1854/problem/C "Codeforces Round 889 (Div. 1)")
    185 
    186 Author: [TheScrasse](/profile/TheScrasse "International Grandmaster TheScrasse")  
    187  Preparation: [akifpatel](/profile/akifpatel "International Master akifpatel")
    188 
    189 **Hint 1**
    190 
    191 Consider $n$ blocks in positions $S_1, S_2, \dots, S_n$. After how much time does block $x$ disappear? It may be convenient to put a fake "static" block in position $m+1$.
    192 
    193 **Hint 2**
    194 
    195 Block $x$ disappears when it reaches block $x+1$. But what if block $x+1$ disappears before block $x$?
    196 
    197 **Hint 3**
    198 
    199 From the perspective of block $x$, it's convenient to assume that block $x+1$ never disappears: when it touches another block $y$, it's $y$ that disappears.
    200 
    201 **Hint 4**
    202 
    203 When you consider the pair of blocks $x, x+1$, the other blocks don't really matter, and you can use linearity of expectation to calculate the contribution of each pair independently.
    204 
    205 A reasonable interpretation is given by considering an $(n+1) \times (m+1)$ grid, where the $i$-th row initially contains a block in column $S_i$. Then, you are calculating the expected time required for the blocks $1, \dots, m$ to have another block immediately below them (in the same column).
    206 
    207 **Hint 5**
    208 
    209 Blocks $x, x+1$ both move with probability $1/2$, unless block $x+1$ has reached position $m+1$.
    210 
    211 **Hint 6**
    212 
    213 $dp_{i,j} =$ expected number of moves of block $x$ before it disappears, if the block $x$ is in position $i$ and the block $x+1$ is in position $j$.
    214 
    215 **Solution**
    216 
    217 Consider an $(n+1) \times (m+1)$ grid, where the $i$-th row initially contains a block in column $S_i$, and row $n+1$ contains a block in column $m+1$.
    218 
    219 * The set is empty if all the blocks are in column $m+1$; i.e., if every block has reached the block in the following row.
    220 * Every "connected component" of blocks (except the last one) represents an element in the set. These components move equiprobably.
    221 
    222 Let's calculate the expected time required for the block in row $x$ to "reach" the block in row $x+1$. If you consider a single pair of blocks, every block moves with probability $1/2$, unless block $x+1$ is in column $m+1$.
    223 
    224 So, you can calculate $dp_{i,j} =$ expected number of moves of the block $x$ before it reaches the block $x+1$, if the block $x$ is in position $i$ and the block $x+1$ is in position $j$.
    225 
    226 The base cases are $dp_{i,m+1} = (m+1)-i$ (because only the block $x$ can move) and $dp_{i,i} = 0$ (because block $x$ has already reached block $x+1$). In the other cases, $dp_{i,j} = ((dp_{i+1,j} + 1) + dp_{i,j+1})/2$.
    227 
    228 By linearity of expectation, the answer is the sum of $dp_{S_i, S_{i+1}}$.
    229 
    230 Complexity: $O(m^2)$
    231 
    232 [1854D - Michael and Hotel](/contest/1854/problem/D "Codeforces Round 889 (Div. 1)")
    233 
    234 Author: [TheScrasse](/profile/TheScrasse "International Grandmaster TheScrasse")  
    235  Preparation: [akifpatel](/profile/akifpatel "International Master akifpatel")
    236 
    237 **Hint 1**
    238 
    239 You can find any $a_i$ in $9$ queries.
    240 
    241 **Hint 2**
    242 
    243 Find the nodes in the cycle in the component with node $1$. What happens if you know the whole cycle?
    244 
    245 **Hint 3**
    246 
    247 Suppose you already know some nodes in the cycle. Can you find other nodes faster?
    248 
    249 **Hint 4**
    250 
    251 Can you "double" the number of nodes in the cycle?
    252 
    253 **Solution**
    254 
    255 The component with node $1$ contains a cycle. If you know the whole cycle (of length $x$), you can win in $n-x$ queries by asking for each node if it ends up in the cycle after $n$ moves.
    256 
    257 You can get a node in the cycle in $9$ queries, doing a binary search on the $n$-th successor of node $1$.
    258 
    259 How to find the rest of the cycle?
    260 
    261 * First, find $k$ nodes in the cycle, doing a binary search on the successor of the last node found. These nodes make a set $C$.
    262 * Then, check for each node if it's "sufficiently close" to $C$, by asking $(i, k, C)$. Now, you know either $2k$ nodes in the cycle, or the whole cycle.
    263 * Repeat until you get the whole cycle.
    264 
    265 If you choose $k = 63$, you spend at most $9 \cdot 63 + (500 - 63) + (500 - 126) + (500 - 252) + (500 - 252) = 1874$ queries.
    266 
    267 [1854E - Game Bundles](/contest/1854/problem/E "Codeforces Round 889 (Div. 1)")
    268 
    269 Author: [dario2994](/profile/dario2994 "International Grandmaster dario2994")  
    270  Preparation: [akifpatel](/profile/akifpatel "International Master akifpatel"), [dario2994](/profile/dario2994 "International Grandmaster dario2994")
    271 
    272 **Hint 1**
    273 
    274 Go for a randomized approach.
    275 
    276 **Hint 2**
    277 
    278 Many ones are useful.
    279 
    280 **Hint 3**
    281 
    282 Either you go for a greedy or for a backpack.
    283 
    284 **Solution**
    285 
    286 We describe a randomized solution that solves the problem for $m$ up to $10^{11}$ (and, with some additional care, may be able to solve also $m$ up to $10^{12}$). We decided to give the problem with the smaller constraint $m\le 10^{10}$ to make the problem more accessible and because there may be some rare cases below $10^{11}$ for which our solution is too slow (even though we could not find any). We don't know any provably correct solution, if you have one we would be curious to see it. We expect to see many different solutions for this problem.
    287 
    288 **Main idea:** Choose suitably the values $a_1, a_2, \dots, a_h$ that belong to $[1,29]$ and then find $a_{h+1}, a_{h+2},\dots,a_k$ in $[31,60]$ by solving a backpack-like problem.
    289 
    290 Let us describe more precisely the main idea. Assume that $a_1, a_2, \dots, a_h\le 30$ are fixed and they satisfy $a_1+a_2+\cdots+a_h \lt 60$. For any $s=0,1,2,\dots,29$, let $f(s)$ be the number of subsets $I\subseteq{1,2,\dots,h}$ so that $\sum_{i\in I}a_i=s$. If we can find some values $0\le s_1,s_2,\dots,s_{k-h}\le 29$ so that $f(s_1)+f(s_2)+\cdots+f(s_{k-h})=s$, then by setting $a_{h+i} = 60-s_i$ for $i=1,2,\dots, k-h$ we have found a valid solution to the problem.
    291 
    292 There are two main difficulties:
    293 
    294 * How can we find $s_1, s_2,\dots, s_{k-h}$?
    295 * How should we choose $a_1, a_2,\dots, a_h$?
    296 
    297 Since it is important to get a good intuitive understanding of the computational complexity of the algorithm, let us say now that we will choose $h\le 44$ and (accordingly) $k-h=16$. These values are flexible (the solution would still work with $h\le 45$ and $k-h=45$ for example). We will say something more about the choice of these values when we will describe how $a_1,a_2,\dots, a_h$ shall be chosen.
    298 
    299 **The backpack problem to find $s_1, s_2,\dots, s_{k-h}$.**
    300 
    301 The naive way to find $s_1,\dots, s_{k-h}$ would be to try all of them. There are $\binom{k-h + 29}{29}$ possible ways (up to order, which does not matter). Since $k-h=16$ this number is $\approx 2\cdot 10^{11}$ which is too much to fit in the time limit.
    302 
    303 To speed up the process, we will do as follows. Partition randomly $A\cup B={0,1,\dots, 29}$ into two sets of size $15$. We iterate over all possible $s_1, s_2, \dots, s_{(k-h)/2}\in A$ and over all possible $s_{(k-h)/2+1},\dots, s_{k-h}\in B$ and check whether the sum of one choice from the first group and one choice from the second group yields the result. This is a standard optimization for the subset sum problem. What is its complexity? It can be implemented in linear time in the size of the two groups we have to iterate over, which have size $\binom{(k-h)/2+15}{15}\approx 5\cdot 10^5$. Notice that in this faster way we will not visit all the $\binom{k-h+29}{29}$ possible choices $s_1,s_2,\dots, s_{k-h}$ because we are assuming that exactly half of them belong to $A$ and exactly half of them belong to $B$. This is not a big deal because with sufficiently high probability we will find a solution in any case.
    304 
    305 **The choice of $a_1, a_2,\dots, a_{h}$.**
    306 
    307 It remains to decide how we should select $a_1, a_2, \dots, a_{h}$. The following choice works:
    308 
    309 * Approximately the first $\log_2(m)$ values are set equal to $1$.
    310 * Five additional values are chosen randomly from $[1, 6]$ so that the total sum stays below $60$.
    311 
    312 One should repeat the whole process until a solution is found.
    313 
    314 **Some intuition on the construction.** The choice of $a_1, \dots, a_{h}$ may seem arbitrary; let us try to justify it. The goal is to generate a set of values $f(0), f(1),\dots, f(29)$ that are simultaneously ``random enough'' and with size smaller but comparable to $m$. These two conditions are necessary to expect that the backpacking problem finds a solution with high enough probability.
    315 
    316 If $a_1=a_2=\cdots=a_{h}=1$, then $f(s) = \binom{k-h}{s}$ and these numbers have size comparable to $m$ if $2^{h}$ is comparable to $m$. This observation explains why we start with approximately $\log_2(m)$ ones. The issue is that we need some flexibility in the process as we may need to repeat it many times, this flexibility is provided by the addition of some additional random elements which don't change the magnitude of the values $f(0), f(1), \dots, f(29)$ but that modify them as much as possible (if we added a large number it would not affect many $f(s)$ and thus it would not be very useful).
    317 
    318 [1854F - Mark and Spaceship](/contest/1854/problem/F "Codeforces Round 889 (Div. 1)")
    319 
    320 Author: [dario2994](/profile/dario2994 "International Grandmaster dario2994")  
    321  Preparation: [akifpatel](/profile/akifpatel "International Master akifpatel"), [dario2994](/profile/dario2994 "International Grandmaster dario2994")
    322 
    323 **Hint 1**
    324 
    325 Solve the 2d version first.
    326 
    327 **Hint 2**
    328 
    329 The 4d version is not too different from the 2d one.
    330 
    331 **Hint 3**
    332 
    333 Find all the points such that the expected number of necessary moves is wrong.
    334 
    335 **Solution**
    336 
    337 ### **The $2$-dimensional case.**
    338 
    339 Let us begin by cpnsidering the $2$-dimensional version of the problem. The solution to this simpler version provides the idea of the approach for the $4$-dimensional version.
    340 
    341 We want to reach $(a, b)$. Can we do it with exactly $k$ moves? Two simple necessary conditions are:
    342 
    343 * $|a|+|b|\le 1 + 2 + \cdots + k$,
    344 * $a+b$ and $1 + 2 + \cdots + k$ shall have the same parity.
    345 
    346 It turns out that this two conditions are also sufficient! One can prove it by induction on $k$ as follows. If $k=0$ or $k=1$ or $k=2$ the statement is simple, thus we may assume $k\ge 3$.
    347 
    348 Without loss of generality we may assume $0\le a\le b$. If $|a|+|b-k| \le 1 + 2 + \cdots + k-1$, then the statement follows by inductive hypothesis. Assume by contradiction that such inequality is false. If $b\ge k$ then we have a contradiction because $|a|+|b-k| = |a|+|b|-k \le (1 + 2 + \cdots + k) - k$. Otherwise $b \lt k$ and the contradiction is $|a|+|b-k| = a + k-b \le k \le 1 + 2 + \cdots + k-1$.
    349 
    350 Hence, we have shown:
    351 
    352 **Lemma 1:** The point $(a, b)$ is reachable with exactly $k$ moves if and only if $|a|+|b| \le 1 + 2 + \cdots + k$ and $a+b$ has the same parity of $1+2+\cdots + k$.
    353 
    354 ### **The $4$-dimensional case.**
    355 
    356 One may expect statement analogous to the one of Lemma 1 to hold also when there are $4$ coordinates. It does not, but it *almost* does and this is the crucial idea of the solution. More precisely, the number of counter examples to such statement is rather small and we can find all of them. This is the intuition behind the following definition.
    357 
    358 **Definition:** For $k\ge 0$, let $A_k$ be the set of points $(a, b, c, d)$ such that $|a|+|b|+|c|+|d|\le 1 + 2 + \cdots + k$ and $a+b+c+d$ has the same parity of $1 + 2 + \cdots + k$ but $(a, b, c, d)$ is not reachable with exactly $k$ moves.
    359 
    360 As an immediate consequence of the definition, we have
    361 
    362 **Observation:** The point $(a, b, c, d)$ is reachable with exactly $k$ moves if and only if $|a|+|b|+|c|+|d| \le 1 + 2 + \dots + k$ and $a+b+c+d$ has the same parity of $1+2+\cdots + k$ and $(a, b, c, d)\not\in A_k$.
    363 
    364 Thanks to this observation, if one is able to efficiently find $A_k$ for all interesting values of $k$, then solving the problem is (comparatively) easy. The following lemma is our main tool for this purpose.
    365 
    366 **Lemma 2:** Assume that $(a, b, c, d) \in A_k$ with $0\le a\le b\le c\le d$. Then, either $k\le 6$ or $(a, b, c, d - k) \in A_{k-1}$.
    367 
    368 **Proof:** The strategy is the same adopted to show Lemma 1. In some sense, we are saying that the inductive step works also in dimension $4$, but the base cases don't.
    369 
    370 If $|a|+|b|+|c|+|d-k|\le 1 + 2 + \cdots + k-1$, then it must be $(a, b, c, d-k)\in A_{k-1}$ because if $(a, b, c, d-k$ were reachable with $k-1$ moves then $(a, b, c, d)$ were reachable with $k$ and we know that this is not true.
    371 
    372 Assume by contradiction that $|a|+|b|+|c|+|d-k| \gt 1 + 2 + \cdots + k-1$. If $d\ge k$ then we reach the contradiction $|a|+|b|+|c|+|d-k| = a+b+c+d-k \le (1 + 2 + \dots + k) - k$. Otherwise, $d \lt k$ and thus we reach the contradiction $|a|+|b|+|c|+|d-k| = a+b+c+k-d\le a+b+k\le 3k-2\le 1 + 2 + \dots + k-1$ (for $k\ge 7$).
    373 
    374 We can now describe the solution. Assume that we know $A_{k-1}$. First of all, notice that it is then possible to determine in $O(1)$ whether a point belongs to $A_k$ or not. To generate a list of candidate elements for $A_k$ we proceed as follows:
    375 
    376 * If $k\le 6$, we simply iterate over all points with $|a|+|b|+|c|+|d|\le 1 + 2 + \cdots + k$.
    377 * Otherwise, we iterate over the points in $A_{k-1}$ and we consider as candidate elements for $A_k$ the points that can be obtained by changing the value of one coordinate by $k$.
    378 
    379 Thanks to Lemma 2, we know that this process finds all the elements in $A_k$. Once $A_0, A_1, A_2, A_3,\dots$ are known, the problem boils down to a (relatively) simple counting argument that we skip.
    380 
    381 One can verify that to handle correctly all points with coordinates up to $1000$ it is necessary to compute $A_k$ for $0\le k \le 62$.
    382 
    383 One additional cheap trick is required to make $A_k$ sufficiently small and get a sufficiently fast solution. Given $(a, b, c, d)$, the instance of the problem is equivalent if we change the signs of the coordinates or we change the order of the coordinates. Hence we shall always ``normalize'' the point so that $0\le a \le b\le c\le d$. If we do this consistently everywhere in the process, the solution becomes an order of magnitude faster. In particular, this trick guarantees $|A_k|\le 5000$ for all $0\le k\le 62$.
    384 
    385 **Bonus question:** Find an explicit closed form for the elements in $A_k$ for any $k$. (in this way one can solve the problem also with larger constraints on $A, B, C, D$; but it is tedious)