1733.md (8744B)
1 Source: https://codeforces.com/blog/entry/83109 2 3 Problem A is developed by [mejiamejia](/profile/mejiamejia "Expert mejiamejia"). 4 5 #### [1733A - Consecutive Sum](/contest/1733/problem/A "Codeforces Round 821 (Div. 2)") 6 7 **Hints** 8 9 **Hint 1** 10 11 $i$-th element moves only to $(i + xk)$-th position ($x$ is integer). 12 13 **Hint 2** 14 15 We cannot select $a_i$ and $a_{i + xk}$ simultaneously. In other words, if we can swap $a_i$ and $a_j$, we cannot select $a_i$ and $a_j$ simultaneously. 16 17 **Hint 3** 18 19 Among all elements $a_{i + xk}$ for each $i$ ($1 \le i \le k$), only one element is selected. 20 21 **Solution** 22 23 For each index $i$ ($k + 1 \le i \le n$), there is exactly one element among $a_1$ to $a_k$, which can swap with $a_i$. If $a_i$ is greater than that element, swap them. This process perform the operation at most $n - k$ times. After performing operations, select $a_1$ to $a_k$. This is the maximum score we can get. 24 25 **Solution Code** 26 27 [#172743256](https://codeforces.com/contest/1733/submission/172743256) 28 29 **Challenge** 30 31 After performing all operations, select $p$ consecutive elements. $p$ can be different from $k$. Find the maximum score. 32 33 #### [1733B - Rule of League](/contest/1733/problem/B "Codeforces Round 821 (Div. 2)") 34 35 **Hints** 36 37 **Hint 1** 38 39 Because one of player $1$ and player $2$ win $0$ games and the other win at least $1$ game, $\min(x, y) = 0$ and $\max(x, y) \gt 0$ must be true in order to generate a valid result. 40 41 **Hint 2** 42 43 There are one winner and one loser for every match. So the sum of winning count and the sum of losing count are same. 44 45 **Hint 3** 46 47 The sum of winning count is a multiple of $\max(x, y)$. Therefore, the sum of losing count is also a multiple of $\max(x, y)$. 48 49 **Hint 4** 50 51 (The sum of losing count) equals to $n - 1$. So $n - 1$ is a multiple of $\max(x, y)$ if there is a valid result. 52 53 **Solution** 54 55 According to hints, $\min(x, y) = 0$ and $\max(x, y) \gt 0$ and $(n - 1) \,\bmod\, \max(x, y) = 0$ holds in order to generate a valid result. If so, player $1$ and player $2$ would play first. Let's consider player $2$ wins. Then player $2$ should win $\max(x, y)$ games, and loses to player $\max(x, y) + 2$. Likewise, player $\max(x, y) + 2$ wins $\max(x, y)$ games and loses to player $2 \cdot \max(x, y) + 2$. Construct the remaining result in the same way. 56 57 **Solution Code** 58 59 [#172746518](https://codeforces.com/contest/1733/submission/172746518) 60 61 **Challenge** 62 63 Expand $x$, $y$ to $x$, $y$, $z$? 64 65 #### [1733C - Parity Shuffle Sorting](/contest/1733/problem/C "Codeforces Round 821 (Div. 2)") 66 67 **Hints** 68 69 **Hint 1** 70 71 If all elements are equal, that array is also non-decreasing. 72 73 **Hint 2** 74 75 For each operation, one element is changed. Because we have to use at most $n$ operations, an element change occurs at most $n$ times. Considering that the initial array can be decreasing, at least $n - 1$ operations can be needed in some cases. 76 77 **Solution** 78 79 If $n = 1$, do nothing. 80 81 Otherwise, select indices $1$ and $n$ to make $a_1$ equal to $a_n$ first. After that, for each element $a_i$ ($2 \le i \lt n$), select indices $1$ and $i$ if $a_1 + a_i$ is odd, and select indices $i$ and $n$ otherwise. This process requires $n - 1$ operations and make all elements equal, which is also non-decreasing. 82 83 **Solution Code** 84 85 [#172746622](https://codeforces.com/contest/1733/submission/172746622) 86 87 **Challenge** 88 89 Find the minimum number of operations? 90 91 #### [1733D1 - Zero-One (Easy Version)](/contest/1733/problem/D1 "Codeforces Round 821 (Div. 2)") 92 93 **Hints** 94 95 **Hint 1** 96 97 Consider $c$ is another binary string, in which $c_i = a_i \oplus b_i$. We have to make $c$ equal to $000 \ldots 000$ using the operation. 98 99 **Hint 2** 100 101 Because the operation does not change the parity of the number of $1$ in $c$, the answer is $-1$ if $c$ has odd number of $1$. 102 103 **Hint 3** 104 105 If the number of $1$ in $c$ is $d$ (now assume that $d$ is even), at least $\frac{d}{2}$ operations are needed. So total cost would be at least $\frac{d}{2} \times y$. 106 107 **Hint 4** 108 109 One $x$-cost operation can be replaced with two $y$-cost operations. 110 111 **Solution** 112 113 Consider another binary string $c$, in which $c_i = a_i \oplus b_i$ ($1 \le i \le n$). So doing an operation means selecting two indices of $c$ and flipping them. Also, let's define $d$ is the number of $1$ in $c$. Because the parity of $d$ never changes, the answer is $-1$ if $d$ is odd. 114 115 If $d$ is even, classify the cases: 116 117 $[1]$ If $d = 2$ and two $1$-s are adjacent, the answer is $\min(x, 2y)$. Because $n \ge 5$ holds, we can always replace one $x$-cost operation with two $y$-cost operations. 118 119 $[2]$ If $d = 2$ and two $1$-s are not adjacent, the answer is $y$. 120 121 $[3]$ If $d \ne 2$, select $i$-th $1$ and $(i + \frac{d}{2})$-th $1$ each ($1 \le i \le \frac{d}{2}$). This costs $\frac{d}{2} \times y$, and we showed the cost cannot be reduced more in hint 3. 122 123 **Solution Code** 124 125 [#172746684](https://codeforces.com/contest/1733/submission/172746684) 126 127 #### [1733D2 - Zero-One (Hard Version)](/contest/1733/problem/D2 "Codeforces Round 821 (Div. 2)") 128 129 **Hints** 130 131 **Hint 1** 132 133 Greedy solution used in D1 doesn't work in this version. 134 135 **Hint 2** 136 137 The restriction accepts normal $O(n^2)$ solution. 138 139 **Solution** 140 141 (Continued from D1 editorial) 142 143 If $x \lt y$, greedy approach used in D1 doesn't work. Let's use DP. Define $z0[i][j]$ as the minimal cost when there is $j$ $1$s in first $i$ elements of $c$ and $c_i = 0$, and $z1[i][j]$ as the minimal cost when there is $j$ $1$s in first $i$ elements of $c$ and $c_i = 1$. Initially all table values are $\infty$. 144 145 First, check $c_1$. If $c_1 = 0$, set $z0[1][0]$ to $0$. Otherwise, set $z1[1][1]$ to $0$. 146 147 Then, check the following elements from $c_2$ to $c_n$ in turn. 148 149 $[4]$ If $c_i = 0$, 150 151 $z0[i][j] = \min(z0[i - 1][j], z1[i - 1][j]), \\ z1[i][j] = \begin{cases} \min(z0[i - 1][j] + y, z1[i - 1][j] + x), & \text{if } j \le 1, \\ \\ \min(z0[i - 1][j] + y, z1[i - 1][j] + x, z0[i - 1][j - 2] + x, z1[i - 1][j - 2] + y), & \text{if } j \gt 1, \end{cases}$ 152 153 $[5]$ If $c_i = 1$, 154 155 $z0[i][j] = \begin{cases} \min(z0[i - 1][j + 1] + y, z1[i - 1][j + 1] + x), & \text{if } j = 0, \\ \min(z0[i - 1][j + 1] + y, z1[i - 1][j + 1] + x, z0[i - 1][j - 1] + x, z1[i - 1][j - 1] + y), & \text{if } 0 \lt j \lt i, \\ \min(z0[i][j], z0[i - 1][j - 1] + x, z1[i - 1][j - 1] + y), & \text{if } j = i, \end{cases} \\ z1[i][j] = \begin{cases} \infty, & \text{if } j = 0, \\ \min(z0[i - 1][j - 1], z1[i - 1][j - 1]), & \text{if } j \gt 0, \end{cases}$ 156 157 for $0 \le j \le i$. The answer is $z[n][0]$. 158 159 **Solution Code** 160 161 [#172746737](https://codeforces.com/contest/1733/submission/172746737) 162 163 **Challenge** 164 165 Solve $n \le 10^5$ version. Some testers found $O(n)$ solution. 166 167 #### [1733E - Conveyor](/contest/1733/problem/E "Codeforces Round 821 (Div. 2)") 168 169 **Hints** 170 171 **Hint 1** 172 173 Each second, slime ball moves to next diagonal. 174 175 **Hint 2** 176 177 Every slime always locates in different diagonal. 178 179 **Hint 3** 180 181 No two slime ball will merge forever. 182 183 **Hint 4** 184 185 If $t \lt x + y$, the answer should be "NO". 186 187 **Solution** 188 189 In the conveyor, cells with same $(i + j)$ value consists a diagonal ($i$ is row number, $j$ is column number). Let's call them $(i + j)$-th diagonal. So there are $239$ diagonals, from $0$-th to $238$-th. 190 191 So, we can find every slime ball move to the next diagonal for every second. It means no two slime ball merge forever. 192 193 Given $t$, $x$, $y$, cell $(x, y)$ belongs to $(x + y)$-th diagonal. If $t \lt x + y$, the answer is NO because there is no slime ball in $(x + y)$-th diagonal yet. If $t \ge x + y$, $(x + y)$-th diagonal contains one slime ball, and the ball is placed on cell $(0, 0)$ after $(t - x - y)$ seconds from the start. So $(t - x - y)$ slime balls passed this diagonal before. 194 195 Now, find out which cell contains slime ball among the diagonal. To do this, we use following method: simulate with $(t - x - y)$ slime balls to check how many slime reach each cell of the diagonal, and repeat this with $(t - x - y + 1)$ slime balls. Exactly one cell will show different result, and this cell is where $(t - x - y + 1)$-th slime ball passes through. If this cell is equal to $(x, y)$, the answer is YES. Otherwise the answer is NO. 196 197 Simulation with $x$ slime balls processes as follows: 198 199 * Place $x$ slime balls on cell $(0, 0)$. 200 * Move slime balls to next diagonal. For each cell, if the cell contains $k$ slime balls, $\lceil \frac{k}{2} \rceil$ moves to right and $\lfloor \frac{k}{2} \rfloor$ moves to down. 201 * Repeat the second step. If slime balls reached aimed diagonal, stop and find the result. 202 203 **Solution Code** 204 205 [#172746768](https://codeforces.com/contest/1733/submission/172746768) 206 207 **Challenge** 208 209 Increase the conveyor size to $10^4 \times 10^4$. Solve this version. Query number is same.