codeforces-scrape

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

2018.md (18063B)


      1 Source: https://codeforces.com/blog/entry/134420
      2 
      3 All the Polygon materials (including the official implementations of all the problems) are [here](https://drive.google.com/file/d/1zWk5N_iF3TWbzzab5IAIza78_FohSZtP/view?usp=sharing).
      4 
      5 [2019A - Max Plus Size](/contest/2019/problem/A "Codeforces Round 975 (Div. 2)")
      6 
      7 Author: [TheScrasse](/profile/TheScrasse "International Grandmaster TheScrasse")  
      8  Preparation: [TheScrasse](/profile/TheScrasse "International Grandmaster TheScrasse")
      9 
     10 **Hint 1**
     11 
     12 Can you reach the score $\max(a) + \lceil n/2 \rceil$?
     13 
     14 **Hint 2**
     15 
     16 Can you reach the score $\max(a) + \lceil n/2 \rceil - 1$?
     17 
     18 **Solution**
     19 
     20 The maximum red element is $\leq \max(a)$, and the maximum number of red elements is $\lceil n/2 \rceil$. Can you reach the score $\max(a) + \lceil n/2 \rceil$?
     21 
     22 * If $n$ is even, you always can, by either choosing all the elements in even positions or all the elements in odd positions (at least one of these choices contains $\max(a)$).
     23 * If $n$ is odd, you can if and only if there is one occurrence of $\max(a)$ in an odd position. Otherwise, you can choose even positions and your score is $\max(a) + \lceil n/2 \rceil - 1$.
     24 
     25 Complexity: $O(n)$
     26 
     27 [2019B - All Pairs Segments](/contest/2019/problem/B "Codeforces Round 975 (Div. 2)")
     28 
     29 Author: [TheScrasse](/profile/TheScrasse "International Grandmaster TheScrasse")  
     30  Preparation: [TheScrasse](/profile/TheScrasse "International Grandmaster TheScrasse")
     31 
     32 **Hint 1**
     33 
     34 Can you determine fast how many intervals contain point $p$?
     35 
     36 **Hint 2**
     37 
     38 The intervals that contain point $p$ are the ones with $l \leq p$ and $r \geq p$.
     39 
     40 **Hint 3**
     41 
     42 Determine how many intervals contain:
     43 
     44 * point $x_1$;
     45 * points $x_1 + 1, \ldots, x_2 - 1$;
     46 * point $x_2$;
     47 * $\ldots$
     48 * point $x_n$.
     49 
     50 **Solution**
     51 
     52 First, let's focus on determining how many intervals contain some point $x$. These intervals are the ones with $l \leq x$ and $x \leq r$.
     53 
     54 So a point $x_i \lt p \lt x_{i+1}$ satisfies $x_1 \leq p, \ldots, x_i \leq p$, and $p \leq x_{i+1}, \ldots, p \leq x_n$. It means that you have found $x_{i+1} - x_i - 1$ points contained in exactly $i(n-i)$ intervals (because there are $i$ possible left endpoints and $n-i$ possible right endpoints).
     55 
     56 Similarly, the point $p = x_i$ is contained in $i(n-i+1) - 1$ intervals (you have to remove interval $[x_i, x_i]$, which you do not draw).
     57 
     58 So you can use a map that stores how many points are contained in exactly $x$ intervals, and update the map in the positions $i(n-i)$ and $i(n-i+1) - 1$.
     59 
     60 Complexity: $O(n \log n)$
     61 
     62 [2018A - Cards Partition](/contest/2018/problem/A "Codeforces Round 975 (Div. 1)")
     63 
     64 Author: [TheScrasse](/profile/TheScrasse "International Grandmaster TheScrasse")  
     65  Preparation: [TheScrasse](/profile/TheScrasse "International Grandmaster TheScrasse")
     66 
     67 **Hint 1**
     68 
     69 The answer is at most $n$.
     70 
     71 **Hint 2**
     72 
     73 Solve the problem with $k = 0$.
     74 
     75 **Hint 3**
     76 
     77 When is the answer $n$?
     78 
     79 **Hint 4**
     80 
     81 If the answer is not $n$, how can you buy cards?
     82 
     83 **Solution**
     84 
     85 Note that there are $n$ types of cards, so the subsets have size at most $n$, and the answer is at most $n$.
     86 
     87 If $k = 0$, you can make subsets of size $s$ if and only if the following conditions are true:
     88 
     89 * the number of cards ($m$) is a multiple of $s$;
     90 * the maximum number of cards of some type ($x$) is $\leq m/s$.
     91 
     92 Proof:
     93 
     94 * $m$ is the number of decks times $s$.
     95 * The number of decks is $m/s$. Each deck can contain at most $1$ card of each type, so there are at most $m/s$ cards of each type in total.
     96 * If the two conditions above hold, you can make a deck containing the $s$ types of cards with maximum frequency. You can show with some calculations that the conditions still hold after removing these cards. So you can prove by induction that the two conditions are sufficient to make decks of size $s$.
     97 
     98 The same idea is used in problems like [1954D - Colored Balls](/contest/1954/problem/D "Educational Codeforces Round 164 (Rated for Div. 2)") and [abc227_d - Project Planning](https://atcoder.jp/contests/abc227/tasks/abc227_d).
     99 
    100 For a generic $k$, the answer is $n$ if you can make the number of cards of type $1, \ldots, n$ equal. Otherwise, for any choice of number of cards to buy, you can buy them without changing $x$. It means that you need $x \cdot s$ cards in total:
    101 
    102 * if you have less than $x \cdot s$ cards, you have to check if you can reach $x \cdot s$ cards by buying at most $k$ new cards;
    103 * if you already have $x \cdot s$ or more cards at the beginning, you have to check if you can make $m$ a multiple of $s$.
    104 
    105 Complexity: $O(n)$
    106 
    107 [2018B - Speedbreaker](/contest/2018/problem/B "Codeforces Round 975 (Div. 1)")
    108 
    109 Author: [TheScrasse](/profile/TheScrasse "International Grandmaster TheScrasse")  
    110  Preparation: [TheScrasse](/profile/TheScrasse "International Grandmaster TheScrasse")
    111 
    112 **Hint 1**
    113 
    114 When is the answer $0$?
    115 
    116 **Hint 2**
    117 
    118 Starting from city $x$ is equivalent to setting $a_x = 1$.
    119 
    120 **Solution**
    121 
    122 At some time $t$, consider the minimal interval $[l, r]$ that contains all the cities with $a_i \leq t$ (let's call it "the minimal interval at time $t$"). You have to visit all this interval within time $t$, otherwise there are some cities with $a_i \leq t$ which you do not visit in time. So if this interval has length $ \gt t$, you cannot visit it all within time $t$, and the answer is $0$.
    123 
    124 Otherwise, the answer is at least $1$. A possible construction is visiting "the minimal interval at time $1$", then "the minimal interval at time $2$", ..., then "the minimal interval at time $n$". Note that, when you visit "the minimal interval at time $t$", the actual time is equal to the length of the interval, which is $\leq t$. In this way, at time $t$ you will have conquered all the cities in the minimal interval at time $t$, and possibly other cities.
    125 
    126 Starting from city $x$ is equivalent to setting $a_x = 1$. After this operation, you have to guarantee that, for each $i$, the minimal interval at time $t$ is short enough. If this interval is $[l, r]$ before the operation, it can become either $[x, r]$ (if $x \lt l$), or $[l, x]$ (if $x \gt r$), or stay the same. In all this cases, the resulting length must be $\leq t$. With some calculations (e.g., $r-x+1 \leq t$), you can get than $x$ must be contained in $[r-t+1, l+t-1]$. So it's enough to calculate and intersect the intervals obtained at $t = 1, \ldots, n$, and print the length of the final interval.
    127 
    128 You can calculate the minimal intervals by iterating on the cities in increasing order of $a_i$. Again, if the old interval is $[l, r]$ and the new city has index $x$, the new possible intervals are $[x, r]$, $[l, r]$, $[l, x]$.
    129 
    130 Another correct solution is to intersect the intervals $[i-a_i+1, i+a_i-1]$. The proof is contained in the editorial of [2018F3 - Speedbreaker Counting (Hard Version)](/contest/2018/problem/F3 "Codeforces Round 975 (Div. 1)").
    131 
    132 Complexity: $O(n)$
    133 
    134 [2018C - Tree Pruning](/contest/2018/problem/C "Codeforces Round 975 (Div. 1)")
    135 
    136 Author: [wksni](/profile/wksni "Newbie wksni")  
    137  Preparation: [TheScrasse](/profile/TheScrasse "International Grandmaster TheScrasse")
    138 
    139 **Hint 1**
    140 
    141 Solve for a fixed final depth of the leaves.
    142 
    143 **Hint 2**
    144 
    145 Which nodes are "alive" if all leaves are at depth $d$ at the end?
    146 
    147 **Solution**
    148 
    149 If the final depth of the leaves is $d$, it's optimal to keep in the tree all the nodes at depth $d$ and all their ancestors. These nodes are the only ones which satisfy the following two conditions:
    150 
    151 * their depth ($a_i$) is $\leq d$;
    152 * the maximum depth of a node in their subtree ($b_i$) is $\geq d$.
    153 
    154 So every node is alive in the interval of depths $[a_i, b_i]$. The optimal $d$ is the one contained in the maximum number of intervals.
    155 
    156 [2018D - Max Plus Min Plus Size](/contest/2018/problem/D "Codeforces Round 975 (Div. 1)")
    157 
    158 Author: [TheScrasse](/profile/TheScrasse "International Grandmaster TheScrasse")  
    159  Preparation: [TheScrasse](/profile/TheScrasse "International Grandmaster TheScrasse")
    160 
    161 **Hint 1**
    162 
    163 The optimal subsequence must contain at least one occurrence of the maximum.
    164 
    165 **Hint 2**
    166 
    167 Iterate over the minimum, in decreasing order.
    168 
    169 **Hint 3**
    170 
    171 You have some "connected components". How many elements can you pick from each component? How to make sure you have picked at least one occurrence of the maximum?
    172 
    173 **Solution**
    174 
    175 The optimal subsequence must contain at least one occurrence of the maximum ($r$) (suppose it doesn't; then you can just add one occurrence, at the cost of removing at most two elements, and this does not make your score smaller).
    176 
    177 Now you can iterate over the minimum value ($l$), in decreasing order. At any moment, you can pick elements with values $[l, r]$. Then you have to support queries "insert pick-able element" and "calculate score".
    178 
    179 The pick-able elements make some "connected components" of size $s$, and you can pick $\lceil s/2 \rceil$ elements. You can maintain the components with a DSU.
    180 
    181 You also want to pick an element with value $r$. For each component, check if it contains $r$ in a subsequence with maximum size. If this does not happen for any component, your score decreases by $1$. All this information can be maintained by storing, for each component, if it contains $r$ in even positions, and if it contains $r$ in odd positions.
    182 
    183 Complexity: $O(n \alpha(n))$
    184 
    185 [2018E1 - Complex Segments (Easy Version)](/contest/2018/problem/E1 "Codeforces Round 975 (Div. 1)"), [2018E2 - Complex Segments (Hard Version)](/contest/2018/problem/E2 "Codeforces Round 975 (Div. 1)")
    186 
    187 Authors: [lorenzoferrari](/profile/lorenzoferrari "Candidate Master lorenzoferrari"), [TheScrasse](/profile/TheScrasse "International Grandmaster TheScrasse")  
    188  Full solution: [Flamire](/profile/Flamire "Legendary Grandmaster Flamire")  
    189  Preparation: [francesco](/profile/francesco "Master francesco"), [lorenzoferrari](/profile/lorenzoferrari "Candidate Master lorenzoferrari")
    190 
    191 **Hint 1**
    192 
    193 Solve for a fixed $m$ (size of the subsets).
    194 
    195 **Hint 2**
    196 
    197 $m = 1$ is easy. Can you do something similar for other $m$?
    198 
    199 **Hint 3**
    200 
    201 Solve for a fixed $k$ (number of subsets).
    202 
    203 **Hint 4**
    204 
    205 If you have a $O(n \log n)$ solution for a fixed $m$, note that there exists a faster solution!
    206 
    207 **Solution**
    208 
    209 Let's write a function `max_k(m)`, which returns the maximum $k$ such that there exists a partition of $k$ valid sets containing $m$ intervals each. `max_k` works in $O(n \log n)$ in the following way (using a lazy segment tree):
    210 
    211 * (wlog) $r_i \leq r_{i+1}$;
    212 * for each $i$ not intersecting the previous subset, add $1$ on the interval $[l[i], r[i]]$;
    213 * as soon as a point belongs to $m$ intervals, they become a subset;
    214 * return the number of subsets.
    215 
    216 For a given $k$, you can binary search the maximum $m$ such that `max_k(m)` $\geq k$ in $O(n \log^2 n)$.
    217 
    218 The problem asks for the maximum $mk$. Since $mk \leq n$, for any constant $C$ either $m \leq C$ or $k \leq n/C$. For $C = (n \log n)^{1/2}$, the total complexity becomes $O((n \log n)^{3/2})$, which is enough to solve [2018E1 - Complex Segments (Easy Version)](/contest/2018/problem/E1 "Codeforces Round 975 (Div. 1)"). You can also find `max_k(m)` for all $m$ with a divide and conquer approach, and the complexity becomes $O(n \sqrt n \log n)$ (see [here](https://codeforces.com/blog/entry/134445)).
    219 
    220 Now let's go back to `max_k(m)`. It turns out you can implement it in $O(n \alpha(n))$.
    221 
    222 First of all, let's make all the endpoints distinct, in such a way that two intervals intersect if and only if they were intersecting before.
    223 
    224 Let's maintain a binary string of size $n$, initially containing only ones, that can support the following queries:
    225 
    226 * set bit in position $p$ to `0`;
    227 * find the nearest `1` to the left of position $p$.
    228 
    229 This can be maintained with DSU, where the components are the maximal intervals containing `100...00`.
    230 
    231 Now let's reuse the previous solution (sweeping $r$ from left to right), but instead of a segment tree we will maintain a binary string with the following information:
    232 
    233 * the positions $ \gt r$ store `1`;
    234 * the positions $\leq r$ store `1` if and only if the value in that position (in the previous solution) is a suffix max.
    235 
    236 So the queries become:
    237 
    238 * add $1$ to $[l, r]$:
    239 * + $r$ changes, so you have to set elements in $[r'+1, r-1]$ to $0$;
    240 * + the only other element that changes is the nearest `1` to the left of position $l$, which does not represent a suffix max anymore.
    241 * find the maximum: it's equal to the number of suffix maximums, which depends on $r$ and on the number of components.
    242 
    243 This solution allows us to replace a $O(\log n)$ factor with a $O(\alpha(n))$ factor.
    244 
    245 Complexity: $O(n \sqrt n \alpha(n))$
    246 
    247 [Bonus: there exists a data structure faster than DSU to solve the subproblem above, so you can solve the problem in $O(n \sqrt n)$. See [here](https://codeforces.com/blog/entry/134445).]
    248 
    249 [2018F1 - Speedbreaker Counting (Easy Version)](/contest/2018/problem/F1 "Codeforces Round 975 (Div. 1)"), [2018F2 - Speedbreaker Counting (Medium Version)](/contest/2018/problem/F2 "Codeforces Round 975 (Div. 1)"), [2018F3 - Speedbreaker Counting (Hard Version)](/contest/2018/problem/F3 "Codeforces Round 975 (Div. 1)")
    250 
    251 Author: [TheScrasse](/profile/TheScrasse "International Grandmaster TheScrasse")  
    252  Full solution: [Flamire](/profile/Flamire "Legendary Grandmaster Flamire")  
    253  Preparation: [TheScrasse](/profile/TheScrasse "International Grandmaster TheScrasse")
    254 
    255 **Hint 1**
    256 
    257 Suppose you are given a starting city and you want to win. Find several strategies to win (if possible) and try to work with the simplest ones.
    258 
    259 **Hint 2**
    260 
    261 The valid starting cities are either zero, or all the cities in $I := \cap_{i=1}^n [i - a_i + 1, i + a_i - 1] = [l, r]$.
    262 
    263 **Hint 3**
    264 
    265 Now you have some bounds on the $a_i$.
    266 
    267 **Hint 4**
    268 
    269 Fix the interval $I$ and try to find a (slow) DP.
    270 
    271 **Hint 5**
    272 
    273 Counting paths seems easier than counting arrays. Make sure that, for each array, you make exactly one path (or a number of paths which is easy to handle).
    274 
    275 **Hint 6**
    276 
    277 How many distinct states do you calculate in your DP?
    278 
    279 **Solution**
    280 
    281 ### Lemma 1
    282 
    283 For a fixed starting city, if you can win, this strategy works:
    284 
    285 * [Strategy 1] If there is a city on the right whose distance is $t$ and whose deadline is in $t$ turns, go to the right. Otherwise, go to the left.
    286 
    287 Proof:
    288 
    289 * All constraints on the right hold.
    290 * This strategy minimizes the time to reach any city on the left. So, if any strategy works, this strategy works too.
    291 
    292 #### Corollary
    293 
    294 For a fixed starting city, if you can win, this strategy works:
    295 
    296 * [Strategy 2] If there is a city whose distance is $t$ and whose deadline is in $t$ turns, go to that direction. Otherwise, go to any direction.
    297 
    298 ### Lemma 2
    299 
    300 The valid starting cities are either zero, or all the cities in $I := \cap_{i=1}^n [i - a_i + 1, i + a_i - 1] = [l, r]$.
    301 
    302 Proof:
    303 
    304 * The cities outside $I$ are losing, because there exists at least one unreachable city.
    305 * Let's start from any city $x$ in $I$, and use Strategy 2.
    306 * You want to show that, for any $x$ in $I$, Strategy 2 can visit all cities in $I$ first, then all the other cities. Then, you can conclude that either all the cities in $I$ are winning, or they are all losing.
    307 * The interval $I$ gives bounds on the $a_i$: specifically, $a_i \geq \max(i-l+1, r-i+1)$. Then, you can verify that visiting the interval $I$ first does not violate Strategy 2.
    308 
    309 #### Corollary
    310 
    311 If you use Strategy 1, the first move on the right determines $l$.
    312 
    313 ### $\LARGE O(n^4)$ DP
    314 
    315 Let's iterate on the (non-empty) interval $I$. Let's calculate the bounds $a_i \geq \max(i-l+1, r-i+1)$. Note that Strategy 1 is deterministic (i.e., it gives exactly one visiting order for each fixed pair (starting city, $a$)). From now, you will use Strategy 1.
    316 
    317 Now you will calculate the number of pairs ($a$, visiting order) such that the cities in $I$ are valid starting cities (and there might be other valid starting cities).
    318 
    319 Let's define `dp[i][j][k] =` number of pairs ($a$, visiting order), restricted to the interval $[i, j]$, where $k =$ "are you forced to go to the right in the next move?". Here are the main ideas to find the transitions:
    320 
    321 * If you go from $[i+1, j]$ to $[i, j]$, you must ensure that $a_i \geq \max(i-l+1, r-i+1, j-i+1)$ (because you visit it at time $j-i+1$). Also, $k$ must be $0$.
    322 * If you go from $[i, j-1]$ to $[i, j]$, and you want to make $k = 0$, you must make $a_j = j-i+1$. It means that $j$ was the city that was enforcing you to go to the right.
    323 
    324 In my code, the result is stored in `int_ans[i][j]`.
    325 
    326 Now you want to calculate the number of pairs ($a$, visiting order) such that the cities in $I$ are the only valid starting cities. This is similar to 2D prefix sums, and it's enough to make `int_ans[i][j] -= int_ans[i - 1][j] + int_ans[i][j + 1] - int_ans[i - 1][j + 1]`.
    327 
    328 Since, for a fixed $a$, the visiting order only depends on the starting city, the number of $a$ for the interval $[i, j]$ is now `int_ans[i][j] / (j - i + 1)`.
    329 
    330 You have solved $k \geq 1$. The answer for $k = 0$ is just $n^n$ minus all the other answers.
    331 
    332 ### $\LARGE O(n^3)$ DP
    333 
    334 In the previous section, you are running the same DP for $O(n^2)$ different "bound arrays" on the $a_i$ (in particular, $O(n)$ arrays for each $k$). Now you want to solve a single $k$ with a single DP.
    335 
    336 For a fixed $k$, you can notice that, if you run the DP on an array of length $2n$ instead of $n$, the bound array obtained from $I = [n-k+1, n]$ contains all the bound arrays you wanted as subarrays of length $n$. So you can run the DP and get all the results as `dp[i][i + n - 1][0]`.
    337 
    338 ### $\LARGE O(n^2)$ DP
    339 
    340 You still have $O(n^3)$ distinct states in total. How to make "bound arrays" simpler?
    341 
    342 It turns out that you can handle $l$ and $r$ differently! You can create bound arrays only based on $r$ (and get $O(n^2)$ distinct states), and find $l$ using the Corollary of Lemma 2. The transitions before finding $l$ are very simple (you always go to the left). So a possible way to get $O(n^2)$ complexity is processing Strategy 1 and the DP in reverse order (from time $n$ to time $1$).
    343 
    344 Complexity: $O(n^2)$