2164.md (3126B)
1 Source: https://codeforces.com/blog/entry/148126 2 3 ## A Sequence Game 4 5 Idea from [cmk666](/profile/cmk666 "Legendary Grandmaster cmk666"), Prepared by [cmk666](/profile/cmk666 "Legendary Grandmaster cmk666") 6 7 **Hint 1** 8 9 Think some straightforward necessary conditions. They are also sufficient. 10 11 **Tutorial** 12 13 Tutorial is loading... 14 15 ## B Even Modulo Pair 16 17 Idea from [244mhq](/profile/244mhq "Legendary Grandmaster 244mhq"), Prepared by [NetSpeed1](/profile/NetSpeed1 "Legendary Grandmaster NetSpeed1") 18 19 **Hint 1** 20 21 Consider a brute force solution. What's the actual complexity of it? 22 23 **Tutorial** 24 25 Tutorial is loading... 26 27 ## C Dungeon 28 29 Idea from [Link_Cut_qwq](/profile/Link_Cut_qwq "Grandmaster Link_Cut_qwq"), Prepared by [Xiaohuba](/profile/Xiaohuba "Master Xiaohuba") 30 31 **Hint 1** 32 33 If you gain a new sword after killing a monster, its damage will be greater or equal than the previous sword. 34 35 **Hint 2** 36 37 When will we attempt to kill monsters with $c_i = 0$? 38 39 **Hint 3** 40 41 Consider a greedy approach. 42 43 **Tutorial** 44 45 Tutorial is loading... 46 47 ## D Copy String 48 49 Idea from [JoesSR](/profile/JoesSR "Legendary Grandmaster JoesSR"), Prepared by [JoesSR](/profile/JoesSR "Legendary Grandmaster JoesSR") 50 51 **Tutorial** 52 53 Tutorial is loading... 54 55 ## E Journey 56 57 Idea from [Link_Cut_qwq](/profile/Link_Cut_qwq "Grandmaster Link_Cut_qwq"), Prepared by [Xiaohuba](/profile/Xiaohuba "Master Xiaohuba") 58 59 **Hint 1** 60 61 Consider when we do not need *transferring*. 62 63 **Hint 2** 64 65 How to calculate the minimum cost when *transferring* between two vertices? 66 67 **Hint 3** 68 69 Come up with a greedy approach. 70 71 **Tutorial** 72 73 Tutorial is loading... 74 75 ## F1/F2 Chain Prefix Rank 76 77 Idea from [JoesSR](/profile/JoesSR "Legendary Grandmaster JoesSR"), Prepared by [JoesSR](/profile/JoesSR "Legendary Grandmaster JoesSR") 78 79 **Tutorial** 80 81 Tutorial is loading... 82 83 ## G Pointless Machine 84 85 Idea from [Daniel777](/profile/Daniel777 "International Grandmaster Daniel777"), Prepared by [zjy2008](/profile/zjy2008 "Legendary Grandmaster zjy2008") 86 87 **Hint 1** 88 89 We can know the degree of each vertex within two queries. 90 91 **Hint 2** 92 93 First come up with an solution that require $2\lceil\log_2(n)\rceil+1$ queries. 94 95 **Hint 3** 96 97 Partition the vertex to 3 groups instead of 2. 98 99 **Tutorial** 100 101 Tutorial is loading... 102 103 ## H PalindromePalindrome 104 105 Idea from [zjy2008](/profile/zjy2008 "Legendary Grandmaster zjy2008"), Prepared by [zjy2008](/profile/zjy2008 "Legendary Grandmaster zjy2008") 106 107 **UPD: Unfortunately, the original analysis regarding the number of "relevant" pairs of disjoint substrings was incorrect. The proof was derived from an online blog concerning the range distinct palindrome substring query problem, but that proof turned out to be flawed. Consequently, we previously believed the complexity of the standard solution to be $O((n + q) \log n)$; however, after the contest, we discovered that it is actually $\Theta(n \log^2 n + q \log n)$ (and this lower bound is reachable). We apologize for any confusion caused.** 108 109 **Hint 1** 110 111 Consider classifying the cases based on the relative positions of two palindromic substrings. 112 113 **Tutorial** 114 115 Tutorial is loading...