codeforces-scrape

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

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.