719.md (11012B)
1 Source: https://codeforces.com/blog/entry/47314 2 3 Special thanks to [Seyaua](/profile/Seyaua "International Master Seyaua") for help with translation. 4 5 ## [Div. 2 A — Vitya in the Countryside](//codeforces.com/contest/719/problem/A) 6 7 Idea: [_XuMuk_](/profile/_XuMuk_ "Expert _XuMuk_"). 8 Preparation: [_XuMuk_](/profile/_XuMuk_ "Expert _XuMuk_"). 9 10 There are four cases that should be carefully considered: 11 12 1. *a**n* = 15 — the answer is always DOWN. 13 2. *a**n* = 0 — the answer is always UP. 14 3. If *n* = 1 — the answer is -1. 15 4. If *n* > 1, then if *a**n*–1 > *a**n* — answer is DOWN, else UP. 16 17 **Time Complexity: .** 18 19 ## [Div. 2 B — Anatoly and Cockroaches](//codeforces.com/contest/719/problem/B) 20 21 Idea: [_XuMuk_](/profile/_XuMuk_ "Expert _XuMuk_"). 22 Preparation: [_XuMuk_](/profile/_XuMuk_ "Expert _XuMuk_"). 23 24 We can notice that there are only two possible final coloring of cockroaches that satisfy the problem statement: *rbrbrb*... or *brbrbr*... 25 26 Let’s go through both of these variants. 27 28 In the each case let's count the number of red and black cockroaches which are not standing in their places. Let's denote these numbers as *x* and *y*. Then it is obvious that the *min*(*x*, *y*) pairs of cockroaches need to be swapped and the rest should be repaint. 29 30 In other words, the result for a fixed final coloring is exactly *min*(*x*, *y*) + *max*(*x*, *y*) - *min*(*x*, *y*) = *max*(*x*, *y*). The final answer for the problem is the minimum between the answers for the first and the second colorings. 31 32 **Time Complexity: .** 33 34 ## [Div. 1 A — Efim and Strange Grade](//codeforces.com/contest/718/problem/A) 35 36 Idea: [BigBag](/profile/BigBag "Grandmaster BigBag"). 37 Preparation: [BigBag](/profile/BigBag "Grandmaster BigBag"). 38 39 One can notice that the closer to the decimal point we round our grade the bigger grade we get. Based on this observation we can easily solve the problem with dynamic programming. 40 41 Let *dp**i* be the minimum time required to get a carry to the (*i* - 1)-th position. 42 43 Let's denote our grade as *a*, and let *a**i* be the (*i*)-th digit of the *a*. There are three cases: 44 45 1. If *a**i* ≥ 5, then *dp**i* = 1. 46 2. If *a**i* < 4, then *dp**i* = *inf* (it means, that we cann't get a carry to the (*i* - 1)-th position). 47 3. If *a**i* = 4, then *dp**i* = 1 + *dp**i* + 1. 48 49 After computing *dp*, we need to find the minimum *pos* such that *dp**pos* ≤ *t*. So, after that we know the position where we should round our grade. 50 51 Now we only need to carefully add 1 to the number formed by the prefix that contains *pos* elements of the original grade. 52 53 **Time Complexity: .** 54 55 ## [Div. 1 B — Alyona and Copiers](//codeforces.com/contest/718) 56 57 Idea: [_XuMuk_](/profile/_XuMuk_ "Expert _XuMuk_"). 58 Preparation: [BigBag](/profile/BigBag "Grandmaster BigBag"). 59 60 Deleted 61 62 ## [div. 1 C — Sasha and Array](//codeforces.com/contest/718/problem/C) 63 64 Idea: [BigBag](/profile/BigBag "Grandmaster BigBag"). 65 Preparation: [BigBag](/profile/BigBag "Grandmaster BigBag"). 66 67 Let's denote 68  69 70 Let's recall how we can quickly find *n*-th Fibonacci number. To do this we need to find a matrix product . 71 72 In order to solve our problem let's create the following segments tree: in each leaf which corresponds to the element *i* we will store a vector  and in all other nodes we will store the sums of all the vectors that correspond to a given segment. 73 74 Now, to perform the first request we should multiply all the vectors in a segment [*l*..*r*] by  and to get an answer to the second request we have to find a sum in a segment [*l*..*r*]. 75 76 **Time Complexity: .** 77 78 ## [Div. 1 D — Andrew and Chemistry](//codeforces.com/contest/718/problem/D) 79 80 Idea: [_XuMuk_](/profile/_XuMuk_ "Expert _XuMuk_"). 81 Preparation: [BigBag](/profile/BigBag "Grandmaster BigBag"). 82 83 Let’s first figure out how we can solve the problem in  time. 84 85 Let’s pick a vertex we’re going to add an edge to and make this vertex the root of the tree. For each vertex *v**i* we’re going to assign a label *a*[*v**i*] (some number). The way we assign labels is the following: if the two given vertices have the same subtrees they’re going to get the same labels, but if the subtrees are different then the labels for these vertices are going to be different as well. 86 87 We can do such labeling in a following way: let’s create a `map<vector<int>, int> m` (the maximum degree for a vertex is 4, but let’s assume that the length of the vector is always equal to 4). Let `m[{x, y, z, w}]` be a label for a vertex which has children with the labels *x*, *y*, *z*, *w*. Let’s note that the vector {*x*, *y*, *z*, *w*} should be sorted to avoid duplications, also if the number of children is less than 4 then we’ll store - 1’s for the missing children (to make the length of a vector always equal to 4). Let’s understand how we can compute the value for the label for the vertex *v*. Let’s recursively compute the labels for its children: *v*1, *v*2, *v*3, *v*4. 88 Now, if `m.count({a[v1], a[v2], a[v3], a[v4]})` then we use the corresponding value. Otherwise, we use the first unused number: `m[{a[v1], a[v2], a[v3], a[v4]}]=cnt++`. 89 90 Now, let’s pick another vertex which we’re going to add an edge to. Again, let’s make it the root of the tree and set the labels without zeroing out our counter *cnt*. Now, let’s do the same operation for all the other possible roots (vertices, *n* times). Now, one can see that if the two roots have the same labels, then the trees which can be obtained by adding an edge to these roots, are exactly the same. Thus, we only need to count the amount of roots with different labels. Also, we should keep in mind that if a degree for a vertex is already 4 it’s impossible to add an edge to it. 91 92 The solution described above has the time complexity , because we consider *n* rooted trees and in the each tree we iterate through all the vertices (*n*), but each label update takes . 93 94 Let’s speed up this solution to . 95 96 Let *b* be an array where *b*[*v**i*] is a label in a vertex *v**i* if we make this vertex the root of the tree. Then the answer to the problem is the number of different numbers in the array *b*. Let’s root the tree in a vertex *root* and compute the values *a*[*v**i*]. Then *b*[*root*] = *a*[*root*] and all the other values for *b*[*v**i*] we can get by pushing the information from the top of the tree to the bottom. 97 98 **Time complexity: .** 99 100 ## [Div. 1 E — Matvey's Birthday](//codeforces.com/contest/718/problem/E) 101 102 Idea: [BigBag](/profile/BigBag "Grandmaster BigBag"). 103 Preparation: [BigBag](/profile/BigBag "Grandmaster BigBag"), [GlebsHP](/profile/GlebsHP "Grandmaster GlebsHP"). 104 105 Let’s prove that the distance between any two vertices is no more than *MaxDist* = 2·*sigma* - 1, where *sigma* is the size of the alphabet. Let’s consider one of the shortest paths from the position *i* to the position *j*. One can see that in this path each letter *ch* occurs no more than two times (otherwise you could have skipped the third occurrence by jumping from the first occurrence to the last which gives us a shorter path). Thus, the total amount of letters in the path is no more than 2·*sigma* which means that the length of the path is no more than 2·*sigma* - 1. 106 107 Let *dist**i*, *c* be the distance from the position *i* to some position *j* where *s**j* = *c*. These numbers can be obtained from simulating bfs for each letter *c*. We can simulate bfs in *O*(*n*·*sigma*2) (let’s leave this as an exercise to the reader). 108 109 Let *dist*(*i*, *j*) be the distance between positions *i* and *j*. Let’s figure out how we can find *dist*(*i*, *j*) using precomputed values *dist**i*, *c*. 110 111 There are two different cases: 112 113 1. The optimal path goes through the edges of the first type only. In this case the distance is equal to . 114 2. The optimal path has at least one edge of the second type. We can assume that it was a jump between two letters *c*. Then, in this case the distance is *dist**i*, *c* + 1 + *dist**c*, *j*. 115 116 Adding these two cases up we get: . 117 118 Let’s iterate over the possible values for the first position *i* = 1..*n*. Let’s compute the distance for all such *j*, where  by the above formula. 119 120 Now, for a given *i* we have to find *max*(*dist*(*i*, *j*)) for . In this case *dist*(*i*, *j*) = *min*(*dist**i*, *c* + 1 + *dist**c*, *j*). 121 122 Let’s compute one additional number *dist**c*1, *c*2 — the minimal distance between positions *i* and *j* where *s**i* = *c*1 and *s**j* = *c*2. This can be easily done using *dist**i*, *c*. 123 124 One can notice that *dist**s**j*, *c* ≤ *dist**j*, *c* ≤ *dist**s**j*, *c* + 1. It means that for every position *j* we can compute a mask *mask**j* with *sigma* bits where *i*-th bit is equal to *dist**j*, *c* - *dist**s**j*, *c*. Thus, we can compute the distance using only *s**j* and *mask**j*. 125 I.e. now *dist**j*, *c* = *dist**s**j*, *c* + *mask**j*, *c*. 126 127 Let *cnt* be an array where *cnt**c*, *mask* is the number of such *j* where , *s**j* = *c* and *mask**j* = *mask*. Now, instead of iterating over *j* for a given *i* we can iterate over (*c*, *mask*) and if *cnt**c*, *mask* ≠ 0 we’ll be updating the answer. 128 129 **Time complexity: .**