548.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 . 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  8 9 Time complexity: . 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  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:  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  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:  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  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: . 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:  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  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: . 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  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:  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 . 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  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  and show it by *lc**i*. 201 202  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:  213 214 [C++ Code](http://ideone.com/6VyRJJ) by [PrinceOfPersia](/profile/PrinceOfPersia "Master PrinceOfPersia") () 215 216 [C++ Code](http://ideone.com/xIKjW2) by [PrinceOfPersia](/profile/PrinceOfPersia "Master PrinceOfPersia") () 217 218 [C++ Code](http://ideone.com/uS0U0f) by [Haghani](/profile/Haghani "International Master Haghani") (Suffix array construction in  and the rest in ) 219 220 [Java Code](http://ideone.com/oag72o) by [Zlobober](/profile/Zlobober "Grandmaster Zlobober") 221 222  223 224 If there's any suggestion or error let me know.