codeforces-scrape

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

1425.md (6062B)


      1 Source: https://codeforces.com/blog/entry/83148
      2 
      3 Hi everyone, sorry for the considerable delay. It turns out, we were exhausted yesterday from supervising two contests back-to-back. We are surprised by the number of participants in the online mirror. And I hope you enjoy the problems :)
      4 
      5 Our big surprise was problem B. We were setting it to be a medium problem. Turns out, maybe the observation is not that obvious.
      6 
      7 **fun fact:** Initially, we don't plan to have any particular naming theme other than the obligatory first letter matches the problem order. However, when naming 6 out of 9 problems, one of my committee member noticed that **5 problems** have A of B theme. So, we decided to continue using this theme.
      8 
      9 Here are the authors and first solvers for all problems:
     10 
     11 **A — Arena of Greed**
     12 
     13 Author: [JulianFernando](/profile/JulianFernando "Master JulianFernando")
     14 
     15 Expected difficulty: Medium
     16 
     17 Tag: greedy
     18 
     19 First solver: [kotamanegi](/profile/kotamanegi "International Grandmaster kotamanegi")
     20 
     21 **B — Blue and Red of Our Faculty!**
     22 
     23 Author: [dewa251202](/profile/dewa251202 "Expert dewa251202"), [hiddentesla](/profile/hiddentesla "Master hiddentesla")
     24 
     25 Expected difficulty: Medium-hard
     26 
     27 Tag: dynamic programming
     28 
     29 First solver: team NeedHelpPls: [MiricaMatei](/profile/MiricaMatei "Master MiricaMatei"), [AlexLuchianov](/profile/AlexLuchianov "Master AlexLuchianov"), [loan](/profile/loan "Grandmaster loan")
     30 
     31 **C — Captain of Knights**
     32 
     33 Author: [AMnu](/profile/AMnu "Expert AMnu")
     34 
     35 Expected difficulty: Very hard
     36 
     37 Tag: math
     38 
     39 First solver: team Extra Registration: [LJC00118](/profile/LJC00118 "Grandmaster LJC00118"), [xay5421](/profile/xay5421 "Grandmaster xay5421"), [Sulfox](/profile/Sulfox "International Grandmaster Sulfox")
     40 
     41 **D — Danger of Mad Snakes**
     42 
     43 Author: [hiddentesla](/profile/hiddentesla "Master hiddentesla")
     44 
     45 Expected difficulty: medium
     46 
     47 Tag: Inclusion-exclusion, DP prefix sum.
     48 
     49 First solver: team hsy-DD: [Yukikaze_](/profile/Yukikaze_ "Candidate Master Yukikaze_"), [Fuyuki](/profile/Fuyuki "International Grandmaster Fuyuki"), [xzx34](/profile/xzx34 "Expert xzx34")
     50 
     51 **E — Excitation of Atoms**
     52 
     53 Author: [hiddentesla](/profile/hiddentesla "Master hiddentesla")
     54 
     55 Expected difficulty: easy-medium
     56 
     57 tag: Adhoc, casework.
     58 
     59 First solver: [jiangly](/profile/jiangly "Legendary Grandmaster jiangly")
     60 
     61 **F — Flamingoes of Mystery**
     62 
     63 Author: [kiwii](/profile/kiwii "Master kiwii")
     64 
     65 Expected Difficulty: easy
     66 
     67 Tag: Adhoc
     68 
     69 First solver: Team LCA on Cactus: [tem_shett](/profile/tem_shett "Master tem_shett"), [Dart-Xeyter](/profile/Dart-Xeyter "Master Dart-Xeyter"), [sevlll777](/profile/sevlll777 "International Master sevlll777")
     70 
     71 **H — Huge Boxes of Animal Toys**
     72 
     73 Author: [kiwii](/profile/kiwii "Master kiwii")
     74 
     75 Expected Difficulty: easy
     76 
     77 Tag: Adhoc
     78 
     79 First solver: idea guy, snake wrangler, and deep learner: [oof_ouch_owie](/profile/oof_ouch_owie "Unrated, oof_ouch_owie"), [tenth](/profile/tenth "Candidate Master tenth"), [WolfBlue](/profile/WolfBlue "Expert WolfBlue").
     80 
     81 **I — Impressive Harvest of The Orchad**
     82 
     83 Author: [kiwii](/profile/kiwii "Master kiwii"), [hiddentesla](/profile/hiddentesla "Master hiddentesla")
     84 
     85 Expected Difficulty: Hard
     86 
     87 Tags: SQRT algorithms, Segment tree beats.
     88 
     89 First solver: IIT Patna: [ravik1](/profile/ravik1 "Candidate Master ravik1"), [Sixpathsguy](/profile/Sixpathsguy "Candidate Master Sixpathsguy"), [darklight13](/profile/darklight13 "Candidate Master darklight13")
     90 
     91 Tutorial is loading...
     92 
     93 Code: [94148836](/contest/1425/submission/94148836 "Submission 94148836 by hiddentesla")
     94 
     95 Tutorial is loading...
     96 
     97 $O(N^2 \sqrt{N})$ code: [94149019](/contest/1425/submission/94149019 "Submission 94149019 by hiddentesla")
     98 
     99 $O(N^2)$ code: [94149066](/contest/1425/submission/94149066 "Submission 94149066 by hiddentesla")
    100 
    101 Tutorial is loading...
    102 
    103 code: [94149150](/contest/1425/submission/94149150 "Submission 94149150 by hiddentesla")
    104 
    105 Tutorial is loading...
    106 
    107 code: [94149327](/contest/1425/submission/94149327 "Submission 94149327 by hiddentesla")
    108 
    109 Tutorial is loading...
    110 
    111 code: [93947185](/contest/1425/submission/93947185 "Submission 93947185 by kiwii")
    112 
    113 Tutorial is loading...
    114 
    115 code: [94151055](/contest/1425/submission/94151055 "Submission 94151055 by hiddentesla")
    116 
    117 Tutorial is loading...
    118 
    119 code: [94151563](/contest/1425/submission/94151563 "Submission 94151563 by hiddentesla")
    120 
    121 Tutorial is loading...
    122 
    123 Code (without lazy propagation): [94152055](/contest/1425/submission/94152055 "Submission 94152055 by hiddentesla")
    124 
    125 Code (with lazy propagation): [94152123](/contest/1425/submission/94152123 "Submission 94152123 by hiddentesla")
    126 
    127 **Honorable mention:** the fastest $O(NQ)$ solution during the contest: [93941953](/contest/1425/submission/93941953 "Submission 93941953 by Bajetii")
    128 
    129 # About problem G
    130 
    131 Problem G was really saddening. We had a cool solution using convex hulls. The solution idea is for we find all connected components of "#". For each CC, we push to a set all non-"#" squares connected in the top, right, left, and down of each '#' and then build a \textbf{convex hull} from the set. The convex hull is then marked the safe zone. If the thief can reach one of these safe zones, the answer is "lolos".
    132 
    133 However, after the contest, one participant found the counter case on solutions like this:
    134 
    135 ```
    136 5 5
    137 M....
    138 .....
    139 ..#..
    140 ...C.
    141 .....
    142 ```
    143 
    144 The distance from the thief to each safe zone is not less than Mr. Chanek. However, the thief can move to bottom-right, which can then react to Mr. Chanek's next move. (output is "lolos", jury will print "tertangkap").
    145 
    146 We are sad and are currently finding the correct answer. We have also taken down the problem (for now). We manually verify every test case during the test generation of this problem, so they are correct. During the contest (official and mirror), nobody managed to pass the test cases (except [jiangly](/profile/jiangly "Legendary Grandmaster jiangly")), so it does not affect the standings. However, broken is still broken. We hope it does not reduce the enjoyment of the other problems that much :(.