167.md (7689B)
1 Source: https://codeforces.com/blog/entry/4214 2 3 I am sorry for mistakes in English and I will be glad if you tell me about them. 4 5 #### [168A - Wizards and Demonstration](/contest/168/problem/A "Codeforces Round 114 (Div. 2)") Аuthor [PavelKunyavskiy](/profile/PavelKunyavskiy "Grandmaster PavelKunyavskiy"). 6 7 In this task, it was necessary to write exactly what has been described in statement. In particular, it was necessary to have  people, who come to the meeting. For this it was necessary to create  clones. 8 9 #### [168B - Wizards and Minimal Spell](/contest/168/problem/B "Codeforces Round 114 (Div. 2)") Аuthor [PavelKunyavskiy](/profile/PavelKunyavskiy "Grandmaster PavelKunyavskiy"). 10 11 In this problem you had to write exactly what has been described in statment too. Read lines one by one. Also keep the last block of lines that are not amplyfying. If the next line is amplyfying (which can be checked by linear search), we print the last block, if any, and the line itself. Otherwise, remove all spaces from the string and add to the last block. It only remains to distinguish between an empty block and a block of empty lines. 12 13 #### [167A - Wizards and Trolleybuses](/contest/167/problem/A "Codeforces Round 114 (Div. 1)") Аuthor [Alex-Gran](/profile/Alex-Gran "Expert Alex-Gran"). 14 15 This was the first problem where you had a little bit away from translating statements to a programming language. Because acceleration trolleybuses are all the same and they can slow down immediately, the answer for the next trolleybus is the maximum of the time when it would come if it were not to stop when he reach the rest trolleybuses which was traveling in front of him and the arrival time of the previous trolleybus. 16 17 It remains only to calculate the arrival time of each trolleybus if ignore others. Here, the easiest way to analyze two cases. If , then trolley should accelerate as long as it can and the answer is equal to . Otherwise the trolley should accelerate all the time and the answer is equal to . 18 19 #### [167B - Wizards and Huge Prize](/contest/167/problem/B "Codeforces Round 114 (Div. 1)") Author [PavelKunyavskiy](/profile/PavelKunyavskiy "Grandmaster PavelKunyavskiy"). 20 21 This problem can be solved using dynamic programming. 22 23 Let d[i][j][m] — the probability we won j of first i days and get bags total capacity of m. For convenience, we assume that the bag is also a prize and the prize is a bag of capacity 0. To do that, retaining a task we must add 1 to all a[i]. Then from d[i][j][m] we can go to the d[i+1][j+1][m+a[i]] with probability p[i]/100, and to d[i+1][j][m] with probability 1-p[i]/100. The answer will be the sum of d[n+1][j][m] for all j,m such that *L* ≤ *j* ≤ *m* + *k*. This solution works for 2004, and do not fit into the time limit. 24 25 It remains to note that if we have over 200 places for prizes, it does not matter how many exactly. So we need to calculate states with *m* ≤ 200 and now solution works for 2003. 26 27 #### [167C - Wizards and Numbers](/contest/167/problem/C "Codeforces Round 114 (Div. 1)") Author [Alex-Gran](/profile/Alex-Gran "Expert Alex-Gran"). 28 29 Consider the position (a, b). Let a < b. From this there is a move to . Recursively check if this position is a winning or a losing. If it is losing, then (a, b) exactly winning. Otherwise, no one will take the remainder. So everyone will subtract from larger number nonnegative degree of smaller. Then the left to learn to solve such problem. You can subtract the nonnegative powers of a from x, and player who cannot move losses. And solve it for . This problem can be solved as follows. If a is odd, then all odd number are wining. In other all the numbers, giving an odd residue modulo a+1 or -1 residue on the same module are wining. This can be easily proved by induction. 30 31 #### [167D - Wizards and Roads](/contest/167/problem/D "Codeforces Round 114 (Div. 1)") Author [PavelKunyavskiy](/profile/PavelKunyavskiy "Grandmaster PavelKunyavskiy"). 32 33 This was the first really hard problem in the contest. One of the challenges was to understand the statement. I hope that we had written the statement as clear as it possible in this problem. 34 35 Consider this graph. In particular, we consider more closely the point with the largest y. 36 37 1) It is connected with the highest points on the left and right of it. 38 39 2) It is not connected to all other points. 40 41 3) It is inside all corners on points from different sides of it. 42 43 All three of these properties are seen quite clearly in the pictures. 44 45 So, 46 47 1) Building roads on the left and right sides are independent. 48 49 2) The graph is a tree. 50 51 Once a graph is a tree, the maximum matching in it can be found greedy, or with a simple dynamic. But it works in linear time, which clearly is not enough to answer all of 105 queries. 52 53 But this is not just a tree! Those who know what it is probably already noticed, that it is Cartesian tree (also known as treep). This allows to get a tree for the subsegments in time which is *O*(*h*), counting all the necessary dynamics, where h is the height of the tree. 54 55 Well, since the city built at random points (the method for the construction of cities guarantees this), the height of the tree *h* = *O*(*K* + *logN*). 56 57 #### [167E - Wizards and Bets](/contest/167/problem/E "Codeforces Round 114 (Div. 1)") Author [Dmitry_Egorov](/profile/Dmitry_Egorov "International Master Dmitry_Egorov"). 58 59 This task was about the pathes from the sources to sinks. For this pathes there was a condition which made them dependent — they should not interfere at vertexes. But in any combinatorics is much easier when everything is independent. So we should try to get rid of the condition of the absence of crossings at the vertices. It is very easy — just forget about it. Lets understand why the answer will not change: Suppose that a certain set of ways in which the two paths intersect. We show that taking into account this way, we at the same time take into account an another with the opposite sign. To do this, change the endings for paths that intersect. The signum of the permutation in this case has changed, so this set of paths is taken into account with the opposite sign and their sum is 0. 60 61 How can it helps us? If we fix the permutation, the number of sets of paths that it corresponds well to the product of the number of paths for each pair of corresponding source and sink. 62 63 Suppose that from the i-th source in the j-th sink there are *cnt**ij* paths. This value can be calculated by depth-first-search and simple dynamic. 64 65 Then the answer is 66 67  68 69 . This value is called the determinant of matrix cnt, which can be calculated using Gauss method in *O*(*S*3) time where S is the number of sinks and sources. 70 71 And we had to remember about isolated vertexes. Deleting one of them either do not change the answer or multiply the answer by -1. 72 73 It remains to see that after deleting all isolated vertexes , and 3003 fine fits into TL.