codeforces-scrape

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

1427.md (7870B)


      1 Source: https://codeforces.com/blog/entry/83553
      2 
      3 #### General comments
      4 
      5 Broadly speaking, problems A-B-C-D were "div2 problems", while F-G-H were "strong grandmaster problems" (with E staying in the middle). I did not expect anyone to solve all the problems and thus I decided to give the scoring F+G=H (so that maybe someone would have solved H).   
      6   
      7  Many of the problems (A, C, D, E, G) admit multiple solutions. Sometimes the core of the solution is the same (C, D) and sometimes the solutions are truly different (A, E, G).   
      8   
      9  If you are an experienced participant, I would like to hear your opinion on the problems. Feel free to comment on this post or send me a private message.
     10 
     11 **Overview of the problemset**
     12 
     13 The easiest problem of the contest, *A-Avoiding Zero*, is about rearranging an array of numbers. It is intended as a very easy problem that still requires to think. Then, in *B-Chess Cheater* an intuitive (but nontrivial to prove) greedy approach is the way to go. *C-The Hard Work of Paparazzi* is a classical dynamic-programming problem with a twist. *D-Unshuffling a deck* is a constructive problem with a multitude of possible solutions (all somewhat similar). The difficulty difference between *D* and *E-Xum* is pretty large. Problem *E* asks to produce the number $1$ (starting from a given number) using only the addition and the xor. A super-clean mathy approach is possible, but also a huge amount of (vastly different) randomized approaches (clean and not so clean) can lead to the solution.   
     14   
     15  Problems *F*, *G* have a similar difficulty. They are very different, so participants could choose which one to attack depending on their taste. Problem *F-Boring Card Game* asks to reconstruct the moves of a game given the final situation. Even if it looks as one more constructive problem, it is not. The crux of the problem is finding a criterion for the admissibility of a final situation and then noticing that a naive greedy algorithm produces a sequence of moves generating such final situation. It requires quite a bit of thinking, but then the implementation is trivial. Problem *G-One Billion Shades of Grey* has the clear smell of a flow, and indeed it is a flow problem! There are two possible approaches: either you have a clever idea, or you apply some advanced classical theory followed by a certain amount of optimizations. Compared to problem *F*, in *G* the ideas are more standard but the implementation is not immediate. Since the statement is extremely simple, it is possible that some versions of this problem are known (and I actually found at least one research paper considering something similar). I decided that the problem is beautiful enough to take the risk.   
     16   
     17  Finally we have *H-Prison Break* which is much harder than all other problems. Even if it is a variation over the well known [Cat and Mouse problem](https://www.youtube.com/watch?time_continue=3&v=vF_-ob9vseM&feature=emb_logo), knowing the solution to the latter is not very helpful. It is a very nonstandard problem and a mix of mathematical insight and ability to handle an involved implementation is necessary to get accepted.
     18 
     19 #### Hints
     20 
     21 **A**
     22 
     23 **Hint 1**
     24 
     25 If $a_1 + \cdots + a_n = 0$, then the answer is NO.
     26 
     27   
     28 
     29 **Hint 2**
     30 
     31 If $a_1 + \cdots + a_n \not=0$, then the answer is YES.
     32 
     33   
     34 
     35 **Hint 3**
     36 
     37 If $a_1 + \cdots + a_n \gt 0$, then there is a rearrangement such that all prefix sums are strictly positive.
     38 
     39   
     40 
     41 **B**
     42 
     43 **Hint 1**
     44 
     45 The score is $2\cdot\texttt{#{wins}} - \texttt{#{winning_streaks}}$.
     46 
     47   
     48 
     49 **Hint 2**
     50 
     51 You shall minimize the number of disjoint winning streaks.
     52 
     53   
     54 
     55 **Hint 3**
     56 
     57 Fill the holes between winning streaks.
     58 
     59   
     60 
     61 **C**
     62 
     63 **Hint 1**
     64 
     65 Find an $O(n^2)$ dynamic-programming solution.
     66 
     67   
     68 
     69 **Hint 2**
     70 
     71 The city is relatively small (i.e.,
     72 
     73 Unable to parse markup [type=CF_MATHJAX]
     74 
     75 ).   
     76 
     77 **Hint 3**
     78 
     79 If
     80 
     81 Unable to parse markup [type=CF_MATHJAX]
     82 
     83 then it is possible to go from the $i$-th appearance to the $j$-th appearance. Use this observation to optimize the $O(n^2)$ solution to $O(nr)$.
     84 
     85   
     86    
     87 
     88 **D**
     89 
     90 **Hint 1**
     91 
     92 If two consecutive cards have consecutive numbers (in the right order) then you can "merge them".
     93 
     94   
     95 
     96 **Hint 2**
     97 
     98 Consider only moves with small $k$.
     99 
    100   
    101 
    102 **Hint 3**
    103 
    104 Find one move that increases by at least $1$ the number of adjacent cards with consecutive numbers.
    105 
    106   
    107 
    108 **E**
    109 
    110 There are two different solutions.   
    111  Solution 1:   
    112 
    113 **Hint 1**
    114 
    115 Write a number $y$ coprime with $x$.
    116 
    117   
    118 
    119 **Hint 2**
    120 
    121 Write the gcd between $x$ and $y$ (that is $1$).
    122 
    123   
    124 
    125 **Hint 3**
    126 
    127 Bezout's Theorem.
    128 
    129   
    130 
    131 **Hint 4**
    132 
    133 If
    134 
    135 Unable to parse markup [type=CF_MATHJAX]
    136 
    137 and $b$ is even, then $a\wedge b=1$.
    138 
    139   
    140  Solution 2:   
    141 
    142 **Hint 1**
    143 
    144 Keep a basis of the numbers that are the xor of a subset of the numbers on the blackboard (i.e., the xor-subspace generated by numbers on the blackboard).
    145 
    146   
    147 
    148 **Hint 2**
    149 
    150 Make some random choices.
    151 
    152   
    153 
    154 **Hint 3**
    155 
    156 If $x=2^{19} + 1$, then it is necessary to write a number
    157 
    158 Unable to parse markup [type=CF_MATHJAX]
    159 
    160 on the blackboard.
    161 
    162   
    163 
    164 **Hint 4**
    165 
    166 Choose randomly two numbers from the xor-subspace and write their sum on the blackboard.
    167 
    168   
    169 
    170 **F**
    171 
    172 **Hint 1**
    173 
    174 Solve the problem without the constraint of alternating turns.
    175 
    176   
    177 
    178 **Hint 2**
    179 
    180 The final situation is achievable if and only if it is achievable without alternating turns but with Giada taking the last turn.
    181 
    182   
    183 
    184 **Hint 3**
    185 
    186 Use a greedy approach to take care of the alternating turns.
    187 
    188   
    189 
    190 **G**
    191 
    192 There are two different solutions.   
    193  Solution 1:   
    194 
    195 **Hint 1**
    196 
    197 Solve the problem when the already painted tiles have only two shades.
    198 
    199   
    200 
    201 **Hint 2**
    202 
    203 Formulate the problem as many min-cuts problems.
    204 
    205   
    206 
    207 **Hint 3**
    208 
    209 Update the max-flow repeatedly to compute quickly enough the many min-cuts.
    210 
    211   
    212  Solution2:   
    213 
    214 **Hint 1**
    215 
    216 Formulate the problem as a linear-programming problem.
    217 
    218   
    219 
    220 **Hint 2**
    221 
    222 Compute the dual of the problem.
    223 
    224   
    225 
    226 **Hint 3**
    227 
    228 Use the shortest-augmenting-path algorithm to compute the min-cost maxflow and optimize Dijkstra as much as possible (and simplify the graph as much as possible).
    229 
    230   
    231 
    232 **H**
    233 
    234 **Hint 1**
    235 
    236 Solve the problem with one guard instead of two.
    237 
    238   
    239 
    240 **Hint 2**
    241 
    242 If the prisoner can escape, his strategy is easy.
    243 
    244   
    245 
    246 **Hint 3**
    247 
    248 If the prisoner can escape, then he should go to a point on the climbable walls and either escape immediately or go toward one of two different points on the climbable walls and escape there.
    249 
    250   
    251 
    252 **Hint 4**
    253 
    254 The prisoner can escape if and only if there are three points A < B < C on the climbable walls such that a guard cannot go from B to A as fast as the prisoner and a guard cannot go from B to C as fast as the prisoner.
    255 
    256   
    257 
    258 **Hint 5**
    259 
    260 Binary search on the answer.
    261 
    262   
    263 
    264 **Hint 6**
    265 
    266 Fix the sides where A and B are. The points B such that there is a good point A form an interval, determine the interval.
    267 
    268   
    269 
    270 **Hint 7**
    271 
    272 Be optimistic and use ternary-search (or be less optimistic and solve a bunch of quadratic equations).
    273 
    274   
    275 
    276 #### Solutions
    277 
    278 **A**
    279 
    280 Tutorial is loading...
    281 
    282 [Solution code](https://codeforces.com/contest/1427/submission/95156251)   
    283 
    284 **B**
    285 
    286 Tutorial is loading...
    287 
    288 [Solution code](https://codeforces.com/problemset/submission/1427/95156305)
    289 
    290   
    291 
    292 **C**
    293 
    294 Tutorial is loading...
    295 
    296 [Solution code](https://codeforces.com/problemset/submission/1427/95156325)
    297 
    298   
    299 
    300 **D**
    301 
    302 Tutorial is loading...
    303 
    304 [Solution code](https://codeforces.com/problemset/submission/1427/95156351)
    305 
    306   
    307 
    308 **E**
    309 
    310 Tutorial is loading...
    311 
    312 [Solution code](https://codeforces.com/problemset/submission/1427/95156382)
    313 
    314   
    315 
    316 **F**
    317 
    318 Tutorial is loading...
    319 
    320 [Solution code](https://codeforces.com/problemset/submission/1427/95156396)
    321 
    322   
    323 
    324 **G**
    325 
    326 Tutorial is loading...
    327 
    328 [Solution code](https://codeforces.com/problemset/submission/1427/95156412)
    329 
    330   
    331 
    332 **H**
    333 
    334 Tutorial is loading...
    335 
    336 [Solution code](https://codeforces.com/problemset/submission/1427/95156439)