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