2061.md (3621B)
1 Source: https://codeforces.com/blog/entry/138620 2 3 Thank you for participating in this round! Problems I are authored by [zhoukangyang](/profile/zhoukangyang "Legendary Grandmaster zhoukangyang") and the rest by me. 4 5 Sorry for the weak pretest in problem B. 6 7 [2061A - Kevin and Arithmetic](/contest/2061/problem/A) 8 9 **Hint 1** 10 11 What is the parity of $s$ after an operation? 12 13 **Solution** 14 15 Tutorial is loading... 16 17 [2061B - Kevin and Geometry](/contest/2061/problem/B) 18 19 **Hint 1** 20 21 What is the condition for four edges to form an isosceles trapezoid? 22 23 **Hint 2** 24 25 How do you find two bases after fixing the length of the legs? 26 27 **Hint 3** 28 29 How do you choose two legs? 30 31 **Solution** 32 33 Tutorial is loading... 34 35 [2061C - Kevin and Puzzle](/contest/2061/problem/C) 36 37 **Hint 1** 38 39 How can you solve the problem in $O(n^2)$? 40 41 **Hint 2** 42 43 **No two liars can stand next to each other** is important. 44 45 **Solution** 46 47 Tutorial is loading... 48 49 [2061D - Kevin and Numbers](/contest/2061/problem/D) 50 51 **Hint 1** 52 53 Thinking outside the box. 54 55 **Hint 2** 56 57 How is a number $x$ merged from? 58 59 **Hint 3** 60 61 Approach the problem in reverse. 62 63 **Solution** 64 65 Tutorial is loading... 66 67 [2061E - Kevin and And](/contest/2061/problem/E) 68 69 **Hint 1** 70 71 Consider the minimum number that can be obtained by operating $0, 1, 2, \dots, m$ times on a number $x$. 72 73 **Hint 2** 74 75 Do these numbers have any other properties? 76 77 **Hint 3** 78 79 Consider the cost of each operation and each number independently. 80 81 **Solution** 82 83 Tutorial is loading... 84 85 [2061F1 - Kevin and Binary String (Easy Version)](/contest/2061/problem/F1) 86 87 [2061F2 - Kevin and Binary String (Hard Version)](/contest/2061/problem/F2) 88 89 **Hint 1** 90 91 What is the property for the final string? 92 93 **Hint 2** 94 95 Consider the immovable blocks. 96 97 **Hint 3** 98 99 For the easy version, fix the immovable blocks greedily. 100 101 **Hint 4** 102 103 For the hard version, use dynamic programming to determine the immovable blocks. 104 105 **Hint 5** 106 107 Use a data structure to speed up dynamic programming. 108 109 **Solution** 110 111 Tutorial is loading... 112 113 [2061G - Kevin and Teams](/contest/2061/problem/G) 114 115 **Hint 1** 116 117 What is the size of the maximum possible matching? What can be the "most dense" graph with maximum matching $k$? 118 119 **Hint 2** 120 121 Mixed-color triplet($u, v$ with edge $0$ and $v, w$ with edge $1$) is a flexible structure to find a matching for both types. 122 123 **Hint 3** 124 125 Add vertices one by one. Try to get a "mixed-color triple" or a larger set of the same color. 126 127 **Solution** 128 129 Tutorial is loading... 130 131 [2061H1 - Kevin and Stones (Easy Version)](/contest/2061/problem/H1) 132 133 [2061H2 - Kevin and Stones (Hard Version)](/contest/2061/problem/H2) 134 135 **Hint 1** 136 137 Think about the necessary conditions. 138 139 **Hint 2** 140 141 Simplify the graph while keeping the conditions. 142 143 **Hint 3** 144 145 Try to move the stones one bye one. 146 147 **Solution** 148 149 Thanks to [zhoukangyang](/profile/zhoukangyang "Legendary Grandmaster zhoukangyang") and [JohnVictor](/profile/JohnVictor "Master JohnVictor") for their discussions. A large part of the following approach comes from discussion with them. 150 151 Tutorial is loading... 152 153 [Draft in Chinese](https://drive.google.com/file/d/1-NMKUs6uyWNztU_221VkGyLfQJ-CnBCt/view?usp=sharing) 154 155 [2061I - Kevin and Nivek](/contest/2061/problem/I) 156 157 **Hint 1** 158 159 Can you compute $dp(r, *)$ from $dp(l, *)$ efficiently? 160 161 **Hint 2** 162 163 If the difference between the number of victories is large, he will either always win or always lose for type 2 matches. 164 165 **Hint 3** 166 167 We can speed up this part to $O(n \log n)$. 168 169 **Hint 4** 170 171 For the part that the difference between the number of victories is not large, solve it recursively. 172 173 **Solution** 174 175 Tutorial is loading...