720.md (8805B)
1 Source: https://codeforces.com/blog/entry/47183 2 3 Hi, everyone! 4 5 Russian Code Cup 2016 is over, the problems for the Final Round were more difficult than usually, but the participants didn't give up. The champion is Gennady Korotkevich [tourist](/profile/tourist "Legendary Grandmaster tourist"), the second place winner is Vladislav Epifanov [vepifanov](/profile/vepifanov "Legendary Grandmaster vepifanov"), the third place winner is Nikolay Kalinin [KAN](/profile/KAN "International Grandmaster KAN"). Congratulations to the winners, the complete results are at the RCC web site <http://russiancodecup.ru> 6 7 Before proceeding to the tutorial, we would like to thank [Mail.Ru Group](https://corp.mail.ru/) for organizing the tournament and providing the prizes, and the judges from [ITMO University](http://www.ifmo.ru) for problems. Chief judge Andrew Stankevich [andrewzta](/profile/andrewzta "Grandmaster andrewzta"), judges Vitaly Aksenov [Aksenov239](/profile/Aksenov239 "Master Aksenov239"), Nikolay Budin [budalnik](/profile/budalnik "International Master budalnik"), Dmitry Filippov [DimaPhil](/profile/DimaPhil "Candidate Master DimaPhil"), Borys Minaiev [qwerty787788](/profile/qwerty787788 "Grandmaster qwerty787788"), Ilya Peresadin [pva701](/profile/pva701 "Candidate Master pva701"), Grigory Shovkoplyas [GShark](/profile/GShark "Expert GShark"), Artem Vasiliev [VArtem](/profile/VArtem "International Grandmaster VArtem"), Nikolay Vedernikov [VedernikovNV](/profile/VedernikovNV "Master VedernikovNV"), Ilya Zban [izban](/profile/izban "Grandmaster izban"). 8 9 And now the short tutorial. To get more details, you can read the programs of the judges solutions, published at the official site <http://russiancodecup.ru> together with the official tests. 10 11 A. Closing ceremony 12 13 Probably the easiest way to solve the problem is greedy. Sort people from the first line by increasing of their stamina. Give them tickets in this order, each time using the place which is furthest away from the other line. After that try to assign people from the second line to the remaining seats by sorting people by stamina and seats by the distance. 14 15 The time complexity of your solution must not exceed *O*((*nm*)2), however using std::set one can get a solution with complexity of *O*(*nm* *log*(*nm*)). 16 17 B. Cactusophobia 18 19 Let us divide the graph to biconnected blocks. Each block is either a bridge, or a cycle. Our goal is to remove one edge from each cycle, so that the number of remaining colors were maximum possible. 20 21 Let us build a bipartite graph, one part would be blocks, another one would be colors. For each block put an edge of capacity 1 for each color of an edge in this block (make multiple edges, or bigger capacity if there are several edges of some color). Add two vertices: source and sink, add edges from source to blocks, if the block is a cycle of length *l*, set its capacity to *l* - 1, if it is a bridge, set its capacity to 1. Add edges from color vertices to the sink of capacity 1. 22 23 It is quite clear that size of the maximum flow in this graph is indeed the answer to the problem. 24 25 As a final note, the judges know the solution that runs in *O*(*n*) and requires no maximum flow algorithms, challenge yourself to come up with it! 26 27 C. Homework 28 29 The solution is constructive. 30 31 * First let us use backtracking to find solutions for all *n*, *m* < 5, it is also better to precalculate all answers, in order not to mess with non-asymptotic optimizations. 32 * Now *m* ≥ 5. 33 * Let us put asterisks from left to right, one row after another. When adding the new asterisk, we add 4 new L-trominoes, except the first asterisk in a row that adds 1 new L-tromino, and the last asterisk in a row adds 3 new L-trominoes. Let us stop when the number of remaining L-trominoes *k* is less than 4, or there are less than 5 free squares in the table. 34 * Now there are two cases 35 + there is a free row 36 + thee is no free row 37 * If there is a free row, we stopped because *k* is now less then 4. So: 38 + k = 0: the solution is found 39 + k = 1: if there are already at least 2 asterisks in the current row, put the asterisk in the beginning of the next row, if there is only 1, put it in the end of the current row 40 + k = 2, k = 3 — similar, left as an exercise. 41 * If there are now free rows left, one can see that you can only add *k* from the set {0, 1, 2, 3, 4, 5, 6, 8, 9, 12, 15} L-trominoes. 42 * And finally there is also the special case where the size of the board is 3 × *m*, *m* ≥ 5 and *k* = 2 * (*m* - 1) - 8 — in this case the first column should be left empty, and the rest of the board must be completely filled with asterisks. 43 44 D. Slalom 45 46 First let us consider all paths from the starting square to the finish one. Let us say that two paths are equivalent, if each obstacle is at the same side for both paths. For each class of equivalence let us choose the representative path — the one that tries to go as low as possible, lexicographically minimum. 47 48 Let us use dynamic programming. For each square let us count the number of representative paths that go from the starting square to this one. When the obstacle starts, some paths can now separate. The new representatives will pass this obstacle from above (it will be to the right of them). So we add the sum of values for squares below it, but above any other lower obstacle, to the value for the square right above the obstacle. 49 50 To overcome the time and memory limits that the naive solution with *O*(*nm*) memory and *O*(*nm*2) time complexity, we use segment tree for range sum queries with mass update, running scanline and events "start of an obstacle", "end of an obstacle". This leads to the solution with *O*(*m*) memory and *O*(*n* *log* *m*) time complexity. 51 52 E. Cipher 53 54 First let us consider a slow solution. Let us find a condition for each number *k* after what number of seconds Borya can distinguish it from the given number. Let us look at their initial encoding. Increase both numbers by 1 until the encodings are different (or one of the numbers needs more than *n* digits to represent in which case the beep allows Borya to distinguish the numbers as well). 55 56 Now there are two main ideas that allow us to get a better solution. First, we don't have to check all numbers. We only need to check numbers that differ from the given number in exactly one digit. 57 58 Second: to get the time when the numbers can be distinguished we don't need to iterate over all possible values. We just need to try all digit positions and all values for that position, and check only moments when the digit at the position will first have this value in one of the numbers. 59 60 So the complexity is now polynomial in *n* and since *n* ≤ 18, it easily fits into the time limit. 61 62 F. Array Covering 63 64 We give the outline of the solution, leaving technical details as an excercise. 65 66 First note that the answer will always use *min*(*k* - *n*, 0) subarrays with maximal sums. Sof let us find the sum of *min*(*k* - *n*, 0) maximal subarrays, elements that are used in them, and the following *min*(*k*, *n*) subarrays. We can do it using binary search for the border sum, and a data structure similar to Fenwick tree. For the given value of the sum this tree must provide the number of subarrays with greater or equal sum, sum of their sums, and the set of the elements of these subarrays. It should also allow to list all these subarrays in linear time complexity. This part has time complexity *O*(*n* *log*2 *n*). 67 68 Let us now describe how to solve the problem in *O*(*n*2 *log* *n*). Let us try all values of *x* — the number of subarrays with maximum sums that we will use in our solution (there are *O*(*n*) variants, because top *min*(*k* - *n*, 0) subarrays will definitely be used). Let elements with indices *i*1, ..., *i**m* be the ones that are not used in these subarrays. Now we must add *k* - *x* segments that would contain all of these elements. Note that each of these *k* - *x* segments must contain at least one of these elements, and no two segments can have a common element among them (in the other case the solution is not optimal). These observations let us greedily choose these *k* - *x* segments in *O*(*n* *log* *n*) and the final solution complexity is *O*(*n*2 *log* *n*) 69 70 To optimize this solution, we keep segments [*i**j* + 1; *i**j* + 1 - 1] in the ordered set. When we iterate over *x* and increase its value, we remove some of the *i**j*-s, and recalculate the required values for the affected segments. After that we must take *k* - *x* maximal values from the set, so since there are *O*(*n*) changes in total, this part now works in *O*(*n* *log* *n*).