codeforces-scrape

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

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 ![ ](/predownloaded/df/01/df015913e2b2e53b4cb2d1ab6649f3218d244483.png)
    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