codeforces-scrape

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

547.md (13469B)


      1 Source: https://codeforces.com/blog/entry/18126
      2 
      3 ### [548A - Mike and Fax](/contest/548/problem/A "Codeforces Round 305 (Div. 2)")
      4 
      5 Consider characters of this string are number 0-based from left to right. If |*s*| is not a multiply of *k*, then answer is "NO". Otherwise, let ![](https://espresso.codeforces.com/0410d055cf3a9d573065b070dac046ccde9c4cde.png). Then answer is "Yes" if and only if for each *i* that 0 ≤ *i* < |*s*|, *s**i* = *s*(*i* / *len*) * *len* + *len* - 1 - (*i*%*len*) where *a*%*b* is the remainder of dividing *a* by *b*.
      6 
      7 ![ ](/predownloaded/6a/91/6a919c3e24c4ce3386cfffb8cc5d847b8b1bdf25.png)
      8 
      9 Time complexity: ![](https://espresso.codeforces.com/49bf7bf727722c313d26487ee2548f4c9c149cc3.png).
     10 
     11 [C++ Code](http://ideone.com/HpYQHZ) by [PrinceOfPersia](/profile/PrinceOfPersia "Master PrinceOfPersia")
     12 
     13 [Python Code](http://ideone.com/A6yhex) by [Haghani](/profile/Haghani "International Master Haghani")
     14 
     15 [Python Code](http://ideone.com/PHiL7p) by [Zlobober](/profile/Zlobober "Grandmaster Zlobober")
     16 
     17 ### [548B - Mike and Fun](/contest/548/problem/B "Codeforces Round 305 (Div. 2)")
     18 
     19 Consider this problem: We have a binary sequence *s* and want to find the maximum number of consecutive 1s in it. How to solve this? Easily:
     20 
     21 ```
     22 ans = 0
     23 cur = 0
     24 for i = 1 to n:
     25      if s[i] == 0
     26           then cur = 0
     27      else
     28           cur = cur + 1
     29      ans = max(ans, cur)
     30 ```
     31 
     32 ![ ](/predownloaded/fc/1d/fc1d505341a403d8133679ddc267ced5d346219c.png)
     33 
     34 Finally, answer to this problem is `ans`. For each row *r* of the table, let *ans**r* be the maximum number of consecutive 1s in it (we know how to calculate it in *O*(*m*) right ?). So after each query, update *ans**i* in *O*(*m*) and then find *max*(*ans*1, *ans*2, ..., *ans**n*) in *O*(*n*).
     35 
     36 Time complexity: ![](https://espresso.codeforces.com/c7fc0518769e860b4a03e0fe1d5d1a8077f46e4d.png)
     37 
     38 [C++ Code](http://ideone.com/m84gS5) by [PrinceOfPersia](/profile/PrinceOfPersia "Master PrinceOfPersia")
     39 
     40 [C++ Code](http://ideone.com/6tX7dW) by [Haghani](/profile/Haghani "International Master Haghani")
     41 
     42 [Python Code](http://ideone.com/EpwXOM) by [Zlobober](/profile/Zlobober "Grandmaster Zlobober")
     43 
     44 ### [547A - Mike and Frog](/contest/547/problem/A "Codeforces Round 305 (Div. 1)")
     45 
     46 In this editorial, consider *p* = *m*, *a* = *h*1, *a*′ = *a*1, *b* = *h*2 and *b*′ = *a*2, *x* = *x*1, *y* = *y*1, *X* = *x*2 and *Y* = *y*2.
     47 
     48 First of all, find the number of seconds it takes until height of Xaniar becomes *a*′ (starting from *a*) and call it *q*. Please note that *q* ≤ *p* and if we don't reach *a*′ after *p* seconds, then answer is  - 1.
     49 
     50 If after *q* seconds also height of Abol will become equal to *b*′ then answer if *q*.
     51 
     52 Otherwise, find the height of Abdol after *q* seconds and call it *e*.
     53 
     54 Then find the number of seconds it takes until height of Xaniar becomes *a*′ (starting from *a*′) and call it *c*. Please note that *c* ≤ *p* and if we don't reach *a*′ after *p* seconds, then answer is  - 1.
     55 
     56 if *g*(*x*) = *Xx* + *Y*, then find *f*(*x*) = *g*(*g*(...(*g*(*x*)))) (*c* times). It is really easy:
     57 
     58 ```
     59 c = 1, d = 0
     60 for i = 1 to c
     61      c = (cX) % p
     62      d = (dX + Y) % p
     63 ```
     64 
     65 Then,
     66 
     67 ```
     68 f(x)
     69      return (cx + d) % p
     70 ```
     71 
     72 ![ ](/predownloaded/dc/70/dc70b365d1560f2027d5fd0108c49cc9570e364f.png)
     73 
     74 Actually, if height of Abol is *x* then, after *c* seconds it will be *f*(*x*).
     75 
     76 Then, starting from *e*, find the minimum number of steps of performing `e = f(e)` it takes to reach *b*′ and call it *o*. Please note that *o* ≤ *p* and if we don't reach *b*′ after *p* seconds, then answer is  - 1.
     77 
     78 Then answer is *x* + *c* × *o*.
     79 
     80 Time Complexity: ![](https://espresso.codeforces.com/ed51fa665cc111873b1023c618dc5dd71f8c955e.png)
     81 
     82 [C++ Code](http://ideone.com/2M9fLb) by [PrinceOfPersia](/profile/PrinceOfPersia "Master PrinceOfPersia")
     83 
     84 [C++ Code](http://ideone.com/MvB3Y1) by [Haghani](/profile/Haghani "International Master Haghani")
     85 
     86 [Java Code](http://ideone.com/4PxOgM) by [Zlobober](/profile/Zlobober "Grandmaster Zlobober")
     87 
     88 ### [547B - Mike and Feet](/contest/547/problem/B "Codeforces Round 305 (Div. 1)")
     89 
     90 For each *i*, find the largest *j* that *a**j* < *a**i* and show it by *l**i* (if there is no such *j*, then *l**i* = 0).
     91 
     92 Also, find the smallest *j* that *a**j* < *a**i* and show it by *r**i* (if there is no such *j*, then *r**i* = *n* + 1).
     93 
     94 This can be done in *O*(*n*) with a stack. Pseudo code of the first part (second part is also like that) :
     95 
     96 ```
     97 stack s // initially empty
     98 for i = 1 to n
     99      while s is not empty and a[s.top()] >= a[i]
    100           do s.pop()
    101      if s is empty
    102           then l[i] = 0
    103      otherwise
    104           l[i] = s.top()
    105      s.push(i)
    106 ```
    107 
    108 ![ ](/predownloaded/82/a9/82a906b1846ef5efdba61b8ce95497ead22906fa.png)
    109 
    110 Consider that you are asked to print *n* integers, *ans*1, *ans*2, ..., *ans**n*. Obviously, *ans*1 ≥ *ans*2 ≥ ... ≥ *ans**n*.
    111 
    112 For each *i*, we know that *a**i* can be minimum element in groups of size 1, 2, ..., *r**i* - *l**i* - 1.
    113 
    114 Se we need a data structure for us to do this:
    115 
    116 We have array *ans*1, *ans*2, ..., *ans**n* and all its elements are initially equal to 0. Also, *n* queries. Each query gives *x*, *val* and want us to perform *ans*1 = *max*(*ans*1, *val*), *ans*2 = *max*(*ans*2, *val*), ..., *ans**x* = *max*(*ans**x*, *val*). We want the final array.
    117 
    118 This can be done in *O*(*n*) with a maximum partial sum (keeping maximum instead of sum), [read here for more information about partial sum](/blog/entry/15729).
    119 
    120 Time complexity: ![](https://espresso.codeforces.com/68e031801404c070f09a1e222bc08242850b89a8.png).
    121 
    122 [C++ Code](http://ideone.com/Ryg2gn) by [PrinceOfPersia](/profile/PrinceOfPersia "Master PrinceOfPersia")
    123 
    124 [C++ Code](http://ideone.com/gQ3ijn) by [Haghani](/profile/Haghani "International Master Haghani")
    125 
    126 [Java Code](ideone.com/EDr7bG) by [Zlobober](/profile/Zlobober "Grandmaster Zlobober")
    127 
    128 ### [547C - Mike and Foam](/contest/547/problem/C "Codeforces Round 305 (Div. 1)")
    129 
    130 We define that a number *x* is good if and only if there is no *y* > 1 that *y*2 is a divisor of *x*.
    131 
    132 Also, we define function *f*(*x*) as follow:
    133 
    134 Consider *x* = *p*1*a*1 × *p*2*a*2 × ... × *p**k**a**k* where all *p**i*s are prime. Then, *f*(*x*) = *a*1 + *a*2 + ... + *a**n*.
    135 
    136 Use simple inclusion. Consider all the primes from 1 to 5 × 105 are *p*1, *p*2, ..., *p**k*.
    137 
    138 So, after each query, if *d*(*x*) is the set of beers like *i* in the shelf that *x* is a divisor of *a**i*, then number of pairs with *gcd* equal to 1 is: ![](https://espresso.codeforces.com/ccd365c58a6bcd364af6a37750173b3536eedabd.png)
    139 
    140 Consider good numbers from 1 to 5 × 105 are *b*1, *b*2, ..., *b**m*. The above phrase can be written in some other way: |*d*(*b*1)| × ( - 1)*f*(*b*1) + |*d*(*b*2)| × ( - 1)*f*(*b*2) + ... + |*d*(*b**m*)| × ( - 1)*f*(*b**m*).
    141 
    142 So, for each query if we can find all good numbers that *a**i* is divisible by them in a fast way, we can solve the rest of the problem easily (for each good number *x*, we can store |*d*(*x*)| in an array and just update this array and update the answer).
    143 
    144 ![ ](/predownloaded/b9/9b/b99be3515b0e676e12ec74f9ef35be668e2305a2.png)
    145 
    146 Since all numbers are less than 2 × 3 × 5 × 7 × 11 × 13 × 17, then there are at most 6 primes divisible buy *a**i*. With a simple preprocesses, we can find their maximum and so easily we can find these (at most 6) primes fast. If their amount is *x*, then there are exactly 2*x* good numbers that *a**i* is divisible by them (power of each prime should be either 0 or 1).
    147 
    148 So we can perform each query in *O*(26)
    149 
    150 Time complexity: ![](https://espresso.codeforces.com/3a6cc27d3829df8530905c445fd6f9dd3333c64e.png).
    151 
    152 [C++ Code](http://ideone.com/IxkI9b) by [PrinceOfPersia](/profile/PrinceOfPersia "Master PrinceOfPersia")
    153 
    154 [C++ Code](http://ideone.com/dQcpTQ) by [Haghani](/profile/Haghani "International Master Haghani")
    155 
    156 [Java Code](http://ideone.com/De4DCl) by [Zlobober](/profile/Zlobober "Grandmaster Zlobober")
    157 
    158 ### [547D - Mike and Fish](/contest/547/problem/D "Codeforces Round 305 (Div. 1)")
    159 
    160 Consider a bipartite graph. In each part (we call them first and second part) there are *L* = 2 × 105 vertices numbered from 1 to *L*. For each point (*x*, *y*) add an edge between vertex number *x* from the first part and vertex number *y* from the second part.
    161 
    162 In this problem, we want to color edges with two colors so that the difference between the number of blue edges connected to a vertex and the number of red edges connected to it be at most 1.
    163 
    164 Doing such thing is always possible.
    165 
    166 We prove this and solve the problem at the same time with induction on the number of edges :
    167 
    168 ![ ](/predownloaded/2f/dd/2fdd0fd2aef16b18552a63720d1ede993ee81050.png)
    169 
    170 If all vertices have even degree, then for each component there is an Eulerian circuit, find it and color the edges alternatively_ with blue and red. Because graph is bipartite, then our circuit is an even walk and so, the difference between the number of blue and red edges connected to a vertex will be 0.
    171 
    172 Otherwise, if a vertex like *v* has odd degree, consider a vertex like *u* that there is and edge between *v* and *u*. Delete this edge and solve the problem for the rest of the edges (with the induction definition) and then add this edge and if the number of red edges connected to *u* is more than the blue ones, then color this edge with blue, otherwise with red.
    173 
    174 You can handle this add/delete edge requests and find odd vertices with a simple `set`. So,
    175 
    176 Time complexity: ![](https://espresso.codeforces.com/dd08d1b083cdecc9051dbe7227c15c2909d7c3eb.png)
    177 
    178 [C++ Code](http://ideone.com/0KCyaW) by [PrinceOfPersia](/profile/PrinceOfPersia "Master PrinceOfPersia")
    179 
    180 [C++ Code](http://ideone.com/eL5XDx) by [Haghani](/profile/Haghani "International Master Haghani")
    181 
    182 [Java Code](http://ideone.com/p5VlGg) by [Zlobober](/profile/Zlobober "Grandmaster Zlobober")
    183 
    184 ### [547E - Mike and Friends](/contest/547/problem/E "Codeforces Round 305 (Div. 1)")
    185 
    186 *call*(*i*, *j*) = *match*(*s**jins**i*) which *match*(*tins*) is the number of occurrences of *t* in *s*.
    187 
    188 Concatenate all strings together in order (an put null character between them) and call it string *S*. We know that ![](https://espresso.codeforces.com/a31a2f2447ef49f855917e565cd550ca8f544ff4.png).
    189 
    190 Consider *N* = 5 × 105. Consider Consider for each *i*, *S**x**i**s**x**i* + 1...*s**y**i* = *s**i* (*x**i* + 1 = *y**i* + 2).
    191 
    192 Also, for *i* - *th* character of *S* which is not a null character, consider it belongs to *s**w**i*.
    193 
    194 Calculate the suffix array of *S* in ![](https://espresso.codeforces.com/53bbc34b824ed0e91a4502ea84b607b407a44a95.png) and show it by *f*1, *f*2, ..., *f*|*S*| (we show each suffix by the index of its beginning).
    195 
    196 For each query, we want to know the number of occurrences of *s**k* in *S**x**l*...*s**y**r*. For this propose, we can use this suffix array.
    197 
    198 Consider that we show suffix of *S* starting from index *x* by *S*(*x*).
    199 
    200 Also, for each *i* < |*S*|, calculate *lcp*(*S*(*f**i*), *S*(*f**i* + 1)) totally in ![](https://espresso.codeforces.com/b107264503e0786a5440e75c05872f7a3a273ed2.png) and show it by *lc**i*.
    201 
    202 ![ ](/predownloaded/54/e3/54e3b699b1f31ed6fbce5771e422ce3b16fca0c9.png)
    203 
    204 For each query, consider *f**i* = *x**k*, also find minimum number *a* and maximum number *b* (using binary search and sparse table on sequence *lc*) such that *a* ≤ *i* ≤ *b* and *min*(*lc**a*, *lc**a* + 1, ..., *lc**i* - 1) ≥ |*s**k*| and *min*(*lc**i*, *lc**i* + 1, ..., *lc**b* - 1) ≥ |*s**k*|.
    205 
    206 Finally answer of this query is the number of elements in *w**a*, *w**a* + 1, ..., *w**b* that are in the interval [*l*, *r*].
    207 
    208 This problem is just like [KQUERY](http://www.spoj.com/problems/KQUERY/). You can read my offline approach for KQUERY [here](/blog/entry/15890). It uses segment tree, but you can also use Fenwick instead of segment tree.
    209 
    210 This wasn't my main approach. My main approach uses aho-corasick and a data structure I invented and named it C-Tree.
    211 
    212 Time complexity: ![](https://espresso.codeforces.com/d5c2a161af837f03f30ca07432f2b99ea3858ac7.png)
    213 
    214 [C++ Code](http://ideone.com/6VyRJJ) by [PrinceOfPersia](/profile/PrinceOfPersia "Master PrinceOfPersia") (![](https://espresso.codeforces.com/d5c2a161af837f03f30ca07432f2b99ea3858ac7.png))
    215 
    216 [C++ Code](http://ideone.com/xIKjW2) by [PrinceOfPersia](/profile/PrinceOfPersia "Master PrinceOfPersia") (![](https://espresso.codeforces.com/d5e921d77c79e34656220d3a7685a01540e7269e.png))
    217 
    218 [C++ Code](http://ideone.com/uS0U0f) by [Haghani](/profile/Haghani "International Master Haghani") (Suffix array construction in ![](https://espresso.codeforces.com/d5e921d77c79e34656220d3a7685a01540e7269e.png) and the rest in ![](https://espresso.codeforces.com/d5c2a161af837f03f30ca07432f2b99ea3858ac7.png))
    219 
    220 [Java Code](http://ideone.com/oag72o) by [Zlobober](/profile/Zlobober "Grandmaster Zlobober")
    221 
    222 ![ ](/predownloaded/40/d1/40d11b74e20e6ccf0c96d3f108bcd09af35a1f4f.png)
    223 
    224 If there's any suggestion or error let me know.