1917.md (19628B)
1 Source: https://codeforces.com/blog/entry/123721 2 3 [1917A - Наименьшее произведение](/contest/1917/problem/A "Codeforces Round 917 (Div. 2)") 4 5 Author: [zidder](/profile/zidder "Гроссмейстер zidder") 6 Preparation: [_LeMur_](/profile/_LeMur_ "Мастер _LeMur_") 7 Editorial: [zidder](/profile/zidder "Гроссмейстер zidder") 8 Official solution: [238752794](/contest/1917/submission/238752794 "Посылка 238752794 от _LeMur_") 9 10 **Hint 1** 11 12 What is the minimum product that we can get, when one of the given numbers is equal to $0$. 13 14 **Hint 2** 15 16 How is the absolute value of the integer changed, when we apply the given operation on that integer? 17 18 **Hint 3** 19 20 We can always make the product as small as possible with at most $1$ operation. 21 22 **Solution** 23 24 First, let's find the minimum product we can get. If one of the numbers is or becomes $0$, then the product will be $0$. Otherwise, all the numbers don't change their sign during the operation. So the initial product won't change its sign as well. Also, we can note that the absolute value will not increase after an operation. That means if the initial product is negative, we cannot decrease it. In this case the necessary number of operations will be $0$. 25 26 If the initial product is positive, then we know the product won't become negative, therefore we will make it zero with $1$ operation, which will be the answer and the operation will be changing any number to $0$. If the initial product is zero, then we don't need to change anything, so the number of operations needed is $0$. 27 28 [1917B - Удалить первый или второй символ](/contest/1917/problem/B "Codeforces Round 917 (Div. 2)") 29 30 Author: [_LeMur_](/profile/_LeMur_ "Мастер _LeMur_") 31 Preparation: [_LeMur_](/profile/_LeMur_ "Мастер _LeMur_") 32 Editorial: [zidder](/profile/zidder "Гроссмейстер zidder") 33 Official solution: [238752759](/contest/1917/submission/238752759 "Посылка 238752759 от _LeMur_") 34 35 **Hint 1** 36 37 Do we need to use the first operation after the second operation? 38 39 **Hint 2** 40 41 Try to fix the number of the applied first operation. How many different strings can be obtained? 42 43 **Hint 3** 44 45 When can two reached strings be the same? 46 47 **Hint 4** 48 49 Try to consider the first occurrence for each letter. 50 51 **Solution** 52 53 Let's first see, that applying the second operation and then the first is equivalent to applying the first operation twice. In the former case the string will become $s_1s_2s_3 \ldots s_n \to s_1s_3 \ldots s_n \to s_3 \ldots s_n$, and in the latter case: $s_1s_2s_3 \ldots s_n \to s_2s_3 \ldots s_n \to s_3 \ldots s_n$. As we are concerned with only the number of distinct resulting strings, let's assume that the second operation is never done before the first operation. This means we do $op_1$ first operations (possibly zero) and then $op_2$ second operations (possibly zero). 54 55 Let's now find the result of applying $i$ of the first and then $j$ of the second operations. It's easy to see, that the result is $s_{i+1}s_{i+j+2}s_{i+j+3} \ldots s_n$. 56 57 The only remaining question is in which cases two sequences of operations such that the first operation always comes before the second result in the same string. Consider for the $(i_1, j_1)$ pair, the resulting string is the same as for the $(i_2, j_2)$ pair. We can see that $i_1+j_1 = i_2+j_2$, because the number of erased letters should be the same to get strings of the same length. Next, $s_{i_1+1} = s_{i_2+1}$ as those are the first letters of two resulting equal strings. It's easy to see that these conditions are also sufficient for the result to be the same string. 58 59 If after applying the first operation $op_1$ times the first letter is not its first occurrence, then any subsequent result could have been achieved by less operations of the first type by removing first character until reaching that letter and then by removing the second character until we reach $op_1$ operations in total. This means we need to consider using the second operation only at the first occurrence of the letter. 60 61 The final solution can look like this: for each letter $a \ldots z$ find it's first occurrence. If the letter is found, any number of second type operations lead to a different result. Thus we can just calculate the number of second operations that is valid and add that to the answer. 62 63 [1917C - Поливка массива](/contest/1917/problem/C "Codeforces Round 917 (Div. 2)") 64 65 Author: [IgorI](/profile/IgorI "Гроссмейстер IgorI") 66 Preparation: [IgorI](/profile/IgorI "Гроссмейстер IgorI") 67 Editorial: [IgorI](/profile/IgorI "Гроссмейстер IgorI") 68 Official solution: [238743155](/contest/1917/submission/238743155 "Посылка 238743155 от IgorI") 69 70 **Hint 1** 71 72 Assume that you are starting with array $a=[0, 0, \ldots, 0]$. 73 74 **Hint 2** 75 76 Can your score increase by more than $1$ in this case? 77 78 **Hint 3** 79 80 Note that array $a$ is non-increasing after each operation and $[1, 2, \ldots, n]$ is strictly increasing. 81 82 **Hint 4** 83 84 Try fixing the first day you make reset operation on. 85 86 **Hint 5** 87 88 Can your score increase by more than $n$ on reset operation? 89 90 **Solution** 91 92 Let's first solve this problem if we start with the array $a=[0, 0, \ldots, 0]$. This array is non-increasing and adding $1$ to any of its prefixes keeps it non-increasing. On the other hand, array $[1, 2, \ldots, n]$ is strictly increasing. This means that if $a_i=i$ and $a_j=j$ then $i=j$ (because if $i \lt j$ then $a_i \ge a_j$ and both conditions cannot hold simultaneously). Thus you cannot increase your score by more than $1$ in one reset operation. Also you cannot increase your score by $1$ in two operations in a row, because array $a$ will be equal to $[0, 0, \ldots, 0]$ before the second of this operations. Similary, you cannot increase your score on the first day. Thus, the maximum score you can get is $\lfloor \frac{d}{2} \rfloor$. On the other way, you can always achieve this score by alternating operations. 93 94 So once we fixed the first day $i$ we are making reset operation on, we can easily compute the maximum total score we will get for all the further days. Trying all $d$ possibilities of the first day $i$ we are making reset operation on is too slow. But do we need to wait for this for more than $2n$ days? Actually no because then we will get at most $n$ score for waiting for $2n+1$ days, but we can get the same (or the greater) score by doing the first reset operation on the first day. 95 96 Thus, we can solve this problem in $\mathcal{O}(n\min(n,d))$. 97 98 **Bonus 1** 99 100 Find the number of ways to achieve the maximum score. 101 102 **Bonus 2** 103 104 Solve this problem for the larger $n$. 105 106 [1917D - Очередная задача про инверсии](/contest/1917/problem/D "Codeforces Round 917 (Div. 2)") 107 108 Author: [IgorI](/profile/IgorI "Гроссмейстер IgorI") 109 Preparation: [IgorI](/profile/IgorI "Гроссмейстер IgorI") 110 Editorial: [IgorI](/profile/IgorI "Гроссмейстер IgorI") 111 Official solution: [238743552](/contest/1917/submission/238743552 "Посылка 238743552 от IgorI") 112 113 **Hint 1** 114 115 How to count the number of inversions in the permutation of length $n$ in $\mathcal{O}(n \log n)$? 116 117 **Hint 2** 118 119 Consider two arrays $x_1, x_2, \ldots, x_k$ and $\alpha x_1, \alpha x_2, \ldots, \alpha x_k$ for some positive $\alpha$. How does the number of inversions in one of them correspond to the number of inversions in the other of them? 120 121 **Hint 3** 122 123 Consider splitting array $a$ into subarrays of the length $k$. 124 125 **Hint 4** 126 127 Let's say you have two arrays $[11, 22, 44, \ldots, 11 \cdot 2^m]$ and $[13, 26, 52, \ldots, 13 \cdot 2^m]$ of the same length. How many inversions are there in their concatenation $[11, 22, 44, \ldots, 11 \cdot 2^m, 13, 26, 52, \ldots, 13 \cdot 2^m]$? 128 129 **Hint 5** 130 131 Consider the merging process of arrays $[11, 22, 44, \ldots, 11 \cdot 2^m]$ and $[13, 26, 52, \ldots, 13 \cdot 2^m]$ into the sorted array (as in the merge sort). 132 133 **Hint 6** 134 135 What if the first elements of the arrays you concatenate are not $11$ and $13$ but some odd positive integers $x$ and $y$? Merging processes for some pairs $(x, y)$ look quite similar. 136 137 **Hint 7** 138 139 The number of inversions in the array $[x, 2x, 4x, \ldots, 2^m x, y, 2y, 4y, \ldots, 2^m y]$ depends only on $\lfloor \log_2(\frac{y}{x}) \rfloor$ and $m$. You don't need to think about rounding of $\log_2(\frac{y}{x})$ because $x$ and $y$ are odd in this problem. Also, $m$ is the same for all merges. 140 141 **Hint 8** 142 143 Consider the following $\mathcal{O}(n \log n)$ algorithm to find the number of inversions in the permutation: make a segment tree corresponding to this permutation and fill it with zeroes. For all $i$ from $1$ to $n$ find $j$ such that $p_j=i$, increase the $j$-th element of this segment tree by $1$ and add the sum of elements on the right of the $j$-th element to the number of inversions. Improve this algorithm to count the number of inversions in array $a$ assuming $q=[0,1,\ldots,k-1]$. 144 145 **Hint 9** 146 147 The problem can be solved in $\mathcal{O}(n \log n \min(\log n, k) + k \log k)$. The order of elements in $q$ matters only on the inversions inside the blocks of length $k$ you chosen in the hint $2$. 148 149 **Solution** 150 151 Let's split the array $a$ into subarrays of the length $k$. The relative order of the elements in each of them is the same (as in permutation $q$), so the number of inversions is the same, too. You can find the number of invesions in one of them as described in the hint $7$. By multiplying this number by $n$, you count all the in-block inversions. 152 153 All the remaining inversions are formed by pairs of elements from the distinct blocks. You may assume that $q=[0, 1, \ldots, k-1]$ now for simplicity: it won't change the number of such inversions. 154 155 Let's fix two elements $x$ and $y$ of $p$ and count the number of inversions $(i, j)$ such that $a_i = x \cdot 2^{\alpha}$ and $a_j = y \cdot 2^{\beta}$ for some $\alpha$ and $\beta$. It is equivalent to counting the number of inversions in the array $[x, 2x, 4x, \ldots, 2^mx, y, 2y, 4y, \ldots, 2^my]$. 156 157 Consider merging two arrays $[x, 2x, 4x, \ldots, 2^mx]$ and $[y, 2y, 4y, \ldots, 2^my]$ with $x \lt y$ ($x$ and $y$ are odd) into one sorted subarray: 158 159 * if $\color{blue}{x} \lt \color{red}{y} \lt \color{blue}{2x}$, then the resulting array would look like $[\color{blue}{x}, \color{red}{y}, \color{blue}{2x}, \color{red}{2y}, \color{blue}{4x}, \color{red}{4y}, \ldots, \color{blue}{2^mx}, \color{red}{2^my}]$; 160 * if $\color{blue}{2x} \lt \color{red}{y} \lt \color{blue}{4x}$, then the resulting array would look like $[\color{blue}{x}, \color{blue}{2x}, \color{red}{y}, \color{blue}{4x}, \color{red}{2y}, \color{blue}{8x}, \color{red}{4y}, \ldots, \color{blue}{2^{m-1}x}, \color{red}{2^{m-2}y}, \color{blue}{2^mx}, \color{red}{2^{m-1}y}, \color{red}{2^my}]$; 161 * if $\color{blue}{4x} \lt \color{red}{y} \lt \color{blue}{8x}$, then the resulting array would look like $[\color{blue}{x}, \color{blue}{2x}, \color{blue}{4x}, \color{red}{y}, \color{blue}{8x}, \color{red}{2y}, \color{blue}{16x}, \color{red}{4y}, \ldots, \color{blue}{2^{m-1}x}, \color{red}{2^{m-3}y}, \color{blue}{2^mx}, \color{red}{2^{m-2}y}, \color{red}{2^{m-1}y}, \color{red}{2^my}]$; 162 * ... 163 164 You can see several blue elements in the beginning, followed by alternating blue and red elements, which are followed by several red elements. The number of blue elements in the beginning is equal to the number of red elements in the end and equal to the largest $z$ such that $2^z x \lt y$. Furthermore, this $z$ is also limited by $\log n + 1$ because $x$ and $y$ are both positive integers less than $2n$. 165 166 If $x \gt y$ the situation is similar, but the order of colors is reversed. 167 168 Going back to inversions, we have some array $[\color{blue}{x}, \color{blue}{2x}, \color{blue}{4x}, \ldots, \color{blue}{2^mx}, \color{red}{y}, \color{red}{2y}, \color{red}{4y}, \ldots, \color{red}{2^my}]$. Inversions are formed by a large blue element and a small red element. 169 170 * if $x \lt y \lt 2x$, then there are $0+1+2+\ldots+m=\frac{m(m+1)}{2}$ inversions; 171 * if $2x \lt y \lt 4x$, the there are $0+0+1+2+\ldots+(m-1)=\frac{m(m+1)}{2} - m$ inversions; 172 * if $4x \lt y \lt 8x$, the there are $0+0+0+1+2+\ldots+(m-2)=\frac{m(m+1)}{2} - m - (m-1)$ inversions; 173 * ... 174 175 For $x \gt y$ the situation is similar, but we will start with $1+2+3+\ldots+m+(m+1)=\frac{(m+1)(m+2)}{2}$ inversions for $y \lt x \lt 2y$ and we will add $m, (m-1), \ldots$ terms instead of substracting them. 176 177 Well, now we can solve this problem in $\mathcal{O}(n^2 \log n)$: enumerate pairs $(x, y)$, find $\log_2(\frac{y}{x})$ and add some value to the answer. 178 179 Now let's add the inversion counting algorithm to solve this problem. Again, let's solve the problem for $x \lt y$ first. Let's enumerate the value of $y$ from $1$ to $2n-1$. 180 181 * the $x$-s on the right of $y$ should not be counted in now; 182 * each of the $x$-s on the left of $y$ such that $x \lt y$ adds $\frac{m(m+1)}{2}$ to the answer; 183 * each of the $x$-s on the left of $y$ such that $2x \lt y$ adds $\frac{m(m+1)}{2} - m$ to the answer; 184 * each of the $x$-s on the left of $y$ such that $4x \lt y$ adds $\frac{m(m+1)}{2} - m - (m-1)$ to the answer; 185 * ... 186 187 We can maintain a segment tree to compute the sum of the values we should sum up. To update this segment tree let's additionally maintain $\Theta(\log n)$ pointers that maintain the largest $x$ such that $2^z x \lt y$ for each $z$ from $0$ to $\lceil\log n\rceil$. 188 189 The solution is similar for $x \gt y$ pairs. 190 191 You should be careful when implementing this, because for small $k$ at some moment there becomes $0$ elements in the alternating segment of the blue-red array and you shouldn't substract anything further. 192 193 **Bonus 1** 194 195 You are also given $s$ queries of the following two types: 196 197 * Swap $p_i$ and $p_j$ 198 * Swap $q_i$ and $q_j$. 199 200 Perform these queries and maintain the answer. 201 202 **Bonus 2** 203 204 You given three permutations $p$, $q$ and $r$ of lengths $l_1$, $l_2$, $l_3$ (of the first $l_1$, $l_2$ and $l_3$ positive integers correspondingly) and array $a$ is defined as $a[i \cdot l_2 \cdot l_3 + j \cdot l_3 + k] = p[i] \cdot 2^{q[j]} \cdot 2^{2^{r[k]}}$. Find the number of inversions in it. 205 206 [1917E - Постройте матрицу](/contest/1917/problem/E "Codeforces Round 917 (Div. 2)") 207 208 Author: [_LeMur_](/profile/_LeMur_ "Мастер _LeMur_") 209 Preparation: [_LeMur_](/profile/_LeMur_ "Мастер _LeMur_") 210 Editorial: [_LeMur_](/profile/_LeMur_ "Мастер _LeMur_") 211 Official solution: [238752669](/contest/1917/submission/238752669 "Посылка 238752669 от _LeMur_") 212 213 **Hint 1** 214 215 Does solution exist when $k$ is odd? 216 217 **Hint 2** 218 219 What can you understand when $k = 2$ or $k = n^2 - 2$? 220 221 **Hint 3** 222 223 How can we easily fill the matrix with $1$s, such that all problem conditions are satisfied when $k$ is divisible by $4$? 224 225 **Hint 4** 226 227 How will you solve the problem when $k = 6$? 228 229 **Hint 5** 230 231 Try to merge ideas of Hint $3$ and Hint $4$ together. 232 233 **Solution** 234 235 First, let's note that when $k$ is odd, the solution doesn't exist. It's obvious since in the solution the xors of all the rows are the same, it follows that the parity of the number of $1$s in each row is the same, and let's remember that $n$ is even, and from these conditions get that solution exists only when $k$ is even. 236 237 Second, let's note that for $k = 2$ or $k = n^2 - 2$, the solution exists only for $n = 2$. 238 239 For all other cases, a solution always exists. 240 241 * when $k \equiv 0 \pmod{4}$, we can fill $\frac{k}{4}$ submatrices of size $2 \times 2$. 242 * when $k \equiv 2 \pmod{4}$. Let's note that $k \geq 6$. Let's write $1$ in the following positions: $(1, 1)$, $(1, 2)$, $(2, 1)$, $(2, 3)$, $(3, 2)$, $(3, 3)$. After this, we should fill the remaining $(k - 6)$ ones, and let's note that $(k - 6) \equiv 0 \pmod{4}$. There are obvious $\frac{n^2 - 16}{4}$ submatrices of size $2 \times 2$, which aren't filled yet — outside the top left $4 \times 4$ submatrix. If $k \lt n^2 - 6$, then we can fill as many of those $2 \times 2$ submatrices as necessary, otherwise if $k = n^2 - 6$, we can also fill with $1$s the following $4$ positions too: $(1, 3)$, $(1, 4)$, $(4, 3)$, $(4, 4)$. 243 244 **Bonus** 245 246 Can you solve the problem for **odd** $n$? 247 248 [tourist](/profile/tourist "Легендарный гроссмейстер tourist") solved it! 249 250 [1917F - Постройте дерево](/contest/1917/problem/F "Codeforces Round 917 (Div. 2)") 251 252 Author: [_LeMur_](/profile/_LeMur_ "Мастер _LeMur_") 253 Preparation: [_LeMur_](/profile/_LeMur_ "Мастер _LeMur_") 254 Editorial: [_LeMur_](/profile/_LeMur_ "Мастер _LeMur_") 255 Official solution: [238752543](/contest/1917/submission/238752543 "Посылка 238752543 от _LeMur_") 256 257 **Hint 1** 258 259 If a solution exists, then we can always construct a tree containing a diameter and edges incident to the vertex $v$ ($v$ is from diameter). 260 261 **Hint 2** 262 263 Try to consider the maximum of the given lengths. 264 265 **Hint 3** 266 267 What can we say when there exist two lengths with a sum greater than $d$? 268 269 **Hint 4** 270 271 If a solution exists, then there should be a subset of lengths with the sum equal to $d$. 272 273 **Hint 5** 274 275 Consider cases when there exists a subset of lengths containing the maximum length with the sum equal to $d$ and doesn't. 276 277 **Hint 6** 278 279 Knapsack with bitset. 280 281 **Solution** 282 283 Let's consider the lengths in increasing order: $l_1 \leq l_2 \leq \ldots \leq l_n$. We will discuss some cases depending on the maximum length $l_n$: 284 285 * If $l_n + l_{n - 1} \gt d$, then the solution doesn't exist since an arbitrary tree will have a diameter greater than $d$. 286 * There exists the subset of the given lengths $l$, such that the sum of the lengths of that subset is equal to $d$ (for making a diameter) and $l_n$ is in that subset. In this case, the solution always exists, since we can construct a tree for example in the following way: let's consider that the size of the found subset is equal to $k$, then we can connect the vertices from $1$ to $k + 1$, such that the vertices $i$ and $i + 1$ are connected by edge for each $1 \leq i \leq k$ and $length(1, 2) = l_n$. We have some remaining lengths that we haven't used yet, so we can add edges for each length incident to the vertex $2$. Added edges will not increase the diameter, since $l_n$ is greater than or equal to all the remaining edges and $l_n + l_{n - 1} \leq d$. To check if there exists a subset of lengths such that it contains $l_n$ and the sum of elements in the subset is equal to $d$, can be easily done by the knapsack algorithm. 287 * Here, we need to find the subset of the given lengths $l$, such that the sum of the lengths of that subset is equal to $d$ (for making a diameter and we also know that $l_n$ can not be in that subset). Let's consider that diameter consisting of the vertices $v_1$, $v_2$, $\ldots$, $v_k$, such that $v_i$ and $v_{i + 1}$ are connected by edge for each $1 \leq i \leq k - 1$. Now, we need to connect an edge with length $l_n$ to the one vertex $v'$ from diameter, such that both $dist(v', v_1) + l_n \lt d$ and $dist(v', v_k) + l_n \lt d$. All the other not-used lengths we can also connect to the vertex $v'$. To check this, we should write knapsack but with two states: $dist(v', v_1)$ and $dist(v', v_k)$. 288 289 Knapsack can be done using bitset and the final complexity will be $O(\frac{n \cdot d^2}{64})$. You can also optimize this two times, since we know that the minimum of $dist(v', v_1)$ and $dist(v', v_k)$ is at most $\frac{d}{2}$.