codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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.