codeforces-scrape

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

1485.md (10204B)


      1 Source: https://codeforces.com/blog/entry/87470
      2 
      3 [1485A - Add and Divide](/contest/1485/problem/A "Codeforces Round 701 (Div. 2)")
      4 
      5 Author: [TheScrasse](/profile/TheScrasse "Master TheScrasse")  
      6  Preparation: [MyK_00L](/profile/MyK_00L "Master MyK_00L")
      7 
      8 **Hint 1**
      9 
     10 Suppose that you can use $x$ operations of type $1$ and $y$ operations of type $2$. Try to reorder the operations in such a way that $a$ becomes the minimum possible.
     11 
     12 **Hint 2**
     13 
     14 You should use operations of type $2$ first, then moves of type $1$. How many operations do you need in the worst case? ($a = 10^9$, $b = 1$)
     15 
     16 **Hint 3**
     17 
     18 You need at most $30$ operations. Iterate over the number of operations of type $2$.
     19 
     20 **Solution**
     21 
     22 Notice how it is never better to increase $b$ after dividing ($\lfloor \frac{a}{b+1} \rfloor \le \lfloor \frac{a}{b} \rfloor$).
     23 
     24 So we can try to increase $b$ to a certain value and then divide $a$ by $b$ until it is $0$. Being careful as not to do this with $b \lt 2$, the number of times we divide is going to be $O(\log a)$. In particular, if you reach $b \geq 2$ (this requires at most $1$ move), you need at most $\lfloor \log_2(10^9) \rfloor = 29$ moves to finish.
     25 
     26 Let $y$ be the number of moves of type $2$; we can try all values of $y$ ($0 \leq y \leq 30$) and, for each $y$, check how many moves of type $1$ are necessary.
     27 
     28 Complexity: $O(\log^2 a)$.
     29 
     30 If we notice that it is never convenient to increase $b$ over $6$, we can also achieve a solution with better complexity.
     31 
     32 Official solution: [107232596](/contest/1485/submission/107232596 "Submission 107232596 by TheScrasse")
     33 
     34 [1485B - Replace and Keep Sorted](/contest/1485/problem/B "Codeforces Round 701 (Div. 2)")
     35 
     36 Author: [TheScrasse](/profile/TheScrasse "Master TheScrasse")  
     37  Preparation: [Kaey](/profile/Kaey "Master Kaey")
     38 
     39 **Hint 1**
     40 
     41 You can make a $k$-similar array by assigning $a_i = x$ for some $l \leq i \leq r$ and $1 \leq x \leq k$.
     42 
     43 **Hint 2**
     44 
     45 How many $k$-similar arrays can you make if $x$ is already equal to some $a_i$ ($l \leq i \leq r$)?
     46 
     47 **Hint 3**
     48 
     49 How many $k$-similar arrays can you make if either $x \lt a_l$ or $x \gt a_r$?
     50 
     51 **Hint 4**
     52 
     53 How many $k$-similar arrays can you make if none of the previous conditions holds?
     54 
     55 **Solution**
     56 
     57 Let's consider each value $x$ from $1$ to $k$.
     58 
     59 * If $x \lt a_l$, you can replace $a_l$ with $x$ (and you get $1$ $k$-similar array). There are $a_l-1$ such values of $x$.
     60 * If $x \gt a_r$, you can replace $a_r$ with $x$ (and you get $1$ $k$-similar array). There are $k-a_r$ such values of $x$.
     61 * If $a_l \lt x \lt a_r$, and $x \neq a_i$ for all $i$ in $[l, r]$, you can either replace the rightmost $b_i$ which is less than $x$, or the leftmost $b_i$ which is greater than $x$ (and you get $2$ $k$-similar arrays). There are $(a_r - a_l + 1) - (r - l + 1)$ such values of $x$.
     62 * If $x = a_i$ for some $i$ in $[l, r]$, no $k$-similar arrays can be made.
     63 
     64 The total count is $(a_l-1)+(k-a_r)+2((a_r - a_l + 1) - (r - l + 1))$, which simplifies to $k + (a_r - a_l + 1) - 2(r - l + 1)$.
     65 
     66 Complexity: $O(n + q)$.
     67 
     68 Official solution: [107232462](/contest/1485/submission/107232462 "Submission 107232462 by TheScrasse")
     69 
     70 [1485C - Floor and Mod](/contest/1485/problem/C "Codeforces Round 701 (Div. 2)")
     71 
     72 Authors: [isaf27](/profile/isaf27 "International Grandmaster isaf27"), [TheScrasse](/profile/TheScrasse "Master TheScrasse")  
     73  Preparation: [Kaey](/profile/Kaey "Master Kaey")
     74 
     75 **Hint 1**
     76 
     77 Let $\lfloor \frac{a}{b} \rfloor = a~\mathrm{mod}~b = k$. Is there an upper bound for $k$?
     78 
     79 **Hint 2**
     80 
     81 $k \leq \sqrt x$. For a fixed $k$, can you count the number of special pairs such that $a \leq x$ and $b \leq y$ in $O(1)$?
     82 
     83 **Solution**
     84 
     85 We can notice that, if $\lfloor \frac{a}{b} \rfloor = a~\mathrm{mod}~b = k$, then $a$ can be written as $kb+k$ ($b \gt k$). Since $b \gt k$, we have that $k^2 \lt kb+k = a \leq x$. Hence $k \leq \sqrt x$.
     86 
     87 Now let's count special pairs for any fixed $k$ ($1 \leq k \leq \sqrt x$). For each $k$, you have to count the number of $b$ such that $b \gt k$, $1 \leq b \leq y$, $1 \leq kb+k \leq x$. The second condition is equivalent to $1 \leq b \leq x/k-1$.
     88 
     89 Therefore, for any fixed $k \gt 0$, the number of special pairs ($a\leq x$; $b \leq y$) is $max(0, min(y,x/k-1) - k)$. The result is the sum of the number of special pairs for each $k$.
     90 
     91 Complexity: $O(\sqrt x)$.
     92 
     93 Official solution: [107232416](/contest/1485/submission/107232416 "Submission 107232416 by TheScrasse")
     94 
     95 [1485D - Multiples and Power Differences](/contest/1485/problem/D "Codeforces Round 701 (Div. 2)")
     96 
     97 Author: [TheScrasse](/profile/TheScrasse "Master TheScrasse")  
     98  Preparation: [MyK_00L](/profile/MyK_00L "Master MyK_00L")
     99 
    100 **Hint 1**
    101 
    102 Brute force doesn't work (even if you optimize it): there are relatively few solutions.
    103 
    104 **Hint 2**
    105 
    106 There may be very few possible values of $b_{i,j}$, if $b_{i-1,j}$ is fixed. The problem arises when you have to find a value for a cell with, e.g., $4$ fixed neighbors. Try to find a possible property of the neighbors of $(i, j)$, such that at least a solution for $b_{i,j}$ exists.
    107 
    108 **Hint 3**
    109 
    110 The least common multiple of all integers from $1$ to $16$ is less than $10^6$.
    111 
    112 **Solution**
    113 
    114 Build a matrix with a checkerboard pattern: let $b_{i, j} = 720720$ if $i + j$ is even, and $720720+a_{i, j}^4$ otherwise. The difference between two adjacent cells is obviously a fourth power of an integer. We choose $720720$ because it is $\operatorname{lcm}(1, 2, \dots, 16)$. This ensures that $b_{i, j}$ is a multiple of $a_{i, j}$, because it is either $720720$ itself or the sum of two multiples of $a_{i, j}$.
    115 
    116 Complexity: $O(nm)$.
    117 
    118 Official solution: [107232359](/contest/1485/submission/107232359 "Submission 107232359 by TheScrasse")
    119 
    120 [1485E - Move and Swap](/contest/1485/problem/E "Codeforces Round 701 (Div. 2)")
    121 
    122 Author: [TheScrasse](/profile/TheScrasse "Master TheScrasse")  
    123  Preparation: [TheScrasse](/profile/TheScrasse "Master TheScrasse")
    124 
    125 **Hint 1**
    126 
    127 What happens if you can't swap coins?
    128 
    129 **Hint 2**
    130 
    131 Let $dp_i$ be the maximum score that you can reach after $dist(1, i)$ moves if there is a red coin on node $i$ after step $3$. However, after step $2$, the coin on node $i$ may be either red or blue. Try to find transitions for both cases.
    132 
    133 **Hint 3**
    134 
    135 If you consider only the first case, you solve the problem if there are no swaps. You can greedily check the optimal location for the blue coin: a node $j$ such that $dist(1,i) = dist(1,j)$ and $a_j$ is either minimum or maximum.
    136 
    137 Instead, if the coin on node $i$ is blue after step $2$, the red coin is on node $j$ and you have to calculate $\max(dp_{parent_j} + |a_j - a_i|)$ for each $i$ with a fixed $dist(1, i)$. How?
    138 
    139 **Solution**
    140 
    141 Divide the nodes in groups based on the distance from the root. Then, for each $dist(1, i)$ in increasing order, calculate $dp_i$ — the maximum score that you can reach after $dist(1, i)$ moves if there is a red coin on node $i$ after step $3$. You can calculate $dp_i$ if you know $dp_j$ for each $j$ that belongs to the previous group. There are two cases:
    142 
    143 * if after step $2$ the coin on node $i$ is red, the previous position of the red coin is fixed, and the blue coin should reach either the minimum or the maximum $a_j$ among the $j$ that belong to the same group of $i$;
    144 * if after step $2$ the coin on node $i$ is blue, there is a red coin on node $j$ ($dist(1, i) = dist(1, j)$), so you have to maximize the score $dp_{parent_j} + |a_j - a_i|$.  
    145    This can be done efficiently by sorting the $a_i$ in the current group and calculating the answer separately for $a_j \leq a_i$ and $a_j \gt a_i$; for each $i$ in the group, the optimal node $j$ either doesn't change or it's the previous node.  
    146    Alternatively, you can notice that $dp_{parent_j} + |a_j - a_i| = \max(dp_{parent_j} + a_j - a_i, dp_{parent_j} + a_i - a_j)$, and you can maximize both $dp_{parent_j} + a_j - a_i$ and $dp_{parent_j} + a_i - a_j$ greedily (by choosing the maximum $dp_{parent_j} + a_j$ and $dp_{parent_j} - a_j$, respectively). In this solution, you don't need to sort the $a_i$.
    147 
    148 The answer is $\max(dp_i)$.
    149 
    150 Complexity: $O(n)$ or $O(n\log n)$.
    151 
    152 Official solution: [107232216](/contest/1485/submission/107232216 "Submission 107232216 by TheScrasse")
    153 
    154 [1485F - Copy or Prefix Sum](/contest/1485/problem/F "Codeforces Round 701 (Div. 2)")
    155 
    156 Author: [TheScrasse](/profile/TheScrasse "Master TheScrasse")  
    157  Preparation: [TheScrasse](/profile/TheScrasse "Master TheScrasse")
    158 
    159 **Hint 1**
    160 
    161 Why isn't the answer $2^{n-1}$? What would you overcount?
    162 
    163 **Hint 2**
    164 
    165 Find a dp with time complexity $O(n^2\log n)$.
    166 
    167 **Hint 3**
    168 
    169 Let $dp_{i, j}$ be the number of hybrid prefixes of length $i$ and sum $j$. The transitions are $dp_{i, j} \rightarrow dp_{i+1, j+b_i}$ and $dp_{i,j} \rightarrow dp_{i+1,b_i}$. Can you optimize it to $O(n\log n)$?
    170 
    171 **Solution**
    172 
    173 For each $i$, you can choose either $a_i = b_i$ or $a_i = b_i - \sum_{k=1}^{i-1} a_k$. If $\sum_{k=1}^{i-1} a_k = 0$, the two options coincide and you have to avoid overcounting them.
    174 
    175 This leads to an $O(n^2\log n)$ solution: let $dp_i$ be a map such that $dp_{i, j}$ corresponds to the number of ways to create a hybrid prefix $[1, i]$ with sum $j$. The transitions are $dp_{i, j} \rightarrow dp_{i+1, j+b_i}$ (if you choose $b_i = a_i$, and $j \neq 0$), $dp_{i,j} \rightarrow dp_{i+1,b_i}$ (if you choose $b_i = \sum_{k=1}^{i} a_k$).
    176 
    177 Let's try to get rid of the first layer of the dp. It turns out that the operations required are
    178 
    179 * move all $dp_j$ to $dp_{j+b_i}$
    180 * calculate the sum of all $dp_j$ in some moment
    181 * change the value of a $dp_j$
    182 
    183 and they can be handled in $O(n\log n)$ with ["Venice technique"](https://codeforces.com/blog/entry/58316).
    184 
    185 $dp$ is now a map such that $dp_j$ corresponds to the number of ways to create a hybrid prefix $[1, i]$ such that $\sum_{k=1}^{i} a_k - b_k = j$. Calculate the dp for all prefixes from left to right. if $b_i = a_i$, you don't need to change any value of the dp; if $b_i = \sum_{k=1}^{i} a_k$, you have to set $dp_{\sum_{k=1}^{i} -b_k}$ to the total number of hybrid arrays of length $i-1$.
    186 
    187 Complexity: $O(n\log n)$.
    188 
    189 Official solution: [107232144](/contest/1485/submission/107232144 "Submission 107232144 by TheScrasse")