696.md (15477B)
1 Source: https://codeforces.com/blog/entry/46031 2 3 [Here](https://gitlab.com/amirmd76/cf-round-362/tree/master) is git repository to solutions of problems of this contest. 4 5 ### Div.2 A 6 7 You should check two cases for YES: 8 9 1. *x* *mod* *s* = *t* *mod* *s* and *t* ≤ *x* 10 2. *x* *mod* *s* = (*t* + 1) *mod* *s* and *t* + 1 < *x* 11 12  13 14 Time Complexity:  15 16 [Codes](https://gitlab.com/amirmd76/cf-round-362/tree/master/2A) 17 18 ### Div.2 B 19 20 Nothing special, right? just find the position of letters `.` and `e` with string searching methods (like `.find`) and do the rest. 21 22  23 24 Time Complexity:  25 26 [Codes](https://gitlab.com/amirmd76/cf-round-362/tree/master/2B) 27 28 ### A 29 30 Do what problem wants from you. The only thing is to find the path between the two vertices (or LCA) in the tree. You can do this in  since the height of the tree is . You can keep edge weights in a map and get/set the value whenever you want. Here's a code for LCA: 31 32 ``` 33 LCA(v, u): 34 while v != u: 35 if depth[v] < depth[u]: 36 swap(v, u) 37 v = v/2 // v/2 is parent of vertex v 38 ``` 39 40  41 42 Time Complexity:  43 44 [Codes](https://gitlab.com/amirmd76/cf-round-362/tree/master/A) 45 46 ### B 47 48 First of all *starting*_*time* of a vertex is the number of `dfs` calls before the `dfs` call of this vertex plus 1. Now suppose we want to find the answer for vertex *v*. For any vertex *u* that is not in subtree of *v* and is not an ancestor *v*, denote vertices *x* and *y* such that: 49 50 * *x* ≠ *y* 51 * *x* is an ancestor of *v* but not *u* 52 * *y* is an ancestor of *u* but not *v* 53 * *x* and *y* share the same direct parent; That is *par*[*x*] = *par*[*y*]. 54 55  56 57 The probability that *y* occurs sooner than *x* in *children*[*par*[*x*]] after shuffling is 0.5. So the probability that *starting*_*time*[*u*] < *starting*_*time*[*v*] is 0.5. Also We know if *u* is ancestor of *v* this probability is 1 and if it's in subtree of *v* the probability is 0. That's why answer for *v* is equal to  (*depth* is 1-based and *sub*[*v*] is the number of vertices in subtree of *v* including *v* itself). Because *n* - *sub*[*v*] - *h*[*v*] is the number of vertices like the first *u* (not in subtree of *v* and not an ancestor of *v*). 58 59 Thus answer is always either an integer or an integer and a half. 60 61 Time complexity:  62 63 [Codes](https://gitlab.com/amirmd76/cf-round-362/tree/master/B) 64 65 ### C 66 67 It gets tricky when the problem statement says *p* and *q* should be coprimes. A wise coder in this situation thinks of a formula to make sure this happens. 68 69 First of all let's solve the problem if we only want to find the fraction . Suppose *dp*[*i*] is answer for swapping the cups *i* times. It's obvious that *dp*[1] = 0. For *i* > 0, obviously the desired cup shouldn't be in the middle in (*i* - 1) - *th* swap and with this condition the probability that after *i* - *th* swap comes to the middle is 0.5. That's why . 70 71  72 73 Some people may use matrix to find *p* and *q* using this dp (using pair of ints instead of floating point) but there's a risk that *p* and *q* are not coprimes, but fortunately or unfortunately they will be. 74 75 Using some algebra you can prove that: 76 77 * if *n* is even then  and *q* = 2*n* - 1. 78 * if *n* is odd then  and *q* = 2*n* - 1. 79 80 You can confirm that in both cases *p* and *q* are coprimes (since *p* is odd and *q* is a power of 2). 81 82 The only thing left to handle is to find 2*n* (or 2*n* - 1) and parity. Finding parity is super easy. Also 2*n* = 2*a*1 × *a*2 × ... × *a**k* = (...((2*a*1)*a*2)...)*a**k*. So it can be calculated using binary exponential. Also dividing can be done using Fermat's little theorem. 83 84 Time complexity: *O*(*klg*(*MAX*_*A*)). 85 86 [Codes](https://gitlab.com/amirmd76/cf-round-362/tree/master/C) 87 88 ### D 89 90 Build the prefix automaton of these strings (Aho-Corasick). In this automaton every state denotes a string which is prefix of one of given strings (and when we feed characters to it the current state is always the longest of these prefixes that is a suffix of the current string we have fed to it). Building this DFA can be done in various ways (fast and slow). 91 92 Suppose these automaton has *N* states () and state *v* has edges outgoing to states in vector *neigh*[*v*] (if we define our DFA as a directed graph). Suppose state number 1 is the initial state (denoting an empty string). 93 94 If *l* was smaller we could use dp: suppose *dp*[*l*][*v*] is the maximum score of all strings with length equal to *l* ending in state *v* of our DFA when fed into it. 95 96 It's easy to show that *dp*[0][1] = 0 and *dp*[1][*v*] ≤ *b**v* + *dp*[*l* + 1][*u*] for *u* in *neigh*[*v*] and calculating dps can be done using this (here *b**v* is sum of *a* of all strings that are a suffix of string related to state *v*). 97 98  99 100 Now that *l* is large, let's use matrix exponential to calculate the dp. Now dp is not an array, but a column matrix. Finding a matrix to update the dp is not hard. Also we need to reform `+` and `*` operations. In matrix multiplying we should use `+` instead of `*` and `max` instead of `+` in normal multiplication. 101 102 Time complexity: . 103 104 [Codes](https://gitlab.com/amirmd76/cf-round-362/tree/master/D) 105 106 ### E 107 108 First of all, for each query of 1st type we can assume *k* = 1 (because we can perform this query *k* times, it doesn't differ). 109 110 Consider this problem: there are only queries of type 1. 111 112 For solving this problem we can use heavy-light decomposition. If for a vertex *v* of the tree we denote *a**v* as the weight of the lightest girl in it (∞ in case there is no girl in it), for each chain in HLD we need to perform two type of queries: 113 114 1. Get weight of the lightest girl in a substring (consecutive subsequence) of this chain (a subchain). 115 2. Delete the lightest girl in vertex *u*. As the result only *a**u* changes. We can find this value after changing in  if we have the sorted vector of girls' weights for each vertex (and then we pop the last element from it and then current last element is the lightest girl, ∞ in case it becomes empty). 116 117  118 119 This can be done using a classic segment tree. In each node we only need a pair of integers: weight of lightest girl in interval of this node and the vertex she lives in (a `pair<int, int>`). 120 121 This works for this version of the problem. But for the original version we need an additional query type: 122 123 *3.* Increase weight of girls in a substring (consecutive subsequence) of this chain (a subchain) by *k*. 124 125 This can be done using the previous segment tree plus lazy propagation (an additional value in each node, type 3 queries to pass to children). 126 127 Now consider the original problem. Consider an specific chain: after each query of the first type on of the following happens to this chain: 128 129 1. Nothing. 130 2. Only an interval (subchain) is effected. 131 3. Whole chain is effected. 132 133 When case 2 happens, *v* (query argument) belongs to this chain. And this can be done using the 3rd query of chains when we are processing a 2nd type query (effect the chain *v* belongs to). 134 135 When case 3 happens, *v* is an ancestor of the topmost vertex in this chain. So when processing 1st type query, we need to know sum of *k* for all 2nd type queries that their *v* is an ancestor of topmost chain in current chain we're checking. This can be done using a single segment/Fenwick tree (using starting-finishing time trick to convert tree to array). 136 137 So for each query of 1st type, we will check all chains on the path to find the lightest girl and delete her. 138 139 Time Complexity:  140 141 [Codes](https://gitlab.com/amirmd76/cf-round-362/tree/master/E) 142 143 ### F 144 145 In the first thoughts you see that there's definitely a binary search needed (on *r*). Only problem is checking if there are such two points fulfilling conditions with radius *r*. 146 147 For each edge, we can shift it *r* units inside the polygon (parallel to this edge). The only points that can see the line coinciding the line on this edge are inside the half-plane on one side of this shifted line (side containing this edge). So problem is to partition these half-planes in two parts such that intersection of half-planes in each partition and the polygon (another *n* half-planes) is not empty. There are several algorithms for this propose: 148 149  Algorithm: 150 151  152 153 It's obvious that if intersection of some half-planes is not empty, then there's at least on point inside this intersection that is intersection of two of these lines (lines denoting these half-planes). The easiest algorithm is to pick any intersection of these 2*n* lines (*n* shifted half-planes and *n* edges of the polygon) like *p* that lies inside the polygon, delete any half-plane containing this point (intersection of deleted half-planes and polygon is not empty because it contains at least *p*) and check if the intersection of half-planes left and polygon is not empty (of course this part needs sorting half-planes and adds an additional *log* but we can sort the lines initially and use something like counting sort in this step). 154 155 Well, constant factor in this problem is too big and this algorithm will not fit into time limit. But this algorithm will be used to prove the faster algorithm: 156 157  Algorithm: 158 159 In the previous algorithm we checked if *p* can be in intersection of one part. Here's the thing: 160 161 **Lemma 1:** If *p* is inside intersection of two half-planes (*p* is not necessarily intersection of their lines) related to *l* - *th* and *r* - *th* edge (*l* < *r*) and two conditions below are fulfilled, then there's no partitioning that in it *p* is inside intersection of a part (and polygon): 162 163 1. At least one of the half-planes related to an edge with index between *l* and *r* exists that doesn't contain *p*. 164 2. At least one of the half-planes related to an edge with index greater than *r* or less than *l* exists that doesn't contain *p*. 165 166 Because if these two lines exist, they should be in the other part that doesn't contain *p* and if they are, intersection of them and polygon will be empty(proof is easy, homework assignment ;)). 167 168  169 170 This proves that if such partitioning is available that *p* is in intersection of one of them, then it belongs to an interval of edges(cyclic interval) and the rest are also an interval (so intersection of both intervals with polygon should be non-empty). Thus, we don't need *p* anymore. We only need intervals! 171 172 Result is, if such partitioning exists, there are integers *l* and *r* (1 ≤ *l* ≤ *r* ≤ *n*) such that intersection of half-planes related to *l*, *l* + 1, ..., *r* and polygon and also intersection of half-planes related to *r* + 1, *r* + 2, ..., *n*, 1, 2, ..., *l* - 1 and polygon are both non-empty. 173 174 This still gives an  algorithm (checking every interval). But this lemma comes handy here: 175 176 We call an interval(cyclic) good if intersection of lines related to them and polygon is non-empty. 177 178 **Lemma 2:** If an interval is good, then every subinterval of this interval is also good. 179 180 Proof is obvious. 181 182 That gives and idea: 183 184 Denote *interval*(*l*, *r*) is a set of integers such that: 185 186 * If *l* ≤ *r*, then *interval*(*l*, *r*) = {*l*, *l* + 1, ..., *r*} 187 * If *l* ≤ *r*, then *interval*(*l*, *r*) = {*r*, *r* + 1, ..., *n*, 1, ..., *l*} 188 189 (In other words it's a cyclic interval) 190 191 Also *MOD*(*x*) is: 192 193 * *x* iff *x* ≤ *n* 194 * *MOD*(*x* - *n*) iff *x* > *n* 195 196 (In other words it's modulo *n* for 1-based) 197 198 The only thing that matters for us for every *l*, is maximum *len* such that *interval*(*l*, *MOD*(*l* + *len*)) is good (because then all its subintervals are good). 199 200 If *l**i* is maximum *len* that *interval*(*i*, *MOD*(*i* + *len*)) is good, we can use 2-pointer to find values of *l*. 201 202 **Lemma 3:** *l**MOD*(*i* + 1) ≥ *l**i* - 1. 203 204 Proof is obvious in result of *lemma 2*. 205 206 Here's a pseudo code: 207 208 ``` 209 check(r): 210 len = 0 211 for i = 1 to n: 212 while len < n and good(i, MOD(i+len)): // good(l, r) returns true iff interval(l, r) is good 213 len = len + 1 214 if len == 0: 215 return false // Obviously 216 if len == n: 217 return true // Barney and Lyanna can both stay in the same position 218 l[i] = len 219 for i = 1 to n: 220 if l[i] + l[MOD(i+l[i])] >= n: 221 return true 222 return false 223 ``` 224 225 *good* function can be implemented to work in  (with sorting as said before). And 2-pointer makes the calls to *good* to be . 226 227 So the total complexity to check an specific *r* is . 228 229 Time Complexity:  230 231 [Codes](https://gitlab.com/amirmd76/cf-round-362/tree/master/F) 232 233 Feel free to comment and ask your questions. 234 235 