codeforces-scrape

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

526.md (11319B)


      1 Source: https://codeforces.com/blog/entry/17281
      2 
      3 Hello everyone, I hope you can enjoy this special round for Zepto Lab. Here are the solutions of this round.
      4 
      5 # [A. King of Thieves](//codeforces.com/contest/526/problem/A)
      6 
      7 This task is easy for many of you. We can just iterate over all possible
      8 
      9 Unable to parse markup [type=CF_TEX]
     10 
     11 and
     12 
     13 Unable to parse markup [type=CF_TEX]
     14 
     15 , then we can compute
     16 
     17 Unable to parse markup [type=CF_TEX]
     18 
     19 , and check whether this subsequence satisfies the condition mentioned in the task.
     20 
     21 # [B. Om Nom and Dark Park](//codeforces.com/contest/526/problem/B)
     22 
     23 We use greedy and recursion to solve this task. For each tree rooted at
     24 
     25 Unable to parse markup [type=CF_TEX]
     26 
     27 , we adjust its two subtrees at first, using recursion. Then we increase one edge from
     28 
     29 Unable to parse markup [type=CF_TEX]
     30 
     31 's child to
     32 
     33 Unable to parse markup [type=CF_TEX]
     34 
     35 .
     36 
     37 # [C. Om Nom and Candies](//codeforces.com/contest/526/problem/C)
     38 
     39 If there is a kind of candy which weighs greater than
     40 
     41 Unable to parse markup [type=CF_TEX]
     42 
     43 , then we can iterate over the number of it to buy, which is less than
     44 
     45 Unable to parse markup [type=CF_TEX]
     46 
     47 .
     48 
     49 Otherwise, without loss of generality we suppose
     50 
     51 Unable to parse markup [type=CF_TEX]
     52 
     53 . If the number of the blue candies that Om Nom eats is more than
     54 
     55 Unable to parse markup [type=CF_TEX]
     56 
     57 , he could eat
     58 
     59 Unable to parse markup [type=CF_TEX]
     60 
     61 red candies instead of
     62 
     63 Unable to parse markup [type=CF_TEX]
     64 
     65 blue candies, because
     66 
     67 Unable to parse markup [type=CF_TEX]
     68 
     69 . It means the number of the blue candies will be less than
     70 
     71 Unable to parse markup [type=CF_TEX]
     72 
     73 , and we can iterate over this number.
     74 
     75 # [D. Om Nom and Necklace](//codeforces.com/contest/526/problem/D)
     76 
     77 This task is to determine whether a string is in the form of
     78 
     79 Unable to parse markup [type=CF_TEX]
     80 
     81 for each prefixes of a given string
     82 
     83 Unable to parse markup [type=CF_TEX]
     84 
     85 For a prefix P, let's split it into some blocks, just like
     86 
     87 Unable to parse markup [type=CF_TEX]
     88 
     89 , which
     90 
     91 Unable to parse markup [type=CF_TEX]
     92 
     93 is a prefix of
     94 
     95 Unable to parse markup [type=CF_TEX]
     96 
     97 . Obviously, if we use KMP algorithm, we can do it in linear time, and the length of
     98 
     99 Unable to parse markup [type=CF_TEX]
    100 
    101 will be minimal. There are only two cases :
    102 
    103 Unable to parse markup [type=CF_TEX]
    104 
    105 .
    106 
    107 1. Unable to parse markup [type=CF_TEX]
    108 
    109    . When
    110 
    111    Unable to parse markup [type=CF_TEX]
    112 
    113    . Assume that
    114 
    115    Unable to parse markup [type=CF_TEX]
    116 
    117    appears
    118 
    119    Unable to parse markup [type=CF_TEX]
    120 
    121    times. Consider "ABABAB....ABABA", the last
    122 
    123    Unable to parse markup [type=CF_TEX]
    124 
    125    must be a suffix of
    126 
    127    Unable to parse markup [type=CF_TEX]
    128 
    129    , and it must be like
    130 
    131    Unable to parse markup [type=CF_TEX]
    132 
    133    , so
    134 
    135    Unable to parse markup [type=CF_TEX]
    136 
    137    will be like
    138 
    139    Unable to parse markup [type=CF_TEX]
    140 
    141    , and so will
    142 
    143    Unable to parse markup [type=CF_TEX]
    144 
    145    . By greedy algorithm, the length of
    146 
    147    Unable to parse markup [type=CF_TEX]
    148 
    149    will be minimal, so it will be
    150 
    151    Unable to parse markup [type=CF_TEX]
    152 
    153    , where
    154 
    155    Unable to parse markup [type=CF_TEX]
    156 
    157    appears
    158 
    159    Unable to parse markup [type=CF_TEX]
    160 
    161    times. And
    162 
    163    Unable to parse markup [type=CF_TEX]
    164 
    165    will be
    166 
    167    Unable to parse markup [type=CF_TEX]
    168 
    169    , where
    170 
    171    Unable to parse markup [type=CF_TEX]
    172 
    173    appears
    174 
    175    Unable to parse markup [type=CF_TEX]
    176 
    177    times. So we just need to check whether
    178 
    179    Unable to parse markup [type=CF_TEX]
    180 
    181    .
    182 2. Unable to parse markup [type=CF_TEX]
    183 
    184    . When
    185 
    186    Unable to parse markup [type=CF_TEX]
    187 
    188    , the strategy is similar to
    189 
    190    Unable to parse markup [type=CF_TEX]
    191 
    192    . A will be like "SS...ST", and its length will be minimal. At last we just need to check whether
    193 
    194    Unable to parse markup [type=CF_TEX]
    195 
    196    .
    197 
    198 The total time complexity is
    199 
    200 Unable to parse markup [type=CF_TEX]
    201 
    202 .
    203 
    204 # [E. Transmitting Levels](//codeforces.com/contest/526/problem/E)
    205 
    206 Our task is to compute at least how many number of blocks are needed to partition a circular sequence into blocks whose sum is less than
    207 
    208 Unable to parse markup [type=CF_TEX]
    209 
    210 .
    211 
    212 By monotonicity, it is easy to get the length of maximal blocks which starts from 1 to
    213 
    214 Unable to parse markup [type=CF_TEX]
    215 
    216 in
    217 
    218 Unable to parse markup [type=CF_TEX]
    219 
    220 . Assume the block with minimal length is
    221 
    222 Unable to parse markup [type=CF_TEX]
    223 
    224 and its length is
    225 
    226 Unable to parse markup [type=CF_TEX]
    227 
    228 , it is obvious that whatever the blocks are, there must be a block that it starts in
    229 
    230 Unable to parse markup [type=CF_TEX]
    231 
    232 . So, we can iterate over all the
    233 
    234 Unable to parse markup [type=CF_TEX]
    235 
    236 numbers of
    237 
    238 Unable to parse markup [type=CF_TEX]
    239 
    240 , making it the start of a block, and calculate the number of blocks.
    241 
    242 Notice that all the lengths of blocks is (non-strictly) greater than
    243 
    244 Unable to parse markup [type=CF_TEX]
    245 
    246 , therefore the number of blocks we need is at most
    247 
    248 Unable to parse markup [type=CF_TEX]
    249 
    250 . We need to iterate
    251 
    252 Unable to parse markup [type=CF_TEX]
    253 
    254 times, but each time we can get the answer in
    255 
    256 Unable to parse markup [type=CF_TEX]
    257 
    258 , so finally we can check whether the answer is legal in
    259 
    260 Unable to parse markup [type=CF_TEX]
    261 
    262 .
    263 
    264 # [F. Pudding Monsters](//codeforces.com/contest/526/problem/F)
    265 
    266 Actually this problem is to compute how many segments in a permutation forms a permutation of successive integers.
    267 
    268 We use divide and conquer to solve this problem.
    269 
    270 If we want to compute the answer for an interval
    271 
    272 Unable to parse markup [type=CF_TEX]
    273 
    274 , we divide this interval into two smaller ones
    275 
    276 Unable to parse markup [type=CF_TEX]
    277 
    278 where
    279 
    280 Unable to parse markup [type=CF_TEX]
    281 
    282 . We only care about the segments which crosses
    283 
    284 Unable to parse markup [type=CF_TEX]
    285 
    286 . We call the first interval
    287 
    288 Unable to parse markup [type=CF_TEX]
    289 
    290 and the latter one
    291 
    292 Unable to parse markup [type=CF_TEX]
    293 
    294 .
    295 
    296 Considering the positiions of maximum numbers and minimum numbers in these valid segments, There are four possible cases:
    297 
    298 1. the maximum number is in
    299 
    300    Unable to parse markup [type=CF_TEX]
    301 
    302    , the the minimum is also in
    303 
    304    Unable to parse markup [type=CF_TEX]
    305 
    306    ;
    307 2. the maximum number is in
    308 
    309    Unable to parse markup [type=CF_TEX]
    310 
    311    , the the minimum is also in
    312 
    313    Unable to parse markup [type=CF_TEX]
    314 
    315    ;
    316 3. the maximum number is in
    317 
    318    Unable to parse markup [type=CF_TEX]
    319 
    320    , the the minimum is in
    321 
    322    Unable to parse markup [type=CF_TEX]
    323 
    324    ;
    325 4. the maximum number is in
    326 
    327    Unable to parse markup [type=CF_TEX]
    328 
    329    , the the minimum is in
    330 
    331    Unable to parse markup [type=CF_TEX]
    332 
    333    ;
    334 
    335 Let
    336 
    337 Unable to parse markup [type=CF_TEX]
    338 
    339 be the given sequence and we define
    340 
    341 Unable to parse markup [type=CF_TEX]
    342 
    343 . Similarly we can define
    344 
    345 Unable to parse markup [type=CF_TEX]
    346 
    347 .
    348 
    349 For simplicity we only cares about case 1 and case 4.
    350 
    351 In Case 1, we iterate over the start position of the segment, so we know the maximum and minimum number so we can compute the length of the segment and check the corresponding segment using
    352 
    353 Unable to parse markup [type=CF_TEX]
    354 
    355 and
    356 
    357 Unable to parse markup [type=CF_TEX]
    358 
    359 .
    360 
    361 In Case 4, we iterate over the start position again, denoted as
    362 
    363 Unable to parse markup [type=CF_TEX]
    364 
    365 . Suppose the right end is
    366 
    367 Unable to parse markup [type=CF_TEX]
    368 
    369 , then we know that
    370 
    371 Unable to parse markup [type=CF_TEX]
    372 
    373 so we can limit
    374 
    375 Unable to parse markup [type=CF_TEX]
    376 
    377 into some range. Another constraint for
    378 
    379 Unable to parse markup [type=CF_TEX]
    380 
    381 is that
    382 
    383 Unable to parse markup [type=CF_TEX]
    384 
    385 , i.e.
    386 
    387 Unable to parse markup [type=CF_TEX]
    388 
    389 . Note that when
    390 
    391 Unable to parse markup [type=CF_TEX]
    392 
    393 varies, the valid range for
    394 
    395 Unable to parse markup [type=CF_TEX]
    396 
    397 also varies, but the range is monotone, so we can maintain how many times a number appears in linear time.
    398 
    399 It's easy to show that this algorithm runs for
    400 
    401 Unable to parse markup [type=CF_TEX]
    402 
    403 , by Master Theorem.
    404 
    405 There are some other people using segment trees. You can see a nice implement [here](//codeforces.com/contest/526/submission/10584435)
    406 
    407 # [G. Spiders Evil Plan](//codeforces.com/contest/526/problem/G)
    408 
    409 In this task, we are given a tree and many queries. In each query, we are supposed to calculate the maximum total length of
    410 
    411 Unable to parse markup [type=CF_TEX]
    412 
    413 paths with the constraint that
    414 
    415 Unable to parse markup [type=CF_TEX]
    416 
    417 must be covered.
    418 
    419 Consider
    420 
    421 Unable to parse markup [type=CF_TEX]
    422 
    423 is the union of the paths (it contains nodes and edges).
    424 
    425 For each query
    426 
    427 Unable to parse markup [type=CF_TEX]
    428 
    429 , if
    430 
    431 Unable to parse markup [type=CF_TEX]
    432 
    433 , then there is always a method that
    434 
    435 Unable to parse markup [type=CF_TEX]
    436 
    437 is connected.
    438 
    439 ![ ](/predownloaded/fa/dd/fadd0452213f899badf6f088134a4a0cb454792b.png)
    440 
    441 Further, we could get the following theorem:
    442 
    443 > For an unrooted tree, if it has
    444 >
    445 > Unable to parse markup [type=CF_TEX]
    446 >
    447 > leaves, then
    448 >
    449 > Unable to parse markup [type=CF_TEX]
    450 >
    451 > paths can cover this tree completely.
    452 
    453 Proof for this theorem is that, if some edge
    454 
    455 Unable to parse markup [type=CF_TEX]
    456 
    457 is not covered, we can interchange two paths, i.e. we change two paths
    458 
    459 Unable to parse markup [type=CF_TEX]
    460 
    461 and
    462 
    463 Unable to parse markup [type=CF_TEX]
    464 
    465 to
    466 
    467 Unable to parse markup [type=CF_TEX]
    468 
    469 and
    470 
    471 Unable to parse markup [type=CF_TEX]
    472 
    473 , for
    474 
    475 Unable to parse markup [type=CF_TEX]
    476 
    477 in the subtree of
    478 
    479 Unable to parse markup [type=CF_TEX]
    480 
    481 and
    482 
    483 Unable to parse markup [type=CF_TEX]
    484 
    485 in the subtree of
    486 
    487 Unable to parse markup [type=CF_TEX]
    488 
    489 .
    490 
    491 ![ ](/predownloaded/2d/e7/2de7cf406e39f6ffa020e99fac975160cdfc3604.png)
    492 
    493 So a query
    494 
    495 Unable to parse markup [type=CF_TEX]
    496 
    497 could be described as :
    498 
    499 Find
    500 
    501 Unable to parse markup [type=CF_TEX]
    502 
    503 leaves in the tree, with node
    504 
    505 Unable to parse markup [type=CF_TEX]
    506 
    507 in
    508 
    509 Unable to parse markup [type=CF_TEX]
    510 
    511 , and maximize the total of weight of the edges in
    512 
    513 Unable to parse markup [type=CF_TEX]
    514 
    515 .
    516 
    517 For a query
    518 
    519 Unable to parse markup [type=CF_TEX]
    520 
    521 , we can make
    522 
    523 Unable to parse markup [type=CF_TEX]
    524 
    525 the root. Then this task is how to choose the leaves. Note that we could select leaves one by one, every time we select the leaf which makes answer larger without selecting the others, as follow :
    526 
    527 ![ ](/predownloaded/39/57/3957e0444442b0aeb80fd3022b19ab590cb8fbc7.png)
    528 
    529 But if for every query we need to change the root, the time complexity cannot be accepted. Assuming the longest path in the tree is
    530 
    531 Unable to parse markup [type=CF_TEX]
    532 
    533 , we could find that whatever the query is,
    534 
    535 Unable to parse markup [type=CF_TEX]
    536 
    537 will contain either
    538 
    539 Unable to parse markup [type=CF_TEX]
    540 
    541 or
    542 
    543 Unable to parse markup [type=CF_TEX]
    544 
    545 certainly.
    546 
    547 ![ ](/predownloaded/cb/20/cb20ae25193445bb7a00d199966eac8f3d28c100.png)
    548 
    549 So, we just need to make
    550 
    551 Unable to parse markup [type=CF_TEX]
    552 
    553 and
    554 
    555 Unable to parse markup [type=CF_TEX]
    556 
    557 the root in turn, and get the maximum answers. However, there is another problem :
    558 
    559 Unable to parse markup [type=CF_TEX]
    560 
    561 may not be in
    562 
    563 Unable to parse markup [type=CF_TEX]
    564 
    565 . Like this :
    566 
    567 ![ ](/predownloaded/fd/88/fd88e67f0e8c9f30e9cfa3ecf295fe59b74f6a95.png)
    568 
    569 But it doesn't matter. We just need to link
    570 
    571 Unable to parse markup [type=CF_TEX]
    572 
    573 with the selected, and erase some leaf. Of course after erasing, the answer should be maximum.
    574 
    575 ![ ](/predownloaded/ee/71/ee71fc1f52758f816217d1b485d5bea522705bf5.png)
    576 
    577 Thanks, for all of your excellent performance!