codeforces-scrape

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

1638.md (6981B)


      1 Source: https://codeforces.com/blog/entry/99942
      2 
      3 I hope you enjoyed the problems! You can give feedback on each problem and also choose your favourite below. This could help me and other problemsetters understand what type of problems you want to see on Codeforces.
      4 
      5 [1638A - Reverse](/contest/1638/problem/A "Codeforces Round 771 (Div. 2)")
      6 
      7 **Hint 1**
      8 
      9 When is it best for the permutation to remain unchanged?
     10 
     11 **Hint 2**
     12 
     13 What elements are obviously optimal and should remain as they are?
     14 
     15 **Hint 3**
     16 
     17 Find the first non-optimal element. What's the best way to fix it?
     18 
     19 **Tutorial**
     20 
     21 Let $p_i$ be the first element such that $p_i \neq i$. For the prefix of elements $p_1=1,p_2=2, \dots ,p_{i-1}=i-1$ we do not need to change anything because it is already the minimum lexicographic, but we would like to have $i$ instead of $p_i$ on that position. The solution is to reverse segment $[i,j]$, where $p_j=i$.
     22 
     23 Notice that $i \lt j$ since $p_k=k$ for every $k \lt i$, so $p_k \lt p_j=i$ for every $k \lt i$.
     24 
     25 Time complexity: $O(n)$.
     26 
     27 **Feedback**
     28 
     29 * Didn't solve
     30 * Good problem
     31 * Average problem
     32 * Bad problem
     33 
     34 [1638B - Odd Swap Sort](/contest/1638/problem/B "Codeforces Round 771 (Div. 2)")
     35 
     36 **Hint 1**
     37 
     38 Replace the condition "$a_i+a_{i+1}$ is odd" with something easier to work with.
     39 
     40 **Hint 2**
     41 
     42 The condition means that we only swap elements of different parity. Now, make some observations.
     43 
     44 **Hint 3**
     45 
     46 What happens if there are some elements $a_i$ and $a_j$ ($i \lt j$) of the same parity, such that $a_i \gt a_j$?
     47 
     48 **Hint 4**
     49 
     50 If such pair exists, the answer is "NO". Now consider the array to be a merge between two increasing arrays (one with odd elements, one with even elements). Try to prove that the answer is always "YES" in this case.
     51 
     52 **Hint 5**
     53 
     54 What does the Bubble Sort algorithm do here? Does it ever do an illegal swap?
     55 
     56 **Tutorial**
     57 
     58 The condition "$a_i + a_{i+1}$ is odd" means that we can only swap elements of different parity. If either the order of even elements or the order of odd elements is not non-decreasing, then it is impossible to sort the sequence. Otherwise, let's prove that it is always possible to sort the sequence. We can for example perform Bubble Sort algorithm. Note that this algorithm only swaps elements $a_i$ and $a_{i+1}$ if $a_i \gt a_{i+1}$, so it will never swap two elements of the same parity (given our assumption on their order).
     59 
     60 Time complexity: $O(n)$.
     61 
     62 **Feedback**
     63 
     64 * Didn't solve
     65 * Good problem
     66 * Average problem
     67 * Bad problem
     68 
     69 [1638C - Inversion Graph](/contest/1638/problem/C "Codeforces Round 771 (Div. 2)")
     70 
     71 **Hint 1**
     72 
     73 Is there any observation you can make on the structure of the components? Ignoring values, how do they look?
     74 
     75 **Hint 2**
     76 
     77 Components form subsegments of the array. Don't prove this now. Instead, try to construct the solution by gradually increasing the prefix and storing components in a simple data structure.
     78 
     79 **Hint 3**
     80 
     81 Use a stack of pairs. For all current components, store the minimum and maximum elements inside. How do these components merge when the prefix increases?
     82 
     83 **Tutorial**
     84 
     85 Tutorial is loading...
     86 
     87 **Feedback**
     88 
     89 * Didn't solve
     90 * Good problem
     91 * Average problem
     92 * Bad problem
     93 
     94 [1638D - Big Brush](/contest/1638/problem/D "Codeforces Round 771 (Div. 2)")
     95 
     96 **Hint 1**
     97 
     98 Solve the problem in reverse.
     99 
    100 **Hint 2**
    101 
    102 What are the possible final operations?
    103 
    104 **Hint 3**
    105 
    106 They are the $2\times2$ squares painted in a single color. After finding all such squares, how can you "remove" them from the painting?
    107 
    108 **Hint 4**
    109 
    110 When removing a square, the cells below could have been painted in any color. So, mark them as special cells. After running out of squares painted in a single color, what are the new possible last operations?
    111 
    112 **Hint 5**
    113 
    114 They are all the $2\times2$ squares whose **non-special** cells are painted in the same color. How do we keep track of those while removing squares?
    115 
    116 **Hint 6**
    117 
    118 Queue.
    119 
    120 **Tutorial**
    121 
    122 Tutorial is loading...
    123 
    124 **Feedback**
    125 
    126 * Didn't solve
    127 * Good problem
    128 * Average problem
    129 * Bad problem
    130 
    131 [1638E - Colorful Operations](/contest/1638/problem/E "Codeforces Round 771 (Div. 2)")
    132 
    133 **Hint 1**
    134 
    135 First, solve the problem for single-element updates.
    136 
    137 **Hint 2**
    138 
    139 Don't actually add to all elements of some color in an update. Instead, just set a reminder that you have to do so. When do you have to be careful?
    140 
    141 **Hint 3**
    142 
    143 When you change color, remember to do the addition. Also, don't forget about the already set reminder on the new color. This is currently wrong because you are up to date. How do you fix it?
    144 
    145 **Hint 4**
    146 
    147 Moving to the range update problem, use a data structure to maintain maximal ranges colored in a single color. How do these color intervals change during a color operation? What's the actual time complexity?
    148 
    149 **Tutorial**
    150 
    151 Tutorial is loading...
    152 
    153 **Feedback**
    154 
    155 * Didn't solve
    156 * Good problem
    157 * Average problem
    158 * Bad problem
    159 
    160 [1638F - Two Posters](/contest/1638/problem/F "Codeforces Round 771 (Div. 2)")
    161 
    162 **Hint 1**
    163 
    164 Consider the ranges of panels covered by the two posters. Split the problem into multiple cases according to how these intervals are positioned relative to eachother. Throughout the solution, consider the concept of "bottlenecks". These are panels that stop the area to be any larger.
    165 
    166 **Hint 2**
    167 
    168 First case: the ranges are disjoint. How do you solve this?
    169 
    170 **Hint 3**
    171 
    172 Now, for the other cases, make some observations when the posters share some common range of pannels. Consider the heights to be fixed and group panels into two different types.
    173 
    174 **Hint 4**
    175 
    176 There are panels that could fit both (let them be grey) and panels that could fit only one (let them be yellow). The shared range of pannels is between two consecutive yellow panels. Moreover, it is bounded by yellow panels in an optimal solution.
    177 
    178 **Hint 5**
    179 
    180 Now, consider the heights of the two posters to not be fixed anymore. How many possible maximal ranges of shared panels can there be? They seem to be $O(n^2)$, but maybe there are less.
    181 
    182 **Hint 6**
    183 
    184 Let the shortest panel inside a maximal shared range to be its "representative panel". Starting from such a panel, what ranges does it represent?
    185 
    186 **Hint 7**
    187 
    188 It can be proven that the only possible range is the one between the closest shorter panels to the left and right. Now you are able to consider all possible shared ranges because there are $O(n)$. You can split further into two cases and solve them using two-pointers and possibly some precomputations.
    189 
    190 **Tutorial**
    191 
    192 Tutorial is loading...
    193 
    194 **Feedback**
    195 
    196 * Didn't solve
    197 * Good problem
    198 * Average problem
    199 * Bad problem
    200 
    201 Now you can choose your favourite problem from the ones you solved during the contest or upsolved after it.
    202 
    203 * Problem A
    204 * Problem B
    205 * Problem C
    206 * Problem D
    207 * Problem E
    208 * Problem F
    209 
    210 **UPD:** Don't forget to check out [competitive__programmer](/profile/competitive__programmer "Specialist competitive__programmer")'s video tutorials on [his channel](https://www.youtube.com/channel/UCnZ5rC2_JY0EuYMGMiAbISg).