1552.md (18593B)
1 Source: https://codeforces.com/blog/entry/93199 2 3 We hope you liked the problems! Before we go ahead with the editorial, let us make some general comments about this round. 4 5 Problems A, B, C, D, E, F are "div 2" problems, while problems G, H, I are meant to be solved by Grandmasters. Overall, our goal was to provide a problemset that could be enjoyable for a wide range of participants and such that the winner could solve all the problems. 6 7 There were three big "jumps" in the difficlty gaps between consecutive problems. Problems A and B are meant to be easy, many contestants have the skills and the techniques to attack them (and, maybe, to solve them). Problems C, D, E, F are gradually harder but the difficulty gap between C and F is not as large as usual (and this is reflected in the score distribution). The same holds for problem G, H, I; the difficulty gap between G and I is relatively small (but there is a big score difference because coding I is much harder). Sadly, we discovered 14 minutes into the round that problem I [has already appeared in a contest](https://codeforces.com/contest/243/problem/E) (most likely also in Polish contest, if you know it please tell us in the comments). See also [this comment](https://codeforces.com/blog/entry/93018?#comment-820809). 8 9 **Pre-contest predictions** 10 11 Let us now make some predictions (you, future reader, can check whether we were right or wrong). We promise not to change these predictions after the beginning of the contest. 12 13 * After 20 minutes someone has solved 4 problems. 14 * After 40 minutes someone has solved 6 problems. 15 * After 70 minutes someone has solved 7 problems. 16 * After 100 minutes someone has solved 8 problems. 17 * At least one contestant solves all the problems. 18 * There is a big difference in number of solves between F and G (let's say a factor 3). 19 * The best Italian contestant solves 6 problems. 20 * There are $\ge 10\,000$ solves for problem A. 21 22 The contest is now finished and our predictions are far from being perfect, but, for intellectual honesty, we are not changing them. 23 24 **Detailed overview on the problemset and a bit of behind-the-scenes** 25 26 In problem [1552A - Subsequence Permutation](/contest/1552/problem/A "Codeforces Global Round 15") you had to sort a sequence by changing the minimum number of elements... you better not touch elements which are already in the correct position! Fun fact: this problem appears again, as an optimization step (not really required to get accepted), in problem G. 27 28 Problem [1552B - Running for Gold](/contest/1552/problem/B "Codeforces Global Round 15"), about the ongoing Olympic Games, had a real-life statement and an obvious quadratic algorithm which had to be improved to get accepted. It could be solved either by an intuitive observation (only one athlete can win the gold medal!) or with a super-simple randomized approach. This problem was added (and changed) last-minute (that is, 2 days before the contest) to make the problemset more balanced. Bonus version: with the same constraints, find the number of athletes who are "likely to get a medal", i.e. who are superior to all but (at most) $2$ other athletes. 29 30 In problem [1552C - Maximize the Intersections](/contest/1552/problem/C "Codeforces Global Round 15") you had to maximize the number of intersections of chords in a circle. It's natural to add the new chords so that they all intersect each other... it turns out that this is enough to solve the problem! This was a subproblem of a harder problem that we discarded because it did not fit the problemset (and it was not particularly nice). 31 32 Problem [1552D - Array Differentiation](/contest/1552/problem/D "Codeforces Global Round 15"), in which you had to write an array as differences of the value of another array, was an undercover graph problem. Once the necessary and sufficient condition is identified, coding it is very easy. Until 5 days before the contest, this was problem B. Since it was too hard for a B, it was moved to D and a new problem B was added. 33 34 Problem [1552E - Colors and Intervals](/contest/1552/problem/E "Codeforces Global Round 15") is a combinatorics problem that asks you to select some "almost disjoint" intervals respecting certain properties. It can be tackled by unexpected simple greedy algorithms. Some variations of this problem appeared in the past (we know of at least two similar problems), but since it is a nice problem and nobody found this version anywhere we decided to give it anyway. 35 36 At first sight, problem [1552F - Telepanting](/contest/1552/problem/F "Codeforces Global Round 15"), about an ant moving and teleporting, seems to require an exponential amount of time to be solved. Once one notices that the states of the portals satisfy a rigid property, it is not hard to come up with a polynomial (actually pseudo-linear) solution. If one drops the assumption $y_i \lt x_i$ it becomes impossible for the authors to solve it. 37 38 Problem [1552G - A Serious Referee](/contest/1552/problem/G "Codeforces Global Round 15") presents you with a daunting task: you are given a "generalized" sorting network and you must tell whether it really is a sorting network or not. Standard knowledge about sorting networks is useful but not sufficient to solve the problem. 39 40 Problem [1552H - Guess the Perimeter](/contest/1552/problem/H "Codeforces Global Round 15") is a strange interactive problem in which you must guess the perimeter of a hidden rectangle. The number of available queries in astonishingly small and one has to come up with a way to find the perimeter without really identifying the rectangle. Initially [cip999](/profile/cip999 "Master cip999") had proposed it with $7$ queries, then [dario2994](/profile/dario2994 "International Grandmaster dario2994"), after failing to solve it for a couple of days, came up with the $4$ queries solution. 41 42 In problem [1552I - Organizing a Music Festival](/contest/1552/problem/I "Codeforces Global Round 15") you have to count the number of permutations with certain sets of values which are contiguous. The statement is very simple but the solution is a bit of a mess to find and also to code. This is the only problem of the problemset whose implementation is involved. It entered in the problemset when we noticed that the previous problem I could be solved by a dull heuristic (which made [cip999](/profile/cip999 "Master cip999") really sad). The first version of the problem had $n=20$, it was a problem E/F and could be solved by subsets-dp, but [antontrygubO_o](/profile/antontrygubO_o "International Grandmaster antontrygubO_o") said (and rightly so) "I am afraid this is too standard". This rejection pushed [dario2994](/profile/dario2994 "International Grandmaster dario2994") to solve the problem in polynomial time and send it back to [antontrygubO_o](/profile/antontrygubO_o "International Grandmaster antontrygubO_o"), who finally accepted it. The official solution can handle also $n=1000, \, k=1000$, but, since it was only a bigger pain to code, we decided to give the "small constraints" version. Sadly, it turns out that the problem was not new for some participants (but there were also some genuine solutions to the problem during the round). 43 44 **Which author did what?** 45 46 * A: Original statement by [cip999](/profile/cip999 "Master cip999"), current statement by [dario2994](/profile/dario2994 "International Grandmaster dario2994"). Prepared by [cip999](/profile/cip999 "Master cip999"). 47 * B: Original statement and preparation by [dario2994](/profile/dario2994 "International Grandmaster dario2994"). 48 * C: Original statement by [cip999](/profile/cip999 "Master cip999"), current statement by [dario2994](/profile/dario2994 "International Grandmaster dario2994"). Prepared by [cip999](/profile/cip999 "Master cip999"). 49 * D: Original statement and preparation by [cip999](/profile/cip999 "Master cip999"). 50 * E: Original statement by [cip999](/profile/cip999 "Master cip999"), current statement by [dario2994](/profile/dario2994 "International Grandmaster dario2994"). Prepared by [cip999](/profile/cip999 "Master cip999"). 51 * F: Original statement by [cip999](/profile/cip999 "Master cip999"), current statement by [dario2994](/profile/dario2994 "International Grandmaster dario2994"). Prepared by [dario2994](/profile/dario2994 "International Grandmaster dario2994"). 52 * G: Original statement by [cip999](/profile/cip999 "Master cip999"), solution by [dario2994](/profile/dario2994 "International Grandmaster dario2994"). Prepared by [dario2994](/profile/dario2994 "International Grandmaster dario2994"). 53 * H: Original statement by [cip999](/profile/cip999 "Master cip999"), solution by [dario2994](/profile/dario2994 "International Grandmaster dario2994"). Prepared by [dario2994](/profile/dario2994 "International Grandmaster dario2994"). 54 * I: Original statement and preparation by [dario2994](/profile/dario2994 "International Grandmaster dario2994"). 55 56 **Some thoughts from cip999** 57 58 This was the first round ever that I (co-)organized, so I'm eager to share some of my experience with the Codeforces community! 59 60 During the problemsetting phase of the preparation I've been the main proposer, basically for two reasons: 61 62 * [dario2994](/profile/dario2994 "International Grandmaster dario2994") didn't have much time to think about problems; 63 * I was totally new to problemsetting and felt the need to propose every problem I came up with, no matter how horrible it was. (Regarding the second point, I believe I am going to write a separate blog post, where I will comment on the negative aspects of some of the ugliest problems I proposed, so that, hopefully, future problemsetters won't repeat my mistakes.) 64 65 As a result, most of the problems ended up being mine, at least in their original formulation (with most of their optimal solutions being [dario2994](/profile/dario2994 "International Grandmaster dario2994")'s). 66 67 However, the more problems I proposed (and the more feedback I received from [dario2994](/profile/dario2994 "International Grandmaster dario2994"), who, during this stage, acted as a coordinator), the better I became at inventing problems: I began to notice when a problem was too mainstream or technical or didn't require any interesting insight; I gradually developed an eye for statements that seemed nice and "natural"; I aimed at the right amount of beauty and originality. I still got rejections, but fewer of them. In the end, I feel that I am now a way better problemsetter than I was in the beginning, and I have to thank [dario2994](/profile/dario2994 "International Grandmaster dario2994") for that! 68 69 The problem preparation phase was another thing entirely. Previously, I had prepared a reasonable amount of problems for the Italian Olympiad in Informatics and the Italian training camps, but in a Codeforces round (and, to a greater extent, in a Global Round) everything must be thought of with the utmost care: there is no room for major mistakes. 70 71 * Statements must be **clear**. As I'm writing this, [dario2994](/profile/dario2994 "International Grandmaster dario2994") is telling me that the statement of problem A has to be clarified (and it's less than 24 hours before the contest!). 72 * The generation of tests is by far the most critical part. If you want to avoid heuristics to pass systems tests (or, maybe worse, pass pretests and get FST), tests must be **strong**. 73 * In order to test the generator, it is essential to write a lot of heuristic/suboptimal/slow solutions and make sure they fail on a reasonable amount of tests. 74 * On the other hand, writing the validator and (when needed) the checker is way easier and almost relaxing. 75 76 Two problems were discarded after or during their preparation because we found unbeatable heuristics: one was the former problem C, the other was former problem I. Both problems were proposed by me, so I was a bit disappointed when that happened (especially for problem I, which neither [dario2994](/profile/dario2994 "International Grandmaster dario2994") nor [antontrygubO_o](/profile/antontrygubO_o "International Grandmaster antontrygubO_o") could solve). However, we were lucky to find those heuristics and save us from unwanted AC on wrong solutions. Hopefully we have caught them all! 77 78 I had a whole lot of fun organizing Global Round 15, and I discovered that I like inventing problems more than solving problems invented by others! For this reason, I think that, sooner or later, I will try to organize another round here on Codeforces (provided that I find the time to do so). 79 80 ## Hints and solutions 81 82 **A** 83 84 **Hint 1.** 85 86 For sure, one must permute the $k$ characters by sorting them alphabetically. 87 88 **Hint 2.** 89 90 If a character is not among the $k$ shuffled characters, then it must be already in the correct position. 91 92 **Hint 3.** 93 94 If a character is not in the correct position, then it must belong to the $k$ shuffled characters. 95 96 **Solution** 97 98 Tutorial is loading... 99 100 **Implementation** 101 102 [123770893](/contest/1552/submission/123770893 "Submission 123770893 by cip999") 103 104 **B** 105 106 **Hints for Solution 1** 107 108 **Hint 1.** 109 110 The "superiority" relationship induces a complete directed graph with $n$ vertices and $\binom{n}{2}$ edges. 111 112 **Hint 2.** 113 114 There can be at most one athlete who is superior to everyone else. 115 116 **Hint 3.** 117 118 Morally, the problem is equivalent to finding the maximum of an array (performing not too many comparisons). 119 120 **Hints for Solution 2** 121 122 **Hint 1.** 123 124 Try to optimize the obvious quadratic solution. 125 126 **Hint 2.** 127 128 Maybe put in some randomization? 129 130 **Solution** 131 132 Tutorial is loading... 133 134 **Implementation of Solution 1** 135 136 [123770963](/contest/1552/submission/123770963 "Submission 123770963 by cip999") 137 138 **Implementation of Solution 2** 139 140 [123770996](/contest/1552/submission/123770996 "Submission 123770996 by cip999") 141 142 **C** 143 144 **Hint 1.** 145 146 If two chords do not intersect, "swapping them" so that they intersect strictly increases the number of intersections. 147 148 **Hint 2.** 149 150 If we repeat the above-described strategy, we will end up with a configuration where all added chords intersect. 151 152 **Hint 3.** 153 154 There is only one configuration so that all added chords intersect. 155 156 **Solution** 157 158 Tutorial is loading... 159 160 **Implementation** 161 162 [123771028](/contest/1552/submission/123771028 "Submission 123771028 by cip999") 163 164 **D** 165 166 **Hint 1.** 167 168 Consider the graph induced by the edges $(j, \, k)$ so that $a_i = b_j - b_k$. 169 170 **Hint 2.** 171 172 Such graph contains $n$ vertices and $n$ edges, so it has a cycle. 173 174 **Hint 3.** 175 176 The sum, with the right signs, of the $a_i$ over the vertices of a cycle is $0$. 177 178 **Hint 4.** 179 180 The above condition is necessary and sufficient. 181 182 **Solution** 183 184 Tutorial is loading... 185 186 **Implementation** 187 188 [123771071](/contest/1552/submission/123771071 "Submission 123771071 by cip999") 189 190 **E** 191 192 **Hints for Solution 1** 193 194 **Hint 1.** 195 196 It is always convenient to choose $a_i, \, b_i$ so that the color $i$ does not appear in $a_i + 1, \, a_i + 2, \, \dots, \, b_i - 1$. So, for each color there are $k - 1$ "candidate intervals". 197 198 **Hint 2.** 199 200 $(k - 1)\left\lceil \frac{n}{k - 1} \right\rceil \ge n$. 201 202 **Hint 3.** 203 204 Choose the intervals in chunks of $\left\lceil \frac{n}{k - 1} \right\rceil$. The intervals in the first chunk should be strictly to the left of the intervals in the second chunk, which should be strictly to the left of the intervals of the third chunk, and so on. 205 206 **Hint 4.** 207 208 For the $t$-th chunk, only consider (among the remaining colors) the candidate intervals whose left endpoint is the $t$-th occurrence of its color. 209 210 **Hints for Solution 2** 211 212 **Hint 1.** 213 214 Try to come up with a greedy algorithm. 215 216 **Hint 2.** 217 218 Order the candidate intervals (defined as above) by second endpoint. 219 220 **Hint 3.** 221 222 Scan the sorted intervals and always select one if you are allowed to. 223 224 **Solution** 225 226 Tutorial is loading... 227 228 **Implementation of Solution 1** 229 230 [123771120](/contest/1552/submission/123771120 "Submission 123771120 by cip999") 231 232 **Implementation of Solution 2** 233 234 [123771150](/contest/1552/submission/123771150 "Submission 123771150 by cip999") 235 236 **F** 237 238 **Hint 1.** 239 240 If you are at position $x$, what can you say on the state of portals with $x_i \lt x$? 241 242 **Hint 2.** 243 244 All such portals must be active. 245 246 **Hint 3.** 247 248 Try to solve the problem under the assumption that initially all portals are active. 249 250 **Hint 4.** 251 252 You must compute the time necessary to go from $x_i$ to $x_i$ again assuming all portals are active. 253 254 **Solution** 255 256 Tutorial is loading... 257 258 **Implementation of Solution 1** 259 260 [123771214](/contest/1552/submission/123771214 "Submission 123771214 by cip999") 261 262 **Implementation of Solution 2** 263 264 [123775629](/contest/1552/submission/123775629 "Submission 123775629 by TheScrasse") 265 266 **G** 267 268 **Hint 1.** 269 270 Testing only arrays with $0$ and $1$ is sufficient (why?). 271 272 **Hint 2.** 273 274 A *quantum array* is a $0$-$1$ array so that some entries can be both $0$ and $1$. Start with a completely undetermined quantum array and apply the algorithm, fixing its values only when necessary. 275 276 **Hint 3.** 277 278 How many quantum arrays will this algorithm have to deal with? 279 280 **Solution** 281 282 Tutorial is loading... 283 284 **Implementation** 285 286 [123771322](/contest/1552/submission/123771322 "Submission 123771322 by cip999") 287 288 **H** 289 290 **Hint 1.** 291 292 The perimeter is twice the base plus twice the height. Figure out them both! 293 294 **Hint 2.** 295 296 Ask a query with all points. The result is a simple expression in terms of base and height. 297 298 **Hint 3.** 299 300 Ask only queries of the form $(di, \, j): 1 \le i \le \lfloor \frac{200}{d} \rfloor, \, 1 \le j \le 200$. Let the result be $f(d)$. 301 302 **Hint 4.** 303 304 For which values of $d$ is $f(d)$ nicely related to $f(1)$? 305 306 **Hint 5.** 307 308 Binary search on the $2$-adic evaluation of the number of points on the base of the rectangle. 309 310 **Solution** 311 312 Tutorial is loading... 313 314 **Implementation** 315 316 [123771375](/contest/1552/submission/123771375 "Submission 123771375 by cip999") 317 318 **I** 319 320 **Hint 1.** 321 322 The valid orderings have a rigid structure. 323 324 **Hint 2.** 325 326 Let $S_i$ be the singers liked by friend $i$. Consider the graph on the friends where there is an edge between $i$ and $j$ if and only if $S_i \cap S_j \ne \varnothing, \, S_i, \, S_j$. 327 328 **Hint 3.** 329 330 Distinct connected components are independent. 331 332 **Hint 4.** 333 334 Up to obvious identifications, each connected component has exactly $0$ or $1$ or $2$ valid orderings. 335 336 **Solution** 337 338 Tutorial is loading... 339 340 **Implementation** 341 342 [123771467](/contest/1552/submission/123771467 "Submission 123771467 by cip999") 343 344 If you find any typo, feel free to tell us with a comment. Moreover, if you want to share your opinion on the problemset, we are eager to read it.