2128.md (16672B)
1 Source: https://codeforces.com/blog/entry/145080 2 3 Thank you for participating in our round ! We hope you enjoyed our problems. Feel free to discuss them in the comment section :) 4 5 /!\ The solution codes will be available in a few minutes 6 7 UPD: The solution codes have been added ! UPD2: The solution codes links are fixed ! Sorry for the inconvenience. 8 9 [2128A - Recycling Center](/contest/2128/problem/A "Codeforces Round 1039 (Div. 2)") 10 11 **Solution** 12 13 Let's say a bag is expensive if $a_i \gt c$ and free if $a_i \leq c$. 14 15 First, observe that as long as there is at least one free bag remaining, we should destroy a free bag. We will perform all expensive destructions at the end. The goal is to perform as much free destructions as possible. 16 17 When there are multiple free bags, which one to choose? The bigger a bag is, the less time you have to destroy it before it becomes expensive. Hence, at each second, you should destroy the biggest remaining free bag. 18 19 This process can be naively simulated in $\mathcal{O}(n^2)$, which was sufficient under given constraints. If you sort the array beforehand and keep the current multiplier in a separate variable (instead of multiplying all weights), it can be done in $\mathcal{O}(n \log n)$ time. 20 21 **Code** 22 23 [331199790](/contest/2128/submission/331199790 "Submission 331199790 by bestial-42-centroids") 24 25 **Rate the problem** 26 27 Amazing 28 29 Good 30 31 Ok 32 33 Bad 34 35 Terrible 36 37 [2128B - Deque Process](/contest/2128/problem/B "Codeforces Round 1039 (Div. 2)") 38 39 **Hint1** 40 41 Instead of taking either the leftmost or rightmost element, think about taking either the minimum or maximum element. 42 43 **Hint2** 44 45 It's possible to ensure that $q_1 \lt q_2 \gt q_3 \lt q_4 \gt q_5 \ldots$ 46 47 **Solution** 48 49 Let's number turns from $1$ to $n$. On odd turns, we take the minimum element and on even turns, we take the maximum element. We claim that $q_1 \lt q_2 \gt q_3 \lt q_4 \gt q_5 \ldots$ (which is actually stronger than what the statement asked). 50 51 **Proof:** consider taking the minimum on an odd turn : $q_i = \min(p_l, p_r)$ where $l, r$ were the endpoints of the remaining array at turn $i$. Suppose without loss of generality the minimum was on the left, i.e. $q_i = p_l \lt p_r$. Then at the next turn, $p_r$ is still available: 52 53 $q_{i+1} = \max(p_{l+1}, p_r) \geq p_r \gt p_l = q_i$ 54 55 For example, if the remaining array at an odd turn is $[5, ?, \ldots, 10]$, we take the minimum $5$, and then no matter what the $?$ is, we take at least $10$ which is greater than $5$. This proves $q_i \lt q_{i+1}$ when $i$ is odd. Similarly, we can prove $q_i \gt q_{i+1}$ when $i$ is even. 56 57 **Code** 58 59 [331199677](/contest/2128/submission/331199677 "Submission 331199677 by bestial-42-centroids") 60 61 **Rate the problem** 62 63 Amazing 64 65 Good 66 67 Ok 68 69 Bad 70 71 Terrible 72 73 [2128C - Leftmost Below](/contest/2128/problem/C "Codeforces Round 1039 (Div. 2)") 74 75 **Hint** 76 77 Try to come up with a sufficient condition first, then prove it's necessary. Doing some examples with $n = 3$ might be useful. 78 79 **Solution** 80 81 Let $m_i = \min(b_1, \ldots, b_{i-1})$ for every $2 \leq i \leq n$, which can be computed in linear time. We claim we can achieve $a = b$ if and only if $b_i - m_i \lt m_i$ for every $2 \leq i \leq n$. 82 83 **Proof that it's sufficient:** we can build the array from left to right. For every $i$, if $b_i \lt m_i$ then we directly add $b_i$. Otherwise, we first add $b_i - m_i$, then $m_i$. 84 85 **Proof that it's necessary:** suppose we managed to reach $b$. At every step, $a_i \leq b_i$ for every $i$. Consider the last operation $x$ that incremented $a_i$. Then, by the definition of $i$, we must have 86 87 $a_i \lt x \leq \min(a_1, \ldots, a_{i-1}) \leq \min(b_1, \ldots, b_{i-1}).$ 88 89 Hence, $b_i = a_i + x \leq 2x-1 \leq 2m_i - 1$. 90 91 **Code** 92 93 [331199604](/contest/2128/submission/331199604 "Submission 331199604 by bestial-42-centroids") 94 95 **Rate the problem** 96 97 Amazing 98 99 Good 100 101 Ok 102 103 Bad 104 105 Terrible 106 107 [2128D - Sum of LDS](/contest/2128/problem/D "Codeforces Round 1039 (Div. 2)") 108 109 **Hint1** 110 111 Let $b_i = \max(a_i, a_{i+1})$, show that $b_1 \geq b_2 \geq \ldots \geq b_{n-1}$. 112 113 **Hint2** 114 115 If $a_i \lt a_{i+1}$, show that $a_{i+1} \gt \max(a_{i+2}, a_{i+3}, \ldots a_{n})$. 116 117 **Solution** 118 119 Let ${i_1, \ldots, i_m}$ be the set of $i \in [1, n]$ such that $a_i \gt a_{i+1}$. Let us show that the sequence $(i_1, \ldots, i_m)$ is an LDS: 120 121 * It is a decreasing subsequence: let $k \in [1, m -1]$. If $i_{k+1} = i_{k}+1$, then $a_{i_k} \gt a_{(i_k) + 1} = a_{i_{k+1}}$. Else, we have $a_{(i_k) + 2} \lt \max(a_{i_k}, a_{(i_k)+1})$, but $i_k + 1$ is such that $a_{i_{k}+2} \geq a_{i_{k+1}}$, so $a_{(i_k) + 2} \lt a_{i_k}$. We have also $a_{i_k + 1} \lt a_{i_k}$ by definition so we can easily prove by induction on $j \gt 0$ that $a_{i_k + j} \lt a_{i_k}$ where it makes sense. 122 * It's optimal : let $E$ be the set of indexes taken by a LDS. For each i such that $a_i \leq a_{i+1}$, at least one of the elements of ${i, i+1}$ does not belong to $E$. Now, these sets are disjoint : if $a_i \lt a_{i+1}$ we cannot have $a_{i+2} \lt a_{i+1}$ (otherwise the condition $\max(a_i, a_{i+1}) \gt a_{i+2}$ is not met. So $|E| \leq m$. 123 124 To calculate the sum of the LDS of the sub-arrays, it is therefore sufficient to count for each $i$ such that $a_i \lt a_{i+1}$ the number of sub-arrays $a[l,r]$ which contain $i$ and $i + 1$. It's $(i+1) \cdot (n - i - 1)$ for $0$-indexation : a necessary and sufficient condition is that $l \leq i$ and $r \geq i + 1$. 125 126 Note that there also exists a dp approach, see [this comment](https://codeforces.com/blog/entry/145080?#comment-1297950). 127 128 **Code** 129 130 [331199533](/contest/2128/submission/331199533 "Submission 331199533 by bestial-42-centroids") 131 132 **Rate the problem** 133 134 Amazing 135 136 Good 137 138 Ok 139 140 Bad 141 142 Terrible 143 144 [2128E1 - Submedians (Easy Version)](/contest/2128/problem/E1 "Codeforces Round 1039 (Div. 2)") 145 146 **Hint1** 147 148 You can use binary search on the answer. Why ? 149 150 **Hint2** 151 152 Let's start with a, perhaps, more natural task: finding whether or not $v$ is a submedian. To do so, we create an array $\text{big}$ such that $\text{big}[i] = 1 \text{ if } \text{a}[i] \geq v \text{ else } -1$ 153 154 We also create an array $\text{small}$ such that $\text{small}[i] = 1 \text{ if } \text{a}[i] \leq v \text{ else } -1$ 155 156 Knowing whether v is a submedian or not requires using both $\mathrm{big}$ and $\mathrm{small}$ ; when you want to know if the largest submedian is larger than or equal to v, do you actually need both arrays? 157 158 **Hint3** 159 160 Solve the relaxed problem where we only consider the first three constraints (and neglect the constraint on $\mathrm{small}$) i.e finding the largest $v$ such that: 161 162 * $1 \leq l \leq r \leq n$, 163 * $r - l + 1 \geq k$, 164 * $\text{big}[l] + \dots + \text{big}[r] \geq 0$ 165 166 **Hint4** 167 168 Use binary search and prefix sums to rewrite the constraint on $\text{big}$ 169 170 **Hint 5** 171 172 Is the resulting value a submedian ? 173 174 **Solution** 175 176 First, note that the predicate ``there exists a submedian $\geq v$'' is monotonic. That is, if there exists a submedian $\geq v$, then for all $v' \lt v$, there exists a submedian $\geq v$. Thus, we can binary search to find the largest $v$ such that there exists a submedian $\geq v$. Such a $v$ will be the largest submedian. 177 178 Now, what is left is to check is, for a fixed $v$, whether or not there exists a submedian $\geq v$. 179 180 Let's start with a, perhaps, more natural task: finding whether or not $v$ is a submedian. To do so, we create an array $\text{big}$ such that $\text{big}[i] = 1 \text{ if } \text{a}[i] \geq v \text{ else } -1$ 181 182 We also create an array $\text{small}$ such that $\text{small}[i] = 1 \text{ if } \text{a}[i] \leq v \text{ else } -1$ 183 184 Using these notations, $v$ is a submedian iff there exists $(l, r)$ such that: 185 186 * $1 \leq l \leq r \leq n$, 187 * $r - l + 1 \geq k$, 188 * $\text{big}[l] + \dots + \text{big}[r] \geq 0$ 189 * $\text{small}[l] + \dots + \text{small}[r] \geq 0$ 190 191 Let's try to solve a relaxed problem where we only consider the first three constraints (and neglect the constraint on $\text{small}$ i.e finding the largest $v$ such that: 192 193 * $1 \leq l \leq r \leq n$, 194 * $r - l + 1 \geq k$, 195 * $\text{big}[l] + \dots + \text{big}[r] \geq 0$ 196 197 Such a problem is standard and can be easily solved in $\mathcal{O}(n \log n)$ by binary search and prefix sums. Indeed, for a fixed $v$, we can iterate over the value of $r$. Now: $\text{big}[l] + \dots + \text{big}[r] \geq 0$ iff $\text{pref}[r] - \text{pref}[l-1] \geq 0$ i.e $\text{pref}[r] \geq \text{pref}[l-1]$ so taking $l$ that minimizes $\text{pref}[l-1]$ is optimal. Thus, it is enough to maintain such an $l$ in constant time (when you increase $r$, there is only one new candidate for $l$). 198 199 Now, I claim that the value of $v$ we get happens to be the largest submedian. Indeed, if it doesn't satisfy $\text{small}[l] + \dots + \text{small}[r] \geq 0$, then $v + 1$ would still satisfy $\text{big}[l] + \dots + \text{big}[r] \geq 0$ which contradicts the maximality of $v$. 200 201 **Code** 202 203 [331199376](/contest/2128/submission/331199376 "Submission 331199376 by bestial-42-centroids") 204 205 **Rate the problem** 206 207 Amazing 208 209 Good 210 211 Ok 212 213 Bad 214 215 Terrible 216 217 [2128E2 - Submedians (Hard Version)](/contest/2128/problem/E2 "Codeforces Round 1039 (Div. 2)") 218 219 **Hint1** 220 221 The set of submedians is a range. Try to prove it. 222 223 **Hint2** 224 225 For $l_1 \leq r_1$ and $l_2, r_2$ such that $|l_1 - l_2| + |r_1 - r_2| \leq 1$, both subarrays share at least one median. How to prove it ? Knowing this fact, how to prove Hint 1 ? 226 227 **Hint3** 228 229 Find a discretely ``continuous'' path from the subarray of the minimum submedian, to the subarray of the maximum submedian 230 231 **Solution** 232 233 Read the editorial of E1 first. 234 235 In such problems, it can be useful to try an easier version, for example, finding maximal/minimal values (which is why the subtask is helpful). 236 237 Now, one can observe that if $x \leq y$ are submedians, then any $z$ such that $x \leq z \leq y$ is also a submedian ! One can prove this using the intermediate value theorem. Let's fix $x \leq z \leq y$ and $[l_1, r_1]$ (resp. $[l_2, r_2]$) be a range where $x$ (resp. $y$) is a submedian. wlog, assume $l_1 \lt l_2$. Start by sweeping $r_1$ to $l_2$. Then $r_1$ to $r_2$. And finally, $l_1$ to $l_2$. Then one of the ranges that we covered has submedian $z$. Intuitively, when incrementing one of the ends of a range, the +1/-1 in the arrays big and small are not changing that much (the norm 1 distance is bounded by 2) so we can think of using the intermediate value theorem (see proof below). Also, note that at any time, the covered range is of length at least $k$. 238 239 Thus, it is enough to find the smallest and largest submedians (using the solution of E1) and maintain the set of submedians while sweeping. One way to do that is to use a fenwick tree to simulate an ordered set (or you can also use two range sum point update queries to simulate the \text{big} and \text{small} arrays). Alternatively, you can use two sets (one with the lower half of the values of the current range, and one with the upper half). 240 241 For each $[l, r]$ that our algorithm covers, we consider the point $(|{i \in [l,r] \mid a[i] \geq z}| - |{i \in [l,r] \mid a[i] \lt z}|, |{i \in [l,r] \mid a[i] \leq z}| - |{i \in [l,r] \mid a[i] \gt z}|)$ where $|A|$ is the cardinal of set $A$. Essentially, you can think of this point as an encoding of both conditions on small and big for $z$ to be a submedian. 242 243 Note that, when moving one end of the range, each coordinate of the point changes by at most 1 (in absolute value). Also note that, by a simple computation, the sum of both coordinates is positive (it is equal to twice the number of $i$ such that $a[i] = z$). 244 245 I claim that one of these points will have positive coordinates (thus, $z$ will be a submedian). Indeed: our path starts at a point with (negative first coordinate, positive second coordinate) and ends at a point with (positive first coordinate, negative second coordinate). Each move allows moving to a point at distance at most 2. However, you can see on the drawing below that one must pass through points with positive coordinates to achieve this (otherwise, you would be stuck in (negative first coordinate, positive second coordinate)). 246 247  248 249 In red, the area with points such that $x+y \geq 0$, below the green line are forbidden points. The blue points are our starting and ending points. Finally, the arrows are the possible moves after incrementing/decrementing one end of the range. 250 251 **Code** 252 253 Fenwick tree solution: [331199080](/contest/2128/submission/331199080 "Submission 331199080 by bestial-42-centroids") Two sets solution: [331198693](/contest/2128/submission/331198693 "Submission 331198693 by bestial-42-centroids") 254 255 **Rate the problem** 256 257 Amazing 258 259 Good 260 261 Ok 262 263 Bad 264 265 Terrible 266 267 [2128F - Strict Triangle](/contest/2128/problem/F "Codeforces Round 1039 (Div. 2)") 268 269 We shorten $\text{dist}_w$ by $d$. We denote $d_L$ as the distance when every edge has weight $l_i$, and $d_R$ as the distance when every edge has weight $r_i$. 270 271 **Hint1** 272 273 **Hint1a** 274 275 Say an edge is green if its weight is $l_i$ and red if its weight is $r_i$. If the answer is YES, prove there exists a solution that colors a path from $1$ to $n$ in green and the rest of the edges in red. 276 277 **Hint1b** 278 279 Consider an arbitrary solution $w$ and let $P$ be the shortest path from $1$ to $n$ with respect to $w$. Decreasing the weight of an edge in $P$ will decrease $d(1, n)$ by exactly one and will decrease $d(1, k) + d(k, n)$ by at most one. Increasing the weight of an edge outside $P$ will not increase $d(1, n)$ and will not decrease $d(1, k) + d(k, n)$. By repeating these operations, we can make $P$ green and the rest red. 280 281 **Hint2** 282 283 **Hint2a** 284 285 Let $P$ be the chosen green path. Find a necessary condition for the corresponding weight assignment to be correct. Then, prove if it's sufficient. 286 287 **Hint2b** 288 289 The condition is $d_L(u, v) \lt d_R(u, k) + d_R(k, v)$ for all $u, v \in P$. 290 291 **Hint2c** 292 293 It's obviously necessary; otherwise, $1 \rightarrow_L u \rightarrow_R k \rightarrow_R v \rightarrow_L n$ would have length $d(1, n)$. Conversely, if there exists a $1-n$ shortest path going through $k$, if you consider the last node in $P$ you visited before reaching $k$ and the first node in $P$ you visited after reaching $k$, this pair of nodes will violate the condition. 294 295 **Hint3** 296 297 Try to build a correct path using a Dijkstra-like algorithm. It might be helpful to have an intuitive understanding of the condition found in the previous hint in order to **quantify with a single integer how good the current path is**. Imagine you're a robber going from $1$ to $n$ and you don't want to be caught by cops. 298 299 **Hint4** 300 301 Imagine nodes are cities, $k$ is a police station, and you're some robber. Traversing the $i$-th edge takes $l_i$ seconds for the robber, and $r_i$ seconds for the citizens and the cops. 302 303 Each time you go through a city, the citizens of this city will run to the police station to warn the cops. Once the cops are warned, they start dispatching in all directions as fast as they can to catch up to you. 304 305 **Hint5** 306 307 The current danger can be represented by an integer timer $x$. If $x \lt 0$, it means the cops will be warned in $-x$ seconds. If $x \geq 0$, it means the cops have been warned since $0$ seconds. It's the only information you need to remember. 308 309 **Hint6** 310 311 Try to find for each node $u$ what is the corresponding minimum timer $t_u$. As the robber runs through the graph, the timer always increases, so you can do this with Dijkstra. 312 313 **Solution** 314 315 Please read all the hints first. 316 317 We first make a classical Dijkstra from $k$ with $r$-weighted edges. Let $d_u$ be the distance between $u$ and $k$ for citizens/cops. 318 319 We then make a modified Dijkstra, starting from the situation $(1, t_1)$ with $t_1 = -d_1$ (meaning the cops will be warned in $d_1$ seconds). 320 321 When you traverse the $i$-th edge to go from $(u, t)$ to $v$, the new timer will be 322 323 $t' = \max(t + l_i, -d_v).$ 324 325 We have $t' \geq t+l_i$ because the previous timer continued to advance while the robber was traversing the edge, and $t' \geq -d_v$ because a new citizen started running from $v$ to the police station. 326 327 Each time, we take the situation with the minimum timer from the priority queue. If the node has already been processed, or if $d_u \leq t_u$ (meaning the cops can catch up to the robber in $v$), the situation is skipped. The answer is YES if and only if we processed the node $n$. 328 329 The time complexity is $\mathcal{O}((n + m) \log (n+m))$. 330 331 **Code** 332 333 [331198575](/contest/2128/submission/331198575 "Submission 331198575 by bestial-42-centroids") 334 335 **Rate the problem** 336 337 Amazing 338 339 Good 340 341 Ok 342 343 Bad 344 345 Terrible