629.md (6747B)
1 Source: https://codeforces.com/blog/entry/43227 2 3 ### [Problem A](//www.codeforces.com/contest/629/problem/A): 4 5 Consider that we have *row**i* chocolates in the *i*'*th* row and *col**i* chocolates in the *i*'*th* column. 6 7 The answer to the problem would be: . It is obvious that every pair would be calculated exactly once (as we have no more than one chocolate in the same square) 8 9 Time Complexity: *O*(*n*2) 10 11 [C++ Solution](http://beepaste.ir/view/056fea5b) 12 13 ### [Problem B](//www.codeforces.com/contest/629/problem/B): 14 15 Consider that we have *boy**i* males in the *i*'*th* day of the year and *girl**i* females in the *i*'*th* day of the year. These arrays can be filled easily when you are reading the input (See the code). Then for the *i*'*th* day of the year, we could have 2 * *min*(*boy**i* , *girl**i*) people which could come to the party. The answer would be maximum of this value between all days *i* (1 ≤ *i* ≤ 366) 16 17 Time Complexity: *O*(366**n*) 18 19 [C++ Solution](http://beepaste.ir/view/8876646e) 20 21 Bonus: Try to solve this problem with *O*(*n*). For each interval given in the input, you don't need to iterate from day *a**i* to day *b**i*. This idea is used to solve problem [276C](//codeforces.com/problemset/problem/276/C). 22 23 ### [Problem C](//www.codeforces.com/contest/629/problem/C): 24 25 This problem can be solved with dynamic programming: 26 27 1. Calculate *dp**i*, *j* : How many sequences of brackets of length *i* has balance *j* and intermediate balance never goes below zero (They form a prefix of a valid sequence of brackets). 28 29 2. For the given sequence of length *n* calculate the resulting balance *a* and the minimum balance *b*. 30 31 3. Try the length of the sequence added at the beginning *c* and its balance *d*. If - *b* ≤ *d* then add *dp**c*, *d* × *dp**m* - *n* - *c*, *d* + *a* to the answer. 32 33 Time complexity: *O*((*n* - *m*)2) 34 35 [C++ Solution](http://beepaste.ir/view/bafe3bd2) 36 37 ### [Problem D](//www.codeforces.com/contest/629/problem/D): 38 39 First of all, we calculate the volume of each cake: *v**i* = π × *h**i* × *r**i*2. 40 41 Now consider the sequence *v*1, *v*2, *v*3, ..., *v**n* : The answer to the problem is the maximum sum of elements between all increasing sub-sequences of this sequence. How do we solve this? First to get rid of the decimals we can define a new sequence *a*1, *a*2, *a*3, ..., *a**n* such that  42 43 We consider *dp**i* as the maximum sum between all the sequences which end with *a**i* and 44 45 *dp**i* =  46 47 The answer to the problem is: π × *max**i* = 1*n**dp*[*i*] 48 49 Now how do we calculate  ? We use a max-segment tree which does these two operations: 1. Change the *i*'*t* member to *v*. 2. Find the maximum value in the interval 1 to *i*. 50 51 Now we use this segment tree for the array *dp* and find the answer. 52 53 Consider that *a*1, *a*2, *a*3, ..., *a**n* is sorted. We define *b**i* as the position of *a**i*. Now to fill *dp**i* we find the maximum in the interval [1, *b**i*) in segment and we call it *x* and we set the *b**i* th index of the segment as *a**i* + *x*. The answer to the problem would the maximum in the segment in the interval [1,n] 54 55 Time complexity: *O*(*nlgn*) 56 57 Thanks to [ATofighi](/profile/ATofighi "Candidate Master ATofighi") who helped a lot for writing the editorial of problem D. 58 59 [C++ Solution](http://beepaste.ir/view/279d0c61) 60 61 ### [Problem E](//www.codeforces.com/contest/629/problem/E): 62 63 First of all, we assume that the tree is rooted! For this problem, first we need to compute some values for each vertex *u*: *qd**u* and *qu**u*, *cnt**u* , *par**u*, *i* and *h**u*. *qd**u* equals to the expected value of length of paths which start from vertex *u*, and ends in *u*’s subtree and also has length at least 1. *qu**u* equals to the expected value of length of paths which start from vertex *u*, and not ends in *u*’s subtree and also has length at least 1. to calculate this values we can use one dfs for *qd*, and one other dfs for *qu*. \ *cnt**u* is the number of vertices in *u*’s subtree except *u*, *par**u*, *i* is the 2*i* ‘th ancestor of *u* and finally *h**u* is the height of the vertex *u*. \ in first dfs (lets call it dfsdown) we can calculate *qd*, *cnt* and *par* array with this formulas: 64 65   66 67 for ecah $v$ as child of *u* and *par**u*, *i* = *par**par**u*, *i* - 1, *i* - 1 68 69 in second dfs (lets call it dfsup) we calculate *qu* using this formula (for clearer formula, I may define some extra variables): 70 71 there are two cases: 72 73 *u* is the only child of its parent: let 74 75  76 77 then 78 79  80 81 \ 82 83 *u* is not the only child of its parent: let 84 85     86 87 then 88 89  90 91 now we should process the queries. For each query *u* and *v*, we have to cases: one of the vertices is either one of the ancestors of the other one or not! In the first case, if we define *w* the vertex before *u* (*u* is assumed to be the vertex with lower height). In the path from *v* to *u*, the answer is 92 93  94 95 . 96 97 In the second case, if we assume *w* = *LCA*(*u*, *v*), then answer is 98 99  100 101 To check if *u* is one of ancestors of *v*, you can check if their *LCA* equals to *u* or you can use dfs to find out their starting and finishing time. *u* is an ancestor of *v* if the interval of starting and finishing time of *v* is completely inside starting and finishing time of *u* 102 103 The time complexity for the whole solution is *O*(*n* + *mlgn*) (*O*(*n*) for dfs and *O*(*lgn*) for each query so *O*(*mlgn*) for queries!). 104 105 [C++ Solution](http://beepaste.ir/view/7ae24ede)