659.md (8041B)
1 Source: https://codeforces.com/blog/entry/44093 2 3 [659A — Round House](//codeforces.com/contest/659/problem/A) 4 5 The answer for the problem is calculated with a formula ((*a* - 1 + *b*)  *n* + *n*)  *n* + 1. 6 7 Such solution has complexity *O*(1). 8 9 There is also a solution with iterations, modelling every of |*b*|'s Vasya's moves by one entrance one by one in desired direction, allowed to pass all the tests. 10 11 This solution's complexity is *O*(|*b*|). 12 13 [659B — Qualifying Contest](//codeforces.com/contest/659/problem/B) 14 15 Let's consider the participants from every region separately. So for every region we just need to sort all of its participants by their score in non-increasing order. The answer for a region is inconsistent if and only if the score of the second and the third participant in this order are equal, otherwise the answer is the first and the second participant in this order. 16 17 The solution complexity is . 18 19 [659C — Tanya and Toys](//codeforces.com/contest/659/problem/C) 20 21 Our task is to take largest amount of toys Tanya doesn't have yet the way the sum of their costs doesn't exceed *m*. To do that one can perform greedy algorithm: let's buy the cheepest toy Tanya doesn't have at every step, while the amount of money left are sufficient to do that. The boolean array *used* can be a handle in that, storing *true* values in indices equal to toy types which Tanya does have at the moment. As soon as 109 money is sufficient to buy no more than 105 toys , *used* is enough to be sized 2 × 105 (we won't buy the toys with types numbered greater). So we just need to iterate over the number of type we want to buy, and if corresponding value in *used* is equal to *false*, we should buy it, otherwise we can't. 22 23 The solution complexity is . 24 25 One can use the <> data structure (C++ \texttt{std::set}, for example), for storing the types Tanya has at the moment. In this case the complexity is . 26 27 [659D — Bicycle Race](//codeforces.com/contest/659/problem/D) 28 29 From the track description follows that Maria moves the way that the water always located to the right from her, so she could fall into the water only while turning left. To check if the turn is to the left, let's give every Maria's moves directions a number: moving to the north — 0, moving to the west — 1, to the south — 2 and to the east — 3. Then the turn is to the left if and only if the number of direction after performing a turn *dir* is equal to the number before performing a turn *oldDir* plus one modulo 4 . 30 31 This solution has complexity *O*(*n*). 32 33 One can solve this problem in alternative way. Let the answer be equal to *x* (that means that the number of inner corners of 270 degrees equals *x*, but the number of inner corners of 90 degrees to *n* - *x*). As soon as the sum of the inner corners' values of polygon of *n* vertices is equal to 180 × (*n* - 2), then *x* × 270 + (*n* - *x*) × 90 equals to 180 × (*n* - 2). This leads us to , being the answer for the problem calculated in *O*(1). 34 35 [659E — New Reform](//codeforces.com/contest/659/problem/E) 36 37 One should notice, that for every connected component of the graph the problem could be solved independently, so we just need to solve the problem for any connected graph. 38 39 Let this connected graph (of *n* vertices) contain *n* - 1 edge (such is called a tree). If one maintain a DFS from any of its vertex, every edge will be oriented, and each of them could given to its ending vertex, this way every vertex (except the one we launched DFS from, that is the root) will be satisfied by an edge. In this case the answer is equal to 1. 40 41 Let's then deal with a case when the graph contains more than *n* - 1 edges. This graph contains at least one cycle. Let's take arbitrary vertex from any of the cycles and launch a DFS (as above) from it. All vertices except chosen will be satisfied, so we are to give an edge to the chosen vertex. As soon as chosen vertex belongs to a cycle, at least one of its edge will not be taken to account in the DFS, so it can be given to a root. This way all the vertices will be satisfied. 42 43 Now we are able to solve the task for any connected graph, so we are to divide the graph into a connected components — this can be easily done by DFS or BFS. 44 45 The solution complexity is *O*(*n* + *m*). 46 47 [659F — Polycarp and Hay](//codeforces.com/contest/659/problem/F) 48 49 In this task one should find a connected area, in which the product of the minimum value of the cells and the number of the cells is equal to *k*. To find such, let's sort all the *n* × *m* cells by their values by non-increasing order. Then we will consecutively add them in this order one by one, maintaining a connected components on their neighbouring relations graph. It's enough to use Disjoint Set Union structure to do so, storing additionally size of every component. 50 51 Let *a**i*, *j* be the last added element in some component *id*, so *a**i*, *j* has the minimum value among all the cells in component *id* (according to our ordering). If *a**i*, *j* does not divide *k*, then the component *id* could not consist of desired area. Otherwise (*a**i*, *j* is divisor of *k*), let's find *need* = *k* / *a**i*, *j* — desired area size (if it contains *a**i*, *j*), and if *CNT**id* is not less than *need*, then the component *id* contains desired area, which could be easily found by launching a DFS in a neighbouring relation graph from *a**i*, *j*, visiting only the *a**p*, *q* ≥ *a**i*, *j* and exactly *need* of them. 52 53 The solution complexity is . 54 55 [659G — Fence Divercity](//codeforces.com/contest/659/problem/G) 56 57 Let the answer for the problem be the sum 58 59  60 61 where *calc*(*l*, *r*) is the number of ways to cut the top part of the fence the way its leftmost part is in position *l* and the rightmost in position *r*. If *l* = *r*, that is the case when the cutted top part consists of part of only one board, then *calc*(*l*, *r*) = *h**l* - 1. 62 63 Let *r* > *l*, then 64 65  66 67 In other words, the number of ways to cut the top part of some board is equal to minimum value among heights of it and its neighbours minus one, otherwise the cutted part will be inconsistent. Leftmost board and rightmost board are considered separately, because each of them does have only one neighbouring board. So the answer looks like 68 69  70 71 The first summand is easy to calculate, so let's take a look at the second. Let us modify it as the following: 72 73  74 75 Let 76 77  78 79 Let's take a look how does the *S*(*r*) change after increasing *r* by one: 80 81 *S*(*r* + 1) = *S*(*r*) × *min*(*h**r* - 1 - 1, *h**r* - 1, *h**r* + 1 - 1) + *min*(*h**r* - 1, *h**r* + 1 - 1). 82 83 This way this sum is easy to maintain if consecutively increase *r* from 2 to *n*. 84 85 The solution complexity is *O*(*n*).