codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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 ![ ](https://espresso.codeforces.com/72731d179aee0e03fb8a446ab4bb2d2c333953b9.png)
     13 
     14 Time Complexity: ![](https://espresso.codeforces.com/e0f3030ecc65e8accd4e0e93a4c694f768e40d1a.png)
     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 ![ ](https://espresso.codeforces.com/67436d52032041dc54647c27e506f956e344f5cb.png)
     23 
     24 Time Complexity: ![](https://espresso.codeforces.com/68e031801404c070f09a1e222bc08242850b89a8.png)
     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 ![](https://espresso.codeforces.com/5f99063b77acadeeafcf85d6be64262c386c2382.png) since the height of the tree is ![](https://espresso.codeforces.com/5f99063b77acadeeafcf85d6be64262c386c2382.png). 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 ![ ](https://espresso.codeforces.com/764c482597d9288bd43c1d792318a0867622bb6e.png)
     41 
     42 Time Complexity: ![](https://espresso.codeforces.com/a9414b6b3e3f51d479ecd26e93de4330afc884de.png)
     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 ![ ](https://espresso.codeforces.com/77c504bcb4d26983d33587ae4f92c69f9229df0a.png)
     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 ![](https://espresso.codeforces.com/440a7f639b59ab9280308ab6f7d1da7ad6df2adb.png) (*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: ![](https://espresso.codeforces.com/68e031801404c070f09a1e222bc08242850b89a8.png)
     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 ![](https://espresso.codeforces.com/cb0172a656698061aefa8eb30b2dbcd1e31f508e.png). 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 ![](https://espresso.codeforces.com/f13c74038b342f3c3078e0da5f634be3743fb25b.png).
     70 
     71 ![ ](https://espresso.codeforces.com/b52c3ac924b7c2f9a3753fdc4faa22e7d5e23be7.png)
     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 ![](https://espresso.codeforces.com/8fd84be2a71dc9412906fd6f37bd3c03b1831420.png) and *q* = 2*n* - 1.
     78 * if *n* is odd then ![](https://espresso.codeforces.com/ac194ee86806b4be28777dce5beea47ddeaeae85.png) 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 (![](https://espresso.codeforces.com/cd6d621bf99a2a096dc91cfdc3e7b99a35ced119.png)) 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 ![ ](https://espresso.codeforces.com/bd37ae34bc71834412ce0f2925079322fe4a4db4.png)
     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: ![](https://espresso.codeforces.com/f3ca95892cb11196016da46b81943a100525ef9a.png).
    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 ![](https://espresso.codeforces.com/e0f3030ecc65e8accd4e0e93a4c694f768e40d1a.png) 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 ![ ](https://espresso.codeforces.com/a01402cb7ddd2240a76415811263fd0cc97a4bbd.png)
    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: ![](https://espresso.codeforces.com/7f962b4a4d26823c842a6b018c132a48c7445c16.png)
    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 ![](https://espresso.codeforces.com/4e1b4126d6b26e55aaecc3e2eca1889d23bc91ed.png) Algorithm:
    150 
    151 ![ ](https://espresso.codeforces.com/7c77e0706bc2e5375879bed0fb332b6959ac2c0b.png)
    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 ![](https://espresso.codeforces.com/3906ccf7533dcd1dc80998404424343f78c3cd19.png) 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 ![ ](https://espresso.codeforces.com/8f9a41bc424201f9441bdd41ebcb12a6f9d25e66.png)
    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 ![](https://espresso.codeforces.com/4e1b4126d6b26e55aaecc3e2eca1889d23bc91ed.png) 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 ![](https://espresso.codeforces.com/68e031801404c070f09a1e222bc08242850b89a8.png) (with sorting as said before). And 2-pointer makes the calls to *good* to be ![](https://espresso.codeforces.com/68e031801404c070f09a1e222bc08242850b89a8.png).
    226 
    227 So the total complexity to check an specific *r* is ![](https://espresso.codeforces.com/3906ccf7533dcd1dc80998404424343f78c3cd19.png).
    228 
    229 Time Complexity: ![](https://espresso.codeforces.com/9ff7ca84dd738c5b6643389d17c8bef607157803.png)
    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 ![ ](/predownloaded/5a/8c/5a8c24d1bf2b5c35b499ea7cd6b7b65af12705c2.png)