1951.md (8181B)
1 Source: https://codeforces.com/blog/entry/128116 2 3 Hi, we hope you enjoyed our problems! For the playlist of songs used in the problem statements, click [this link](https://www.youtube.com/playlist?list=PLTVdHvnX6LZhAJre49E7M7tpGA30WlBM3). 4 5 [1951A - Dual Trigger](/contest/1951/problem/A "Codeforces Global Round 25") 6 7 Author: [MofK](/profile/MofK "Grandmaster MofK") 8 Prepared by [Kuroni](/profile/Kuroni "International Grandmaster Kuroni") 9 First solve: [xiachong](/profile/xiachong "Grandmaster xiachong") at 00:01 10 11 **Tutorial and Implementation** 12 13 Tutorial is loading... 14 15 [255371605](/contest/1951/submission/255371605 "Submission 255371605 by Kuroni") 16 17 **Rate this problem** 18 19 Yay 20 21 Meh 22 23 Nay 24 25 Banger song 26 27 [1951B - Battle Cows](/contest/1951/problem/B "Codeforces Global Round 25") 28 29 Author: [MofK](/profile/MofK "Grandmaster MofK") 30 Prepared by [Kuroni](/profile/Kuroni "International Grandmaster Kuroni") 31 First solve: [pavement](/profile/pavement "Master pavement") at 00:05 32 33 **Hint 1** 34 35 What is the condition for your cow to win her first match? 36 37 **Hint 2** 38 39 If your cow is not already winning her first match, there are at most two candidate positions you can swap her to. 40 41 **Tutorial and Implementation** 42 43 Tutorial is loading... 44 45 [255371643](/contest/1951/submission/255371643 "Submission 255371643 by Kuroni") 46 47 **Comments from the authors** 48 49 This problem was added after [1951D - Buying Jewels](/contest/1951/problem/D "Codeforces Global Round 25") was deemed too hard to be problem B. At first, we decided to hide the case of swapping with the first stronger cow from the sample test. The testers weren't too impressed: 50 51  52 53 **Rate this problem** 54 55 Yay 56 57 Meh 58 59 Nay 60 61 Banger song 62 63 [1951C - Ticket Hoarding](/contest/1951/problem/C "Codeforces Global Round 25") 64 65 Author: [MofK](/profile/MofK "Grandmaster MofK") 66 Prepared by [Kuroni](/profile/Kuroni "International Grandmaster Kuroni") 67 First solve: [arvindf232](/profile/arvindf232 "Legendary Grandmaster arvindf232") at 00:11 68 69 **Hint 1** 70 71 If there is no additional cost (i.e. buying a ticket at day $i$ costs only $a_i$), what is the optimal buying strategy? 72 73 **Hint 2** 74 75 If there \textit{is} additional cost but $a_i = 1$ for all $i$, what is the optimal buying strategy? 76 77 **Hint 3** 78 79 The above two strategies are the same, and the primary and secondary costs are independent of each other. \textit{Surely} the solution is not just choosing $k$ cheapest tickets right? 80 81 **Tutorial and Implementation** 82 83 Tutorial is loading... 84 85 [255371666](/contest/1951/submission/255371666 "Submission 255371666 by Kuroni") 86 87 **Rate this problem** 88 89 Yay 90 91 Meh 92 93 Nay 94 95 Banger song 96 97 [1951D - Buying Jewels](/contest/1951/problem/D "Codeforces Global Round 25") 98 99 Author: [MofK](/profile/MofK "Grandmaster MofK") 100 Prepared by [MofK](/profile/MofK "Grandmaster MofK") 101 First solve: [conqueror_of_tourist](/profile/conqueror_of_tourist "Legendary Grandmaster conqueror_of_tourist") at 00:14 102 103 **Hint** 104 105 Perhaps the easiest way of dealing with this problem is writing down small cases and see what happens. 106 107 **Tutorial and Implementation** 108 109 Tutorial is loading... 110 111 [255371688](/contest/1951/submission/255371688 "Submission 255371688 by Kuroni") 112 113 **Comments from the authors** 114 115 This problem was originally problem B. It turned out to be too hard and was switched to C, with [1951B - Battle Cows](/contest/1951/problem/B "Codeforces Global Round 25") inserted, before being further switched to D as it was still too hard. 116 117 **Rate this problem** 118 119 Yay 120 121 Meh 122 123 Nay 124 125 Banger song 126 127 [1951E - No Palindromes](/contest/1951/problem/E "Codeforces Global Round 25") 128 129 Author: [MofK](/profile/MofK "Grandmaster MofK") 130 Prepared by [MofK](/profile/MofK "Grandmaster MofK") 131 First solve: [DottedCalculator](/profile/DottedCalculator "Specialist DottedCalculator") at 00:16 132 133 **Hint** 134 135 Let $i$ be the first character that is different from $s_1$. Then $s_{1..i}$ is not a palindrome. If $s_{i+1..n}$ is also not a palindrome then we are done, but what can we do if it is? 136 137 **Tutorial and Implementation** 138 139 Tutorial is loading... 140 141 [255371747](/contest/1951/submission/255371747 "Submission 255371747 by Kuroni") 142 143 **Comments from the authors** 144 145 It is rather unfortunate that the solution only uses partitions of at most size $2$, therefore one can "solve" the problem by brute forcing every possible partition and check validity using any string matching algorithm. Nevertheless, we tried our hardest to make sure dumber "solutions" won't pass. 146 147 **Rate this problem** 148 149 Yay 150 151 Meh 152 153 Nay 154 155 Banger song 156 157 [1951F - Inversion Composition](/contest/1951/problem/F "Codeforces Global Round 25") 158 159 Author: [Kuroni](/profile/Kuroni "International Grandmaster Kuroni") 160 Prepared by [Kuroni](/profile/Kuroni "International Grandmaster Kuroni") 161 First solve: [CeItic](/profile/CeItic "Pupil CeItic") at 00:42 162 163 **Hint 1** 164 165 Let's look at the "inverseness" of $(p_i, p_j)$ on $q$ and $(i, j)$ on $q \cdot p$. What is their relation to the inverseness of $(i, j)$ on $p$? 166 167 **Hint 2** 168 169 They either contribute $0$ or $2$ if $(i, j)$ is not an inverse on $p$, or $1$ if $(i, j)$ is an inverse on $p$. We now know the necessary condition for $k$ if there is an answer. This is also sufficient. 170 171 **Tutorial and Implementation** 172 173 Tutorial is loading... 174 175 [255371767](/contest/1951/submission/255371767 "Submission 255371767 by Kuroni") 176 177 **Rate this problem** 178 179 Yay 180 181 Meh 182 183 Nay 184 185 Banger song 186 187 [1951G - Clacking Balls](/contest/1951/problem/G "Codeforces Global Round 25") 188 189 Author: [MofK](/profile/MofK "Grandmaster MofK") 190 Prepared by [Kuroni](/profile/Kuroni "International Grandmaster Kuroni") 191 First solve: [Little09_love_YCY](/profile/Little09_love_YCY "Master Little09_love_YCY") at 00:19 192 193 **Hint 1** 194 195 We should represent a state as the sequence of distances between each pair of consecutive balls. 196 197 **Hint 2** 198 199 [This should probably help.](https://codeforces.com/blog/entry/77284#comment-620956) 200 201 **Tutorial and Implementation** 202 203 Tutorial is loading... 204 205 [255371802](/contest/1951/submission/255371802 "Submission 255371802 by Kuroni") 206 207 **Rate this problem** 208 209 Yay 210 211 Meh 212 213 Nay 214 215 Banger song 216 217 [1951H - Thanos Snap](/contest/1951/problem/H "Codeforces Global Round 25") 218 219 Author: [Kuroni](/profile/Kuroni "International Grandmaster Kuroni") 220 Prepared by [Kuroni](/profile/Kuroni "International Grandmaster Kuroni") 221 First solve: [ecnerwala](/profile/ecnerwala "Legendary Grandmaster ecnerwala") at 01:34 222 223 **Hint 1** 224 225 Let's binary search the answer. Every element is now either $0$ or $1$, and Alice tries to get $1$. 226 227 **Hint 2** 228 229 Let's directly construct the strategy for Alice. It can be viewed as a perfect binary game tree. 230 231 **Hint 3** 232 233 Construct the strategy greedily bottom-up. 234 235 **Tutorial and Implementation** 236 237 Tutorial is loading... 238 239 [255374619](/contest/1951/submission/255374619 "Submission 255374619 by Kuroni") 240 241 **Rate this problem** 242 243 Yay 244 245 Meh 246 247 Nay 248 249 Banger song 250 251 [1951I - Growing Trees](/contest/1951/problem/I "Codeforces Global Round 25") 252 253 Author: [Kuroni](/profile/Kuroni "International Grandmaster Kuroni") 254 Prepared by [Kuroni](/profile/Kuroni "International Grandmaster Kuroni") 255 First solve: [rainboy](/profile/rainboy "Master rainboy") at 02:27 256 257 **Hint 1** 258 259 [This helps to check if $x$ satisfies](https://en.wikipedia.org/wiki/Nash-Williams_theorem). Pattern match it to [Hall's marriage theorem](https://en.wikipedia.org/wiki/Hall%27s_marriage_theorem). 260 261 **Hint 2** 262 263 It is possible to check if $x$ satisfies with $n$ flow runs, each flow graph having $O(n + m)$ nodes and edges. 264 265 **Hint 3** 266 267 Spanning trees are independent sets of the graphic matroid. [Direct sums of $k$ such matroids is also a matroid.](https://en.wikipedia.org/wiki/Matroid#:~:text=.%5B20%5D-,Sums%20and%20unions,-%5Bedit%5D). 268 269 **Hint 4** 270 271 We can greedily select to increase $x_i$ with the least increment cost that still satisfies. Quickly simulate this via a binary search. 272 273 **Tutorial and Implementation** 274 275 Tutorial is loading... 276 277 [255371862](/contest/1951/submission/255371862 "Submission 255371862 by Kuroni") 278 279 **Rate this problem** 280 281 Yay 282 283 Meh 284 285 Nay 286 287 Banger song 288 289 **UPD**: Added implementations.