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  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  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  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  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  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  576 577 Thanks, for all of your excellent performance!