671.md (15253B)
1 Source: https://codeforces.com/blog/entry/44821 2 3 ### [672A - Summer Camp](/contest/672/problem/A "Codeforces Round 352 (Div. 2)") 4 5 This one is a simple brute force problem, we will construct our array. Adding numbers between 1 and 370 will be enough. After construction we just have to print *n*-th element of array. 6 7 ### [672B - Different is Good](/contest/672/problem/B "Codeforces Round 352 (Div. 2)") 8 9 We observe that in a good string all letters must be different, because all substrings in size 1 must be different. So if size of string is greater than 26 then answer must be - 1 since we only have 26 different letters. 10 11 Otherwise, Let's suppose we have *k* different letters in string sized *n*, in our string *k* elements must be stay as before, all others must be changed. So will be (*n* — *k*). Here is the [code](https://ideone.com/NJw7V2). 12 13 ### [671A - Recycling Bottles](/contest/671/problem/A "Codeforces Round 352 (Div. 1)") 14 15 Let's solve the problem when Adil and Bera in the same coordinate with bin. Then answer will be , let's say *T* to this value. If Adil will take *i*-th bottle and Bera will take *j*-th bottle (*i* ≠ *j*), then answer will be *T* + *distance*(*Adil*, *Bottle**i*) - *distance*(*Bin*, *Bottle**i*) + *distance*(*Bera*, *Bottle**j*) - *distance*(*Bin*, *Bottle**j*). 16 17 Because for all bottles but the chosen ones we have to add 2 * *distance*(*bottle*, *bin*). 18 19 For example if we choose a bottle *i* for Adil to take first then we have to add *distance*(*Adil*, *Bottle**i*) + *distance*(*Bottle**i*, *Bin*). 20 21 In defined *T* we already count 2 * *distance*(*Bottle**i*, *Bin*) but we have to count *distance*(*Adil*, *Bottle**i*) + *distance*(*Bottle**i*, *Bin*) for *i*. 22 23 So we have to add *distance*(*Adil*, *Bottle**i*)-*distance*(*Bottle**i*, *Bin*) to *T*. 24 25 Because 2 * *distance*(*Bin*, *Bottle**i*)+*distance*(*Adil*, *Bottle**i*)-*distance*(*Bin*, *Bottle**i*) is equal to *distance*(*Adil*, *Bottle**i*)+*distance*(*Bottle**i*, *Bin*). 26 27 Lets construct two arrays, *a**i* will be *distance*(*Adil*, *Bottle**i*) - *distance*(*Bin*, *Bottle**i*), and *b**j* will be *distance*(*Bera*, *Bottle**j*) - *distance*(*Bin*, *Bottle**j*). 28 29 We will choose *i* naively, after that we have to find minimum *b**j* where *j* is not equal to *i*. This one easily be calculated with precalculations, let's find optimal *opt*1 for Bera, also we will find second optimal *opt*2 for Bera, if our chosen *i* is equal to *opt*1 then Bera will go *opt*2, otherwise he will go *opt*1. 30 31 Don't forget to cases that all bottles taken by Adil or Bera! 32 33 Here is the [code](https://ideone.com/Qs5ItS). 34 35 ### [671B - Robin Hood](/contest/671/problem/B "Codeforces Round 352 (Div. 1)") 36 37 We observe that we can apply operations separately this means first we will apply all increase operations, and after will apply all decrease operations, vice versa. We will use following algorithm. 38 39 We have to apply following operation *k* times, add one to minimum number in array. We will simply binary search over minimum value after applying k operation. Let's look how to check if minimum will be great or equal to *p*. If  is less or equal to *k* then we can increase all elements to at least *p*. In this way we can find what will be minimum value after *k* operations. 40 41 Let's say this minimum value to *m*. After we find it we will increase all numbers less than *m* to *m*. But there may be some operations we still didn't apply yet, this number can be at most *n* - 1, otherwise minimum would be greater than *m* because we can increase all numbers equal to *m* by one with this number of increases. Since minimum has to be same we just have to increase some elements in our array that equal to *m*. 42 43 We will use same algorithm for decreasing operations. Finally we will print *max* *element* — *min* *element* in final array. Overall complexity will be *O*(*nlogk*). 44 45 Here is the [code](https://ideone.com/cc3KO5). 46 47 Solution with another approach [code](https://ideone.com/WT1j4B). 48 49 ### [671C - Ultimate Weirdness of an Array](/contest/671/problem/C "Codeforces Round 352 (Div. 1)") 50 51 If we calculate an array *H* where *H**i* is how many (*l* - *r*)s there are that *f*(*l*, *r*) ≤ *i*, then we can easily calculate the answer. 52 53 How to calculate array *H*. Let's keep a vector, *v**i* keeps all elements indexes which contain *i* as a divisor — in sorted order. We will iterate over *max* *element* to 1. When we are iterating we will keep another array *next*, Let's suppose we are iterating over *i*, *next**j* will keep leftmost *k* where *f*(*j*, *k*) ≤ *i*. Sometimes there is no such *k*, then *next**j* will be *n* + 1. *H**i* will be equal to , because if we choose p as *l*, *r* must be at least *next**p*, so for *l* we can choose *n*-*next**p*+1 different *r* s. 54 55 Let's look how we update *next* array when we iterate *i* to *i* - 1. 56 57 Let *v**i* be *b*1, *b*2, *b*3...*b**k*. Note that our *l* - *r* must be cover at least *k* - 1 of this indexes. *l* must less or equal to *b*2. So we have to maximize all *next**p* with *n* + 1 where *p* > *b*2. Otherwise If *l* ≥ *b*1 + 1 then *r* must be at least *b**k*, that's we will maximize all *next**p*'s where *b*1 < *p* ≤ *b*2 with *b**k*. And finally for all *next**p*'s where (1 ≤ *p* ≤ *b*1) we have to maximize them with *b**k* - 1. Observe that *next* array will be monotonic - in non decreasing order - after all operations. So we can easily make our updates with a segment tree that can perform following operations: 58 59 - Returns rightmost index *i* where *next**i* is less than some *k*. 60 61 - Returns sum of all elements in *next* array. 62 63 - Can assign some *k* to all elements between some *l* and *r*. 64 65 If all update and queries performed in *O*(*logn*) then overall complexity will be *O*(*nlogn*), we can also apply all this operations with STL set in same complexity. 66 67 Code with set structure: [link](https://ideone.com/QhwMPF) 68 69 Code with segment tree: [link](https://ideone.com/MyQfZz) 70 71 ### [671D - Roads in Yusland](/contest/671/problem/D "Codeforces Round 352 (Div. 1)") 72 73 I want to thank [GlebsHP](/profile/GlebsHP "Grandmaster GlebsHP"), i originally came up with another problem similar to it, [GlebsHP](/profile/GlebsHP "Grandmaster GlebsHP") suggested to use this one in stead of it. 74 75 Let's look for a optimal subset of paths, paths may intersect. To prevent from this let's change the problem litte bit. A worker can repair all nodes between *u**i* and some *k*, where *k* is in the path between *u**i* and *v**i* with cost *c**i*, also paths must not intersect. In this way we will never find better solution from original problem and we can express optimal subset in original problem without any path intersections in new problem. 76 77 Let's keep a *dp* array, *dp**i* keeps minimum cost to cover all edges in subtree of node *i*, also the edge between *i* and *parent**i*. How to find answer of some *i*. Let's choose a worker which *u**j* is in the subtree of *i* and *v**j* is a parent of node *i*. Then if we choose this worker answer must be *c**j* + (*dp**k* where *k* is child of a node in the path from *u**j* to *i* for all *k*'s). Of course we have to exclude nodes chosen as *k* and in the path from *u**j* to *i* since we will cover them with *j*-th worker. We will construct a segment tree by dfs travel times so that for all nodes, workers which start his path in subtree of this node can be reached by looking a contiguous segment in tree. In node *i*, segment will keep values what will be *dp**i* equal to if we choose this worker to cover path between *u**j* and *parent**i*. We will travel our tree with dfs, in each *i* after we calculated node *i*'s children dp's we will update our segment in following way, add all workers to segment where *u**j* = *i* with value *c**j* + (sum of node *i*'s children dp's). For all workers *v**j* equal to *i*, we must delete it from segment, this is assigning *inf* to it. The only thing we didn't handle is what to do with workers under this node. Imagine all updates in subtree of node *k* where *k* is a child of node *i*. We have to increase all of them by (sum of node *i*'s children dp's-*dp**k*). After applying all of this operations answer will be minimum value of workers start their path from a node in subtree of *i* in segment tree. 78 79 Overall complexity will be ((*n* + *m*)*logm*). 80 81 Please look at the [code](https://ideone.com/oxuDlE) to be more clear. 82 83 ### [671E - Organizing a Race](/contest/671/problem/E "Codeforces Round 352 (Div. 1)") 84 85 Intended solution was . Here is [Zlobober](/profile/Zlobober "International Grandmaster Zlobober")'s  code: [Link](https://ideone.com/mYPIwi). 86 87 #### *O*(*n*2) *Solution* 88 89 Let *cost*(*l*, *r*) be minimum cost to make *l*-*r* suitable for a race. In task we have to find such *l*-*r* that *cost*(*l*, *r*) ≤ *k* and *r*-*l*+1 is maximum. 90 91 How to calculate *cost*(*l*, *r*): Let's look at how we do our increases to make race from *l* to *r* (first stage) possible. Greedily we will make our increases in right as much as possible. So if we run out of gas in road between *i* and *i*+1 we will add just enough gasoline to *G**i*. After make first stage possible we will add gasoline to *r* just enough to make second stage possible. This solution will be *O*(*n*3). 92 93 Let's find *next**i*, *next**i* will keep leftmost *j* that we can't reach with current gasoline, we will also keep *need**i* that keeps how many liter gasoline we have to add to *next**i*-1. After applying this increase city *next**i* will be reachable from *i*, cars will be consumed all of their gasoline just before taking gasoline in city *next**i*. 94 95 How to find it: We will keep an array *pre* where *pre**i* = *pre**i* - 1 + *G**i*-*W**i*. If *pre**j*-*pre**i* - 1 < 0 then we can't reach to *j* + 1. If we find leftmost *j* (*j* ≥ *i*) where *pre**j* is strictly smaller than *pre**i* then *next**i* will be equal to *j* and *need**i* will be equal to *pre**j*-*pre**i* - 1. 96 97 Building tree: Let's make a tree where *next**i* is father of node *i*. In dfs travel, when we are in a node *i* all increases will be made to make all first stages possible from *i* to all *j*'s, now we will keep an array *suff* where *suff**i* = *suff**i* - 1 + *G**i*-*W**i* - 1. So when we are increasing a city *u*'s *G**u* we have to increase all *suff* values from u to *n*. We will also keep another array *cost*, *cost**j* will keep the cost to make stage 1 possible from *i* to *j*+1. Increases will be nearly same, for *u* we will increase all *v*'s costs *v* ≥ *u*. So when we reach a node *i* we will apply increases to make first stage possible between *i* ans *next**i*. When we are done with this node, we will revert increases. 98 99 Last part: Now we have to find rightmost *j* for all *i*'s. Let's look at whether it is possible or not for a j. We can check it in *O*(1). First *cost**j* - 1 must be less or equal to *k*, also *maximum*(*suff**k* *i* ≤ *k* < *j*)-(*suff**j*-*delta**j*) + (*cost**j*-*delta**j*) ≤ *k*. *delta**j* keeps how many increases we apply to node *j*. We will decrease them since direct increases in *j* are made for *j*+1, we don't need to keep *delta* array since it will not effect expression. Also observe that the only thing changes in expression is *maximum*(*suff**k* *i* ≤ *k* < *j*). In this way problem can be solved in *O*(*n*2). Both sqrt dec. solutions are using the same idea. Main solution will be posted soon. 100 101 #### How to Reduce it to *O*(*nlog*2*n*) 102 103 Let *p**i* be *cost**i*-*suff**i*. As we said before this value will never change. 104 105 Let's keep a segment tree. In each node we will keep such values. Assume this node of segment covers between *l* and *r*. We will keep such *ind*1, *ind*2 and *mx**suff*. 106 107 *ind*1 will keep minimum *p**j*'s index where *l* ≤ *j* ≤ *r*. 108 109 *ind*2 will keep minimum (*maximum*{*suff**l*≤ *k* < *j*}+*p**j*)'s index where *mid* + 1 ≤ *j* ≤ *r* this means we have to choose *j* from this nodes right child. 110 111 *mx**suff* will keep *maximum*{*suff**l*≤*k*≤*r*}. 112 113 We also have to keep values for *ind*1 and *ind*2 (*p**ind*1 and (*maximum*{*suff**l*≤ *k* < *ind*2}+*p**ind*2)). 114 115 How to update them: In a update we will increase some some suffixes *cost**i* and *suff**i* values. So *ind*1 will be same for each node. For every covered node *mx**suff* will increase by *k* (*k* is increase value in update). Tricky part is how to update *ind*2. Let's define a function *relax*(). *relax*(*u*) calculates *ind*2 value for node *u*. Note that for relax function to work all nodes in subtree of *u* must be calculated already. We will call relax function after calculating this nodes children. We will come to relax function later. 116 117 How to query: We can use pretty much same function as relax. We have to query find values for a *l*-*r* segment. We will keep an extra value in function, let's call it *t*. If this node covers segment *a*-*b* then *t* will keep *maximum*{*suff**l*≤ *k* < *a*}}. If this node doesn't intersect with *l*-*r* segment we will return worst values (for example for mx_suff value we will return -inf). Let's look what to do when this node is covered by *l*-*r*. If *mx**suff* value of this node's left child is greater or equal to *t* then *ind*2 value will be same. So if *maximum*{*suff**l*≤ *k* < *ind*2}+*p**ind*2) is lower or equal to *k* for this node answer is ind2, it is greater than *k* then we will go this nodes left child to calculate answer. If *mx**suff* value of this node's left child is lower than *t* value then (*maximum*{*suff**l*≤ *j* < *mid*}) will equal to *t* for each *j*. So we just have to rightmost *j* that *p**j* ≤ *k* - *t* in subtree of this node. This can be calculated in *O*(*logn*) time. We didn't look at right child yet, so we will go to right child again with same *t* value. What to do when this node intersects with *l*-*r* and *l*-*r* doesn't cover it. We will go both children, first to left, after we will update *t* value for right child by *mx**suff* value returned from left child. We will lazy prop to push values. 118 119 Other condition: In node *l* we have to query between *l* and *r*, *r* is rightmost index that *cost**r* - 1 < *k*. Since cost values are monotonic this *r* can be found easily in *O*(*logn*). 120 121 Relax function can be calculated nearly same as query. But this will work in *O*(*logn*), since we just have to go exactly one child, since we don't interested in rightmost values.