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 :(.