codeforces-scrape

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

2189.md (21228B)


      1 Source: https://codeforces.com/blog/entry/150452
      2 
      3 Thank you for participating in our round! We hope you enjoyed the problems. We are really sorry for the inconveniences caused by the English statement of problem B.
      4 
      5 **Fun facts**
      6 
      7 1. A total of 30 problems were proposed for this round
      8 2. E was proposed as C, and C as B
      9 
     10 [2189A - Table with Numbers](/contest/2189/problem/A "Codeforces Round 1075 (Div. 2)")
     11 
     12 Idea: [Fakewave](/profile/Fakewave "Master Fakewave")
     13 
     14 **Solution**
     15 
     16 Note that maximizing the sum of numbers in the table is equivalent to maximizing the number of chosen pairs that specify a valid cell.
     17 
     18 Without loss of generality, we assume that $h \leq l$. For any cell of the table $(x, y)$, $1 \leq x \leq h$, $1 \leq y \leq l$. Let $cnt_h$ be the number of elements in the array not exceeding $h$, and $cnt_l$ be the number of elements in the array not exceeding $l$. Then, firstly, the answer does not exceed $cnt_h$, since each pair must contain a number not exceeding $h$. Conversely, the answer does not exceed $\displaystyle \Big\lfloor \frac{cnt_l}{2} \Big\rfloor$, since both numbers in each pair must not exceed $l$. It remains to be seen that $\displaystyle min(cnt_h, \Big\lfloor \frac{cnt_l}{2} \Big\rfloor)$ pairs can be obtained. To do this, let's consider two cases.
     19 
     20 * if $\displaystyle cnt_h \leq \Big\lfloor \frac{cnt_l}{2} \Big\rfloor$, then it is sufficient to pair each number $x \leq h$ with its own number $h \lt y \leq l$, and there will be $cnt_h$ pairs. This can be done since there are at least as many suitable numbers $y$ as there are suitable $x$.
     21 * if $\displaystyle cnt_h \gt \Big\lfloor \frac{cnt_l}{2} \Big\rfloor$, then we need to pair each number $h \lt y \leq l$ with its own number $x \leq h$. After this, split the remaining numbers $x \leq h$ into pairs (there may be one extra number left over). We'll get exactly $\displaystyle \Big\lfloor \frac{cnt_l}{2} \Big\rfloor$ pairs.
     22 
     23 **Code**
     24 
     25 [359457886](/contest/2189/submission/359457886 "Submission 359457886 by Akulyat")
     26 
     27 **Rate the problem**
     28 
     29 Amazing
     30 
     31 Good
     32 
     33 Ok
     34 
     35 Bad
     36 
     37 Terrible
     38 
     39 [2189B - The Curse of the Frog](/contest/2189/problem/B "Codeforces Round 1075 (Div. 2)")
     40 
     41 Idea: [furt1ve](/profile/furt1ve "Specialist furt1ve"), [Fakewave](/profile/Fakewave "Master Fakewave")
     42 
     43 **Solution**
     44 
     45 Note that the problem is equivalent to minimizing the number of rollbacks to reach a point with a number $\geq x$. (Consider the moment when the frog first reached the point $\geq x$. Instead of a full jump, the frog could have jumped not the full distance, but exactly to the point $x$). We then assume that the frog always jumps $a_i$ units forward using the $i$-th type of jump.
     46 
     47 First, the frog can use the $i$-th type of jump $b_i-1$ times without any rollbacks. Let $r$ be the number of units remaining to the number $x$ after these jumps (if $r \leq 0$, then $0$ rollbacks are required).
     48 
     49 Now, any jump will cause a rollback. However, note that after one jump with rollback, if we used the $i$th type of jump, we can use the same jump $b_i-1$ more times without rollbacks. After that, we'll find ourselves in the same situation (any jump creates a rollback), but we have moved $a_ib_i-c_i$ units. Therefore, it's always worth using the jump with the maximum value of $a_ib_i-c_i$.
     50 
     51 Let $m = \max(a_ib_i-c_i)$ over all $i$ from $1$ to $n$. Then, if $m \leq 0$, we can't move forward (as we first get a rollback of $c_i$, and only then move by $a_ib_i$), and the answer is $-1$. Otherwise, $\displaystyle \Big\lceil \frac{r}{m} \Big\rceil$ rollbacks will be required.
     52 
     53 **Code**
     54 
     55 [359458220](/contest/2189/submission/359458220 "Submission 359458220 by Akulyat")
     56 
     57 **Rate the problem**
     58 
     59 Amazing
     60 
     61 Good
     62 
     63 Ok
     64 
     65 Bad
     66 
     67 Terrible
     68 
     69 [2189C1 - XOR Convenience (Easy Version)](/contest/2189/problem/C1 "Codeforces Round 1075 (Div. 2)")
     70 
     71 Idea: [Fakewave](/profile/Fakewave "Master Fakewave")
     72 
     73 **Solution**
     74 
     75 First, note that $p_i = p_j \oplus i$ is equivalent to $p_i \oplus i = p_j$. For $i = n-1$, the only possible $j$ is $j = n$. Let's try to construct a permutation such that for all $i$, the corresponding $j$ is $j = n$. That is, we want to ensure that for all $i \geq 2$, the condition $p_i \oplus i = p_n$ holds. Take $p_n = 1$. Then we notice that at position $2k$, the value must be $2k \oplus 1= 2k+1$, and at position $2k+1$, the value must be $(2k+1) \oplus 1 = 2k$. Thus, the numbers split into pairs $2k$ and $2k+1$.
     76 
     77 Let's examine two cases:
     78 
     79 1. If $n$ is even, take $p_1 = n$, $p_{2k} = 2k+1$, $p_{2k+1} = 2k$ ($1 \leq k \leq \frac{n}{2} - 1$);
     80 2. If $n$ is odd, take $p_1 = n-1$, $p_{2k} = 2k+1$ ($1 \leq k \leq \frac{n-1}{2}$), $p_{2k+1} = 2k$ ($1 \leq k \leq \frac{n-3}{2}$).
     81 
     82 The cases differ in the number remaining for $p_1$.
     83 
     84 For example, for $n = 9$: $[8, 3, 2, 5, 4, 7, 6, 9, 1]$, for $n = 10$: $[10, 3, 2, 5, 4, 7, 6, 9, 8, 1]$.
     85 
     86 **Code**
     87 
     88 [359458251](/contest/2189/submission/359458251 "Submission 359458251 by Akulyat")
     89 
     90 **Rate the problem**
     91 
     92 Amazing
     93 
     94 Good
     95 
     96 Ok
     97 
     98 Bad
     99 
    100 Terrible
    101 
    102 [2189C2 - XOR-convenience (Hard Version)](/contest/2189/problem/C2 "Codeforces Round 1075 (Div. 2)")
    103 
    104 **Solution**
    105 
    106 First, let's prove that no example exists when $n = 2^x$ ($x$ is an integer).
    107 
    108 Suppose $n$ is at position $i$. Assume $i \lt n$. Then $p_i \oplus i = p_j$ for some $j$. But $p_i \oplus i \ge n$, since $p_i = n = 2^x$, while $p_j \lt n$---a contradiction. Hence $i = n$. But then $p_{n-1} = p_n \oplus (n-1)$. However $p_n \oplus (n-1)$ is larger than $n$, while $p_{n-1}$ is smaller---again a contradiction.
    109 
    110 For $n \neq 2^x$, we show that an example does exist.
    111 
    112 Consider the examples from part C1. Notice that for odd $n$, the example works, because $p_1 = n-1$, and somewhere later the number $n$ occurs, and $n \oplus 1 = (n-1)$. Now consider the example for even $n$.
    113 
    114 Write $n = 2^x + r$, where $r \lt 2^x$ (in other words, $x$ is the highest bit of $n$). Then let us swap $p_1$ and $p_r$. Let's see what has changed. Since for all $i \ge 2$ earlier the only $j$ was $n$, the only number that could be broken is the one at position $r$. But now $p_r = n$. Notice that $2^x \oplus r = n$, and the number $2^x$ is at position $2^x+1$. Thus, for $i = r$, a suitable $j$ is now $j = 2^x+1 \gt r$.
    115 
    116 It remains to check that $i = 1$ has a suitable $j$. Take $j = r + 1$. Since $n$ is even, $r$ is even. Then $p_j = r$ and $p_1 = r+1$. Indeed: $r+1 = r \oplus 1$.
    117 
    118 **Code**
    119 
    120 [359458288](/contest/2189/submission/359458288 "Submission 359458288 by Akulyat")
    121 
    122 **Rate the problem**
    123 
    124 Amazing
    125 
    126 Good
    127 
    128 Ok
    129 
    130 Bad
    131 
    132 Terrible
    133 
    134 [2189D1 - Little String (Easy Version)](/contest/2189/problem/D1 "Codeforces Round 1075 (Div. 2)")
    135 
    136 Idea: [Fakewave](/profile/Fakewave "Master Fakewave"), [yanb0](/profile/yanb0 "Master yanb0")
    137 
    138 **Solution**
    139 
    140 Let's consider which permutations $p$ satisfy the condition of the string $w$. It is obvious that if $w_1 = \texttt{0}$ or $w_n = \texttt{0}$, there are no suitable $p$ (in any permutation, there is a subsegment with only the number $0$ and a subsegment with all numbers), so we will assume that $w_1 = w_n = \texttt{1}$. Let's construct $p$, starting with $p = [0]$ and sequentially inserting the numbers $1, 2, \ldots, n - 1$ into some positions.
    141 
    142 Suppose we have placed the numbers $0, 1, \ldots, k - 1$ and are now going to insert the number $k$ relative to them. We have $k + 1$ options for where to insert it.
    143 
    144 If we insert $k$ before all the numbers or after all the numbers, we can always choose all remaining numbers as a segment and get $\operatorname{mex} = k$ (note that inserting subsequent numbers will not affect the $\operatorname{mex}$ of this segment, since all subsequent values are $ \gt k$).
    145 
    146 However, if we insert $k$ between some values, we will have a situation where there is a value $ \lt k$ both to the left and to the right of $k$. Then, to achieve $\operatorname{mex} = k$, we need to collect all numbers $ \lt k$, but since they exist both to the left and to the right, we will include $k$, resulting in $\operatorname{mex} \gt k$.
    147 
    148 In total, we have $2$ options for ensuring $w_k=1$, and $k-1$ options for $w_k=0$. We have derived that
    149 
    150 $f(w) = \prod_{i = 1}^{n - 1}\begin{cases} 2 &\text{if } w_i = \texttt{1} \\ i - 1 &\text{otherwise}\end{cases}$
    151 
    152 In this version of the problem, $w = s$, so we only need to check whether $f(w)$ is divisible by $c$. To do this, we will iterate through all $i$ and reduce $c$ by the greatest common divisor of the current factor and the number $c$. If we end up with $c = 1$, then the answer is $-1$. Otherwise, the answer is $f(w)$.
    153 
    154 **Code**
    155 
    156 [359458322](/contest/2189/submission/359458322 "Submission 359458322 by Akulyat")
    157 
    158 **Rate the problem**
    159 
    160 Amazing
    161 
    162 Good
    163 
    164 Ok
    165 
    166 Bad
    167 
    168 Terrible
    169 
    170 [2189D2 - Little String (Hard Version)](/contest/2189/problem/D2 "Codeforces Round 1075 (Div. 2)")
    171 
    172 **Solution**
    173 
    174 From D1 we have:
    175 
    176 $f(w) = \prod_{i = 1}^{n - 1}\begin{cases} 2 &\text{if } w_i = \texttt{1} \\ i - 1 &\text{otherwise}\end{cases}$
    177 
    178 We will calculate the product of the multiplicative terms for all symbols $s$ that are given (\texttt{0} or \texttt{1}), and we will call this number $b$; the product of the remaining terms will be called $x$. The remaining symbols can be chosen, so we need to find the smallest value
    179 
    180 $bx = b\prod_{i \in [1, n - 1], s_i = \texttt{?}}\begin{cases} 2 \\ i - 1\end{cases}$
    181 
    182 that is not divisible by $c$. We can eliminate $b$, $x$ must not be divisible by $c' = \frac{c}{\gcd(b, c)}$. (In the implementation, to obtain $c'$, we divide $c$ by the gcd with each term of the product $b$ to avoid overflow.) If we can choose $s_2$, we will choose $s_2 = \texttt{1}$, which will make one of the terms in the product equal to $1$ — this will not cause divisibility and will not increase the number. In the end, we need to choose for several $j \ge 2$ (for $j = i - 1$, where $s_i = \texttt{?}$) to multiply $x$ either by $2$ or by $j$, so that the product is minimal and not divisible by $c'$, and the answer will be $bx$.
    183 
    184 Let's consider two cases.
    185 
    186 1. $c'$ is a power of $2$. For all even $j$, we will choose to multiply by $2$, since multiplying by $2$ instead of a positive even number will not cause divisibility and will not increase the product. We will greedily choose to multiply by $2$ for the largest of the remaining $j$ as long as possible (while $c'$ still does not divide $x$) to minimize $x$.
    187 2. $c'$ is not a power of $2$. Then, by choosing to multiply by $2$ each time, $x$ will not be divisible by $c'$, and the product will be minimal, since each time we chose the smaller of the possible factors ($2 \le j$).
    188 
    189 Final asymptotic complexity: $\mathcal{O}(n \log n)$.
    190 
    191 **Code**
    192 
    193 [359458348](/contest/2189/submission/359458348 "Submission 359458348 by Akulyat")
    194 
    195 **Rate the problem**
    196 
    197 Amazing
    198 
    199 Good
    200 
    201 Ok
    202 
    203 Bad
    204 
    205 Terrible
    206 
    207 [2189E - Majority Wins?](/contest/2189/problem/E "Codeforces Round 1075 (Div. 2)")
    208 
    209 Idea: [Fakewave](/profile/Fakewave "Master Fakewave"), [furt1ve](/profile/furt1ve "Specialist furt1ve")
    210 
    211 **Solution**
    212 
    213 Let's start by saying the answer is $-1$ if the string consists only of $0$'s.
    214 
    215 Suppose we performed $k$ operations, where the $i$-th operation cost $a_i$. Then
    216 
    217 $(a_1 - 1) + (a_2 - 1) + \dots + (a_k - 1) = n - 1$ (the number of characters that need to be removed), so
    218 
    219 $cost = a_1 + a_2 + \dots + a_k = n - 1 + k$.
    220 
    221 Thus the problem reduces to finding the minimal number of operations $k$ needed to achieve the goal. The answer will be $n - 1 + k$.
    222 
    223 We show that $k \le 4$.  
    224 Let $s_i = 1$. Replace substrings $[1, i-1]$ and $[i+1, n]$ with some characters. Now we have the string $x 1 y$. Replace the substring $[1, 2]$ with $1$, giving $1 y$. Finally replace it with the string $1$.
    225 
    226 Now we determine when the minimal number of operations is $k = 0, 1, 2, 3$ (otherwise $k = 4$).
    227 
    228 By the **difference** of a string we mean the difference between the number of $1$'s and $0$'s.
    229 
    230 It is claimed that $k$ operations are sufficient if:
    231 
    232 1. **$k = 0$** When $s = 1$.
    233 2. **$k = 1$** The string's difference is nonnegative.
    234 3. **$k = 2$** Either the string has a prefix or suffix with positive difference (then the remaining part can be replaced with any symbol, after which the whole string can be turned into $1$ in one move),  
    235     or the string's difference equals $-1$ (if the first condition does not hold, then we can replace substring $[1, n-1]$ with $1$ — its difference is $0$ because $s_n = 0$ — obtaining the string $10$, which can be changed to $1$ in one operation).
    236 4. **$k = 3$** Either the string has a prefix or suffix with nonnegative difference (then the remaining part can be replaced by $0$, that part can be turned into $1$, resulting in string $10$ or $01$, after which one operation suffices),  
    237     or there are two consecutive $1$'s (then replace the prefix before them and the suffix after them with something, obtaining a string with difference $\ge 0$, which can be turned into $1$).
    238 5. **$k = 4$** Otherwise.
    239 
    240 ---
    241 
    242 Now we proceed to the proofs for $k \ge 2$:
    243 
    244 #### **$k = 2$**
    245 
    246 Assume the goal cannot be achieved in $k \lt 2$ operations, but can in $k = 2$, under the conditions that the difference is not $-1$ and there is no prefix/suffix with positive difference.
    247 
    248 If the first operation is on a prefix or suffix, then that substring's difference is $\ge 0$. To finish in one more operation, the remaining part must have difference $-1$ (if it had difference $\ge 0$, the whole original string would have nonnegative difference; if $ \lt -1$, the total after the first operation would be $ \lt 0$). In this case the whole original string's difference would also be $-1$.
    249 
    250 If the first operation is on some middle substring, then after it the difference $\le -1 + 1 + (-1) = -1$, so winning becomes impossible.
    251 
    252 #### **$k = 3$**
    253 
    254 Assume the goal cannot be achieved in $k \lt 3$ operations, but can in $k = 3$, under the conditions that no prefix/suffix has nonnegative difference and there are no two consecutive $1$'s.
    255 
    256 Let the initial difference be $z$. Suppose the first operation is on substring $[l, r]$. Let the difference in $[1, l-1]$ be $a \lt 0$, in $[l, r]$ be $b$, and in $[r+1, n]$ be $c \lt 0$.
    257 
    258 **Case $b = 0$**  
    259  Now the difference becomes $a + 1 + c$.  
    260  If $a + c + 1 = -1$, then $a + c = -2$ with $a, c \le -1$, so $a = c = -1$. But then if substring $[l, r]$ starts and ends with $0$ (otherwise prefix $[1\ldots l]$ or suffix $[r\ldots n]$ would have nonnegative difference). Then substring $[l+1, r-1]$ has difference $2$, so its length is even (if zeros $= x$, ones $= 2 + x$, total $= 2 + 2x$). Group adjacent pairs $(l+1, l+2), \dots, (r-2, r-1)$. In each pair difference $\le 0$ (since no two consecutive $1$'s), so difference of the whole sub-substring cannot be $2$ — contradiction.
    261 
    262 Otherwise, suppose a positive prefix/suffix emerges after the operation (w.l.o.g., a prefix).  
    263  Let $T$ be that positive prefix. It contains the $1$ produced from $b$ plus some part $M$ from suffix $[r+1\ldots n]$ with difference $d \gt 0$. Then $T$'s difference is $a + 1 + d \ge 1$, so $a + d \le 0$. We already know $d \le 1$ (otherwise there would be two consecutive $1$'s), so $a \ge -1$, hence $a = -1$. Then $M$ starts with $0$ (otherwise $a + b + 1 = 0$ giving a prefix with nonnegative difference). Thus the used part $M$ must have difference $2$, so it contains two consecutive $1$'s — contradiction.
    264 
    265 **Case $b \lt 0$** If difference becomes $-1$, then $a - 1 + c = -1 \implies a + c = 0$, impossible.  
    266  Otherwise, suppose a positive prefix emerges (w.l.o.g., a prefix).
    267 
    268 * If $l = 1$, then suffix $[r+1\ldots n]$ remains. We get $0$ + a prefix from $M$, so that prefix must have difference $\ge 2 \implies$ two consecutive $1$'s — contradiction.
    269 * Otherwise, the new prefix includes $[1\ldots l-1]$ + $0$ (from $b$) + prefix $M$ from $[r+1\ldots n]$. That prefix would need difference $\ge 3$ (since $[1\ldots l-1]$ has difference $\le -1$ and we add a $0$), so again two consecutive $1$'s — contradiction.
    270 
    271 **Code**
    272 
    273 [359458367](/contest/2189/submission/359458367 "Submission 359458367 by Akulyat")
    274 
    275 **Rate the problem**
    276 
    277 Amazing
    278 
    279 Good
    280 
    281 Ok
    282 
    283 Bad
    284 
    285 Terrible
    286 
    287 [2189F - Zhora the Vacuum Cleaner](/contest/2189/problem/F "Codeforces Round 1075 (Div. 2)")
    288 
    289 Idea: [yanb0](/profile/yanb0 "Master yanb0")
    290 
    291 **Solution**
    292 
    293 We call a vertex dead if it has $0$ nuts, and if we root the tree in it, among the subtrees of its children, there is at most one subtree with a positive sum of the numbers of nuts.
    294 
    295 We denote the movement operation for a vertex $v$ as $\operatorname{c}(v)$.
    296 
    297 Let $A$ be the forest consisting of all living vertices. We prove that $A$ is always connected, i.e., it is a tree. Suppose for a contradiction, $A$ has at least two connected components, then the path between them must contain a dead vertex $v$. However, $v$ is alive, since both connected components are in different subtrees of $v$'s children when the tree's rooted in $v$, a contradiction, q.e.d.
    298 
    299 Let $\deg(v)$ be the degree of $v$ in $A$. It's easy to see that when applying $\operatorname{c}(v)$, $a_v := a_v + \deg(v)$, and for all other vertices $u \in A$, $a_u := a_u + \deg(u) - 2$. If $v \not \in A$, then $a_v := a_v + 1$, $a_u := a_u + \deg(u) - 2$, $a_p := a_p + \deg(p) - 1$, where $p$ is the closest vertex from $A$ to $v$. $[*]$
    300 
    301 For a sequence of operations, we define the tree $L$ as $A$ at the moment after all $\operatorname{c}(v)$ operations and before the nuts are eaten.
    302 
    303 Suppose we have a sequence of operations (including the eating) that results in no nuts remaining. Let us prove that the last operation $\operatorname{c}(v)$, where $v \not \in L$, can be replaced by $\operatorname{c}(u)$, where $u \in L$. In this case, $A$ becomes a non-strict subset of itself, and again, there are no nuts left. Consider the moment before applying $\operatorname{c}(v)$. There are two options:
    304 
    305 1. $v$ is alive. Then, when replacing $\operatorname{c}(v)$ with $\operatorname{c}(u)$, $a_v$ decreases by $2$, and $a_u$ increases by $2$ according to $[*]$.
    306 2. $v$ is dead. Let $p$ be the closest vertex in $A$ to $v$. Then, when replacing $\operatorname{c}(v)$ with $\operatorname{c}(u)$, $a_v$ and $a_u$ will decrease by $1$ (become equal to $0$), and $a_p$ will increase by $1$ according to $[*]$.
    307 
    308 In both cases, all $a_x$ for $x \not \in L$ will decrease, and it is easy to see that the sequence of operations after $\operatorname{c}(v)$ will also bring all nuts into $L$, after which the same eating operations will remove all nuts, q.e.d. Thus, all operations of type $\operatorname{c}(v)$, where $v \not \in L$, can be (sequentially from the end) replaced by $\operatorname{c}(u)$ for some $u \in L$.
    309 
    310 Now we have to solve the following problem:
    311 
    312 We need to choose a subtree $L$ of the original tree, then repeatedly apply $\operatorname{c}(u)$, $u \in L$, to make all vertices not in $L$ dead, and then apply the eat operation to all $v \in L$. Note that by $[*]$, all vertices not in $L$ will become dead regardless of which vertices in $L$ we choose; in other words, we can apply all $\operatorname{c}(v)$ to only one vertex $v$.
    313 
    314 Consider the dynamics along directed edges $xy$, $dp[x][y]$: the smallest number of $\operatorname{c}(v)$ operations, where $v$ is on the $x$ side of $xy$, needed to make all vertices on the $y$ side (including $y$) of $xy$ dead. The value of $a_y$ can only decrease when $\deg(y) = 1$, so $dp[x][y] = \sum_{i=0}^{k}dp[y][ch[i]]$, that is, $dp[x][y]$ is equal to the sum of $a_v$ over all $v$ in the subtree $y$, if we hang the entire tree on $x$.
    315 
    316 For all vertices $v \not \in L$, at some point and always after that, $a_v = 0$. It is also possible that $a_v = 0$ before all operations; $a_v$ is never equal to $0$ again.
    317 
    318 We define $zero[y]$ to be the smallest number of $\operatorname{c}(v)$ operations required for $a_y = 0$ after any number of $\operatorname{c}(v)$ operations at least equal to $zero[y]$. $zero[y] = \min_x({dp[x][y]})$ for all $x$ adjacent to $y$, and $zero[y] = 0$ if $a_y = 0$ and $\deg(y) = 2$ initially. This is true because if $a_y \ne 0$ or $\deg(y) \ne 2$, $y$ will finally "zero out" only when it becomes dead. $\min_x({dp[x][v]})$ is greater than $dp[v][u]$ for all, possibly except one, vertices $u$ adjacent to $v$, and therefore is greater than $\min_t({dp[t][u]})$ for $t$ adjacent to $u$ adjacent to $v$. Therefore, applying $\operatorname{c}(v)$ to $v$ with the largest $zero[v]$, each $a_u$ will become equal to $0$ after $zero[u]$ operations.
    319 
    320 Thus, either there are no $\operatorname{c}(x)$ operations, and the eating operation must be applied to all $y$ with initial $a_y = 0$, or there are $\operatorname{c}(x)$ $k$ operations, and the eating operation must be applied to all vertices $y$ with $zero[y] \ge k$. For the first case, we simply calculate the cost of this sequence of operations. For the second case, we sort $zero$ in $O(n \log n)$, then iterate over the number of "zeroed" vertices, iterating over $zero$, and calculate the answer as $(n - i) \cdot q + zero[i - 1] \cdot p$. The answer to the problem will be the minimum of the obtained ones.
    321 
    322 Total complexity: $O(n \log n)$.
    323 
    324 **Code**
    325 
    326 [359458396](/contest/2189/submission/359458396 "Submission 359458396 by Akulyat")
    327 
    328 **Rate the problem**
    329 
    330 Amazing
    331 
    332 Good
    333 
    334 Ok
    335 
    336 Bad
    337 
    338 Terrible