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).