codeforces-scrape

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

1509.md (14030B)


      1 Source: https://codeforces.com/blog/entry/89644
      2 
      3 Note: I can't figure out how to place the tutorials inside spoilers. If someone is familiar with how CF spoilers work and can help I would really appreciate it. For now, be warned that the tutorials are visible by default (but everything else isn't)
      4 
      5 **UPD:** I figured out how to use spoilers! Also added implementations for all problems.
      6 
      7 Thanks for participating in our contest!
      8 
      9 [1509A - Average Height](/contest/1509/problem/A "Codeforces Round 715 (Div. 2)")
     10 
     11 Author: [Kuroni](/profile/Kuroni "International Grandmaster Kuroni")   
     12  First solve: [Nutella3001](/profile/Nutella3001 "Expert Nutella3001") at 00:01:02
     13 
     14 **Hint**
     15 
     16 How can you write the condition that $\frac{a_u + a_v}{2}$ is an integer in a more useful way? Think of the parities.
     17 
     18 **Tutorial**
     19 
     20 Tutorial is loading...
     21 
     22 **Comments from the authors**
     23 
     24 ![ ](/predownloaded/75/33/7533b7a16e77743958066419a33487b3e38691e0.png)
     25 
     26 [Implementation](https://codeforces.com/contest/1509/submission/113263196)
     27 
     28 [1509B - TMT Document](/contest/1509/problem/B "Codeforces Round 715 (Div. 2)")
     29 
     30 Author: [Ari](/profile/Ari "Grandmaster Ari")   
     31  First solve: [blue](/profile/blue "Unrated, blue") at 00:04:51
     32 
     33 **Hint**
     34 
     35 You can think of the partition as associating to each $M$ character a $T$ to its left and a $T$ to its right. What's the best way to perform this assignment?
     36 
     37 **Answer**
     38 
     39 Assign greedily from left to right.
     40 
     41 **Tutorial**
     42 
     43 Tutorial is loading...
     44 
     45 **Comments from the authors**
     46 
     47 Do yourself a favor and listen to Towa-sama's singing! [Here](https://www.youtube.com/watch?v=3UV8OZj2olg) [are](https://www.youtube.com/watch?v=2D0B3wTjE20) [some](https://www.youtube.com/watch?v=ZQ3gmQzpvBM) [links](https://www.youtube.com/watch?v=2o_H09MdT94) [to](https://www.youtube.com/watch?v=64kI2BWRd2g) [cool](https://www.youtube.com/watch?v=9RBY7u5qas8) [songs.](https://www.youtube.com/watch?v=Ud73fm4Uoq0)
     48 
     49 [Implementation](https://codeforces.com/contest/1509/submission/113263820)
     50 
     51 [1509C - The Sports Festival](/contest/1509/problem/C "Codeforces Round 715 (Div. 2)")
     52 
     53 Author: [Ari](/profile/Ari "Grandmaster Ari")   
     54  First solve: [Dukkha](/profile/Dukkha "Specialist Dukkha") at 00:05:32
     55 
     56 **Hint 1**
     57 
     58 What is the discrepancy of the last stage? How can we make it smaller in previous stages?
     59 
     60 **Answer**
     61 
     62 The discrepancy of the last stage is always the difference between the largest and the smallest $a_i$. We can make it smaller in the previous stages by placing the smallest or the largest $a_i$ at the end.
     63 
     64 **Hint 2**
     65 
     66 Use dynamic programming.
     67 
     68 **Tutorial**
     69 
     70 Tutorial is loading...
     71 
     72 **Comments from the authors**
     73 
     74 This problem was originally going to appear in [Codeforces Round 668 (Div. 2)](/contest/1405 "Codeforces Round 668 (Div. 2)"), but it was removed one day before the contest for balance reasons :P
     75 
     76 [Implementation](https://codeforces.com/contest/1509/submission/113263837)
     77 
     78 [1508A - Binary Literature](/contest/1508/problem/A "Codeforces Round 715 (Div. 1)")
     79 
     80 Author: [Ari](/profile/Ari "Grandmaster Ari")   
     81  First solve (Div. 2): [traxex2](/profile/traxex2 "Unrated, traxex2") at 00:22:48   
     82  First solve (Div. 1): [tourist](/profile/tourist "Legendary Grandmaster tourist") at 00:05:04
     83 
     84 **Hint 1**
     85 
     86 Consider two of the strings. We can obviously achieve our goal using at most $4n$ characters. How can we save some of them?
     87 
     88 **Answer**
     89 
     90 Take advantage of any common subsequence in our two strings by including the characters in it only once.
     91 
     92 **Hint 2**
     93 
     94 Find a long common subsequence that has a simple structure. You'll need to involve the third string as well.
     95 
     96 **Hint 3**
     97 
     98 Either $00\dots 0$ or $11\dots 1$ is a subsequence of each string.
     99 
    100 **Tutorial**
    101 
    102 Tutorial is loading...
    103 
    104 **Comments from the authors**
    105 
    106 This problem was originally suggested as a 2B. It turned out to be too hard and was switched to 2C, before being further switched to 1A because it was still too hard. Some testers still believed this problem to be even harder, but we ended up deciding to have it as 1A with a larger score than usual.   
    107    
    108  Apologies to the testers who had to solve this as if it was the second easiest problem in the contest :^)
    109 
    110 [Implementation](https://codeforces.com/contest/1508/submission/113263847)
    111 
    112 [1508B - Almost Sorted](/contest/1508/problem/B "Codeforces Round 715 (Div. 1)")
    113 
    114 Author: Both of us!   
    115  First solve (Div. 2): [shenmadongdong.qaq](/profile/shenmadongdong.qaq "Newbie shenmadongdong.qaq") at 00:29:52   
    116  First solve (Div. 1): [tourist](/profile/tourist "Legendary Grandmaster tourist") at 00:08:19
    117 
    118 **Hint 1**
    119 
    120 What is the general structure of an almost sorted permutation?
    121 
    122 **Answer**
    123 
    124 Start with the identity permutation, choose some disjoint subarrays, and reverse each of them.
    125 
    126 **Hint 2**
    127 
    128 How many almost sorted permutations of length $n$ exist? In other words, how many ways are there to reverse subarrays?
    129 
    130 **Answer**
    131 
    132 $2^{n - 1}$
    133 
    134 **Hint 3**
    135 
    136 Two options — either solve recursively in a greedy fashion or find a smart bijection.
    137 
    138 **Tutorial**
    139 
    140 Tutorial is loading...
    141 
    142 **Comments from the authors**
    143 
    144 This problem's creation has a funny story. Back when we were coming up with problems for Round 668, I (Ari) came up the following relatively simple and standard problem and shared it.   
    145    
    146  ![ ](/predownloaded/11/41/114138713eb3ec9a20ecc7373b9e704ff08ee5a6.png)   
    147    
    148  The next day, Kuroni saw the problem, but misread it and ended up solving the version that made it into this contest, which we think is a lot cooler!   
    149    
    150  One more fun fact for your consideration: This problem's name in Polygon is "sorrow".
    151 
    152 [Implementation](https://codeforces.com/contest/1508/submission/113263859)
    153 
    154 [1508C - Complete the MST](/contest/1508/problem/C "Codeforces Round 715 (Div. 1)")
    155 
    156 Author: [Kuroni](/profile/Kuroni "International Grandmaster Kuroni")   
    157  First solve (Div. 2): [deepspacewaifu](/profile/deepspacewaifu "Newbie deepspacewaifu") at 01:42:36   
    158  First solve (Div. 1): [maroonrk](/profile/maroonrk "Legendary Grandmaster maroonrk") at 00:33:17
    159 
    160 **Hint 1**
    161 
    162 How can we solve this problem without the restriction that the xor of all edge weights is $0$?
    163 
    164 **Answer**
    165 
    166 Just assign $0$ to every unassigned edge :P
    167 
    168 **Hint 2**
    169 
    170 When does the solution to the unrestricted problem fail for the real problem?
    171 
    172 **Answer**
    173 
    174 When any minimum spanning tree (of the graph with every unassigned edge having weight $0$) contains every unassigned edge, and the xor sum of all the edge weights is not $0$.
    175 
    176 **Hint 3**
    177 
    178 Leave the xor sum of the weights of the unassigned edges in the spanning tree fixed. How do we minimize their sum?
    179 
    180 **Answer**
    181 
    182 Assign the entire xor sum to a single edge, and assign weight $0$ to every other edge.
    183 
    184 **Hint 4**
    185 
    186 Exactly one unassigned edge ends up with a non-zero weight. If we don't use all unassigned edges, which others can we use?
    187 
    188 **Answer**
    189 
    190 Any edge that isn't part of the MST when we consider unassigned edges to have weight $0$, and that doesn't form a cycle with pre-assigned edges with smaller weights.
    191 
    192 **Tutorial**
    193 
    194 Tutorial is loading...
    195 
    196 **Comments from the authors**
    197 
    198 If the unassigned edges in the graph don't form a forest, then the answer is simply the weight of the MST where all the unassigned edges have weight $0$. Thus the interesting tests in this problem require these edges to form a forest, which means $m \ge \frac{n(n - 1)}{2} - (n - 1)$. This automatically limits the maximum value of $n$ to approximately $2\sqrt{m}$. Concretely, $n \le 633$ for all interesting tests in this problem. You can also use this to obtain a solution that runs in $O(m \sqrt{m})$, which a tester found, and which passes if implemented reasonably.
    199 
    200 [Implementation](https://codeforces.com/contest/1508/submission/113263168)
    201 
    202 [1508D - Swap Pass](/contest/1508/problem/D "Codeforces Round 715 (Div. 1)")
    203 
    204 Author: [Ari](/profile/Ari "Grandmaster Ari")   
    205  First solve: [ksun48](/profile/ksun48 "Legendary Grandmaster ksun48") at 00:57:13
    206 
    207 **Hint 1**
    208 
    209 It is always possible to find the sequence.
    210 
    211 **Hint 2**
    212 
    213 There's a simple algorithm that fixes a point and repeatedly moves its current label to the correct position. When does it work?
    214 
    215 **Answer**
    216 
    217 When the permutation of the labels is a single cycle.
    218 
    219 **Hint 3**
    220 
    221 Any permutation can be split into one or more cycles. What can we do to these cycles?
    222 
    223 **Answer**
    224 
    225 Merge them, by swapping two elements in different cycles.
    226 
    227 **Hint 4**
    228 
    229 We would like to merge all cycles of the permutation by swapping elements in different cycles and then repeatedly move each label from a certain point to its correct location. How can we do this without intersections?
    230 
    231 **Answer**
    232 
    233 Fix a point beforehand to perform the final step, and sort angularly with respect to this point.
    234 
    235 **Tutorial**
    236 
    237 Tutorial is loading...
    238 
    239 **Comments from the authors**
    240 
    241 This problem was originally proposed with the points always being the vertices of a convex polygon. This allows us to do a slightly different solution where we first merge the cycles and choose the pivot afterwards by choosing a point unaffected by the previous swaps.   
    242    
    243  The reason for having $n = 2000$ in this problem rather than a larger $n$ like $10^5$ is because of the validator: it is essential to not have three collinear points in this problem, and I don't know how to check this for large $n$. The small $n$ also makes the checker much easier to write, though it's possible (albeit tricky) to write a checker that works in $O(n \log n)$.   
    244    
    245  Regarding the number of operations used: The solution described in the editorial uses approximately $\frac{3}{2}n$ operations in the worst case when the permutation consists of cycles of size $2$. The minimum number of operations is lower bounded by $n - 1$ by combinatorics reasons when the permutation is a single cycle. Moreover, by Euler's formula, we have an upper bound of $3n - 6$ operations for any valid sequence, which goes down to $2n - 3$ when the points are the vertices of a convex polygon. I don't know of a solution that uses $cn$ operations for some $c \lt 3/2$, nor do I know of a general test case where it can be proven that at least $cn$ operations are needed for some $c \gt 1$, so I'd be really interested in seeing either.
    246 
    247 [Implementation](https://codeforces.com/contest/1508/submission/113263865)
    248 
    249 [1508E - Tree Calendar](/contest/1508/problem/E "Codeforces Round 715 (Div. 1)")
    250 
    251 Author: [Kuroni](/profile/Kuroni "International Grandmaster Kuroni")   
    252  First solve: [ecnerwala](/profile/ecnerwala "Legendary Grandmaster ecnerwala") at 01:02:26
    253 
    254 **Hint 1**
    255 
    256 During the process, we will repeatedly push the same label down until we no longer can. What happens at this point?
    257 
    258 **Answer**
    259 
    260 The labels that have been fully pushed down will look like a post-order of the tree, while the other labels will look like a pre-order of the tree.
    261 
    262 **Hint 2**
    263 
    264 Look at the children of a particular vertex. What can we say about the ones that are fully pushed down in relation to the ones that aren't?
    265 
    266 **Answer**
    267 
    268 Every fully pushed down label is smaller than every other label.
    269 
    270 **Hint 3**
    271 
    272 For each node, the order of the labels of its children stays fixed.
    273 
    274 **Hint 4**
    275 
    276 How can we use the previous observations to identify the state of the process?
    277 
    278 **Answer**
    279 
    280 We can reconstruct the DFS order and the fully pushed down labels. Then check that the current pushing step of the process is valid.
    281 
    282 **Tutorial**
    283 
    284 Tutorial is loading...
    285 
    286 **Comments from the authors**
    287 
    288 This problem was inspired by a wrong solution to [1477D - Nezzar and Hidden Permutations](/contest/1477/problem/D "Codeforces Round 698 (Div. 1)"), but it seems that knowing that problem beforehand doesn't help at all to solve this one.
    289 
    290 [Implementation](https://codeforces.com/contest/1508/submission/113263313)
    291 
    292 [1508F - Optimal Encoding](/contest/1508/problem/F "Codeforces Round 715 (Div. 1)")
    293 
    294 Author: [Kuroni](/profile/Kuroni "International Grandmaster Kuroni")   
    295  First solve: [ecnerwala](/profile/ecnerwala "Legendary Grandmaster ecnerwala") at 01:52:02 (The only contestant who solved this problem!)
    296 
    297 **Hint 1**
    298 
    299 Start by solving the problem for $q$-encodings only.
    300 
    301 **Hint 2**
    302 
    303 We can get an encoding by including every possible edge. Which of them can we exclude?
    304 
    305 **Answer**
    306 
    307 We need to keep an edge $u \to v$ if and only if no other path from $u$ to $v$ exists.
    308 
    309 **Hint 3**
    310 
    311 What does the previous observation look like from the perspective of a single vertex?
    312 
    313 **Answer**
    314 
    315 Each vertex has at most two outgoing edges, one on each side, and we can easily characterize when one of them is redundant.
    316 
    317 **Hint 4**
    318 
    319 We need to solve the full version now. For a vertex $u$, how do the endpoints of its outgoing edges change when we add a new interval?
    320 
    321 **Answer**
    322 
    323 The endpoints of the right edges increase monotonically, while the endpoints of the left edges decrease monotonically.
    324 
    325 **Hint 5**
    326 
    327 How can we use the previous observation to characterize edges becoming redundant more concretely?
    328 
    329 **Answer**
    330 
    331 For each right edge, we can find a particular left edge, such that the right edge becomes redundant once the left edge appears. This gives us an interval of times for each edge during which it is relevant.
    332 
    333 **Hint 6**
    334 
    335 Use Mo's algorithm on the input intervals to find the relevant edges.
    336 
    337 **Tutorial**
    338 
    339 Tutorial is loading...
    340 
    341 **Comments from the authors**
    342 
    343 Huge shoutouts to [tfg](/profile/tfg "Grandmaster tfg") who came up with one of the key steps of the solution! Including this problem probably would have not been possible without him. ❤️
    344 
    345 [Implementation](https://codeforces.com/contest/1508/submission/113263058)
    346 
    347 Finally, here's some funny moments that happened while we were working on the round :)
    348 
    349 **Memes**
    350 
    351 ![ ](/predownloaded/74/2c/742c45d78eeea327e879561d6421d9c27ac140f3.png) ![ ](/predownloaded/3d/47/3d4744911219ae3c82e3774d0d497ca31bb864dd.png) ![ ](/predownloaded/d0/e5/d0e57c315c1c001b19211983c1a3e53802eebe84.png) ![ ](/predownloaded/f2/4e/f24ee861d4e3f884ebae16a1e82529607ef55b24.png) ![ ](/predownloaded/2f/b7/2fb704a2082ab3f857d17bd36ce4750cc0fa18c5.png)