645.md (20118B)
1 Source: https://codeforces.com/blog/entry/43868 2 3 ## [645A - Amity Assessment](/contest/645/problem/A "CROC 2016 - Elimination Round") 4 5 **Idea:** [yummy](/profile/yummy "International Master yummy") 6 7 One solution is to just brute force and use DFS to try all the possibilities. Alternatively, note that two puzzles can be changed to each other if and only if the *A*, *B*, and *C* have the same orientation—clockwise or counterclockwise—in the puzzle. A third option, since the number of possibilities is so small, is to simply classify all of the 4! = 24 configurations by hand. 8 9 **Code** 10 11 ``` 12 #include <bits/stdc++.h> 13 using namespace std; 14 15 string b, b1, b2, e, e1, e2; 16 17 int main(){ 18 cin >> b1 >> b2 >> e1 >> e2; 19 swap(b2[0], b2[1]); 20 swap(e2[0], e2[1]); 21 b = b1 + b2; 22 e = e1 + e2; 23 b.erase(b.find('X'), 1); 24 e.erase(e.find('X'), 1); 25 if((b + b).find(e) != string::npos){ 26 cout << "YESn"; 27 } else { 28 cout << "NOn"; 29 } 30 } 31 ``` 32 33 ## [645B - Mischievous Mess Makers](/contest/645/problem/B "CROC 2016 - Elimination Round") 34 35 **Idea: [ksun48](/profile/ksun48 "Master ksun48")** 36 37 Loosely speaking, we’re trying to reverse the array as much as possible. 38 39 Intuitively, the optimal solution seems to be to switch the first and last cow, then the second and second-to-last cow, and so on for *k* minutes, unless the sequence is reversed already, in which case we are done. But how can we show that these moves give the optimal messiness? 40 41 It is clear when 2·*k* ≥ *n* - 1 that we can reverse the array with this method. 42 43 However, when 2·*k* < *n* - 1, there are going to be cows that we must not have not moved a single time. Since in each move we swap at most 2 cows, there must be at least *n* - 2·*k* cows that we have not touched, with *p**i* = *i*. Two untouched cows *i* and *j* must have *p**i* < *p**j*, so there must be at least  pairs of cows which are ordered correctly. 44 45 In fact, if we follow the above process, we get that *p**i* = (*n* + 1) - *i* for the first *k* and last *k* cows, while *p**i* = *i* for the middle *n* - 2·*k* cows. From this we can see that the both *i* < *j* and *p**i* < *p**j* happen only when *i* and *j* are in the middle *n* - 2·*k* cows. Therefore we know our algorithm is optimal. 46 47 An *O*(*k*) solution, therefore, is to count how many incorrectly ordered pairs (*i*, *j*) are created at each step and add them up. When we swap cow *i* and (*n* + 1) - *i* in step *i*, this creates 1 + 2·(*n* - 2*i*) more pairs. So the answer will be . 48 49 We can reduce this to *O*(1) by using our earlier observation, that every pair except those  pairs are unordered, which gives  total pairs (*i*, *j*). Note that this does always not fit in a 32-bit integer. 50 51 **Code** 52 53 ``` 54 #include<bits/stdc++.h> 55 using namespace std; 56 typedef long long LL; 57 58 int main(){ 59 LL n, k; 60 cin >> n >> k; 61 LL c = max(n-2*k,0LL); 62 LL a = n*(n-1)/2-c*(c-1)/2; 63 cout << a << endl; 64 } 65 ``` 66 67 ## [645C - Enduring Exodus](/contest/645/problem/C "CROC 2016 - Elimination Round") 68 69 **Idea: [GlebsHP](/profile/GlebsHP "Grandmaster GlebsHP")** 70 71 First, observe that the *k* + 1 rooms that Farmer John books should be consecutive empty rooms. Thus we can loop over all such sets of rooms with a sliding window in linear time. To check the next set of rooms, we simply advance each endpoint of our interval to the next empty room. Every time we do this, we need to compute the optimal placement of Farmer John’s room. We can maintain the position of his room with two pointers—as we slide our window of rooms to the right, the optimal position of Farmer John’s room should always move to the right or remain the same. This solution runs in *O*(*n*). 72 73 Alternatively, we can use binary search or an STL set to find the best placement for Farmer John’s room as we iterate over the intervals of rooms. The complexity of these approaches is . 74 75 **Code** 76 77 ``` 78 #include <bits/stdc++.h> 79 using namespace std; 80 81 int N, K, res = 1e9; 82 string S; 83 84 int next(int i){ // finds the next empty room 85 do { 86 i += 1; 87 } while(i < N && S[i] == '1'); 88 return i; 89 } 90 91 int main(){ 92 cin >> N >> K >> S; 93 int l = next(-1), m = l, r = l; 94 for(int i = 0; i < K; i++){ // sets up the sliding window 95 r = next(r); 96 } 97 while(r < N){ 98 while(max(m - l, r - m) > max(next(m) - l, r - next(m))){ 99 m = next(m); 100 } 101 res = min(res, max(m - l, r - m)); 102 l = next(l); 103 r = next(r); 104 } 105 cout << res << 'n'; 106 } 107 ``` 108 109 ## [645D - Robot Rapping Results Report](/contest/645/problem/D "CROC 2016 - Elimination Round") 110 111 **Idea: [abacadaea](/profile/abacadaea "Candidate Master abacadaea")** 112 113 The robots will become fully sorted if and only if there exists a path with *n* vertices in the directed graph defined by the match results. Because it is guaranteed that the results are not contradictory, this graph must be directed and acyclic—a DAG. Thus we can compute the longest path in this DAG via dynamic programming or a toposort. 114 115 We now have two cases. First, if the longest path contains *n* vertices, then it must uniquely define the ordering of the robots. This means the answer is the time at which the last edge was added to this path. Otherwise, if the longest path has fewer than *n* vertices, then multiple orderings satisfy the results and you should print - 1. Note that this algorithm runs in *O*(*n* + *m*). 116 117 Another solution to this problem binary searches on the answer. For some *k*, consider only those edges that were added before time *k*. We can determine if the robots could be totally ordered at time *k* by running a toposort and checking if the longest path covers all *n* vertices. This might be more intuitive for some, but has a complexity of . 118 119 **Code** 120 121 ``` 122 #include <bits/stdc++.h> 123 using namespace std; 124 125 const int MAXN = 1000005; 126 int N, M, dp[MAXN], res[MAXN]; 127 vector<pair<int,int>> adj[MAXN]; 128 129 int check(int v){ 130 if(dp[v]) return dp[v]; 131 dp[v] = 1; 132 for(auto p : adj[v]){ 133 int n = p.first; 134 if(check(n) + 1 > dp[v]){ 135 dp[v] = dp[n] + 1; 136 res[v] = max(res[n], p.second); 137 } 138 } 139 return dp[v]; 140 } 141 142 int main(){ 143 scanf("%d%d", &N, &M); 144 for(int i = 0; i < M; i++){ 145 int a, b; 146 scanf("%d%d", &a, &b); 147 a -= 1, b -= 1; 148 adj[a].push_back({b, i + 1}); 149 } 150 for(int i = 0; i < N; i++){ 151 if(check(i) == N){ 152 printf("%dn", res[i]); 153 return 0; 154 } 155 } 156 printf("-1n"); 157 } 158 ``` 159 160 ## [645E - Intellectual Inquiry](/contest/645/problem/E "CROC 2016 - Elimination Round") 161 162 **Idea: [yummy](/profile/yummy "International Master yummy")** 163 164 For simplicity, let’s represent the letters by 1, 2, ..., *k* instead of actual characters. Let *a*[*i*] denote the number of distinct subsequences of the string that end in the letter *i*. Appending the letter *j* to a string only changes the value of *a*[*j*]. Note that the new *a*[*j*] becomes —we can have the single letter *j*, or append *j* to any of our old subsequences. 165 166 The key observation is that no matter what character *j* we choose to append, *a*[*j*] will always end up the same. This suggests a greedy algorithm—always appending the character *j* with the smallest *a*[*j*]. But how do we know which *a*[*j*] is minimal while maintaining their values modulo 109 + 7? 167 168 The final observation is that if the last occurrence of *j* is after the last occurrence of *j*' in our string, then *a*[*j*] > *a*[*j*']. This is true because appending *j* to the string makes *a*[*j*] larger than all other *a*[*i*]. So instead of choosing the minimum *a*[*i*], we can always choose the letter that appeared least recently. Since the sequence of letters we append becomes periodic, our solution runs in . Of course, we can also find the least recently used letter with less efficient approaches, obtaining solutions with complexity *O*((*L* + *n*)*k*). 169 170 **Code** 171 172 ``` 173 #include <bits/stdc++.h> 174 using namespace std; 175 176 typedef long long ll; 177 178 const ll MOD = 1000000007; 179 const int MAXK = 26; 180 int N, K, last[MAXK], ord[MAXK]; 181 ll dp[MAXK], sum; 182 string S; 183 184 bool comp(int a, int b){ 185 return last[a] < last[b]; 186 } 187 188 void append(int c){ 189 sum = (sum - dp[c] + MOD) % MOD; 190 dp[c] = (dp[c] + sum + 1) % MOD; 191 sum = (sum + dp[c]) % MOD; 192 } 193 194 int main(){ 195 cin >> N >> K >> S; 196 fill(last, last + K, -1); 197 for(int i = 0; i < S.size(); i++){ 198 int c = S[i] - 'a'; 199 last[c] = i; 200 append(c); 201 } 202 iota(ord, ord + K, 0); 203 sort(ord, ord + K, comp); 204 for(int i = 0; i < N; i++){ 205 int c = ord[i % K]; 206 append(c); 207 } 208 cout << (sum + 1) % MOD << 'n'; 209 } 210 ``` 211 212 ## [645F - Cowslip Collections](/contest/645/problem/F "CROC 2016 - Elimination Round") 213 214 **Idea: [desert97](/profile/desert97 "Master desert97")** 215 216 After each query, the problem is essentially asking us to compute the sum of  for each choice of *k* flowers. One quickly notes that it is too slow to loop over all choices of *k* flowers, as there could be up to  choices of *k* species. 217 218 So how can we compute a sum over  terms? Well, we will definitely need to use the properties of the gcd function. If we figure out for each integer *a* ≤ 106 how many times  occurs in the sum (let this be *g*(*a*)), then our answer will be equal to  overall all *a*. 219 220 It seems that if *d*(*a*) is the number of multiples of *a* in our sequence, then there are  *k*-tuples which have gcd *a*. Yet there is something wrong with this reasoning: some of those *k*-tuples can have gcd 2*a*, or 3*a*, or any multiple of *a*. In fact, , the number of gcds which are a multiple of *a*. 221 222 We will try to write  as a sum of these . We’ll take an example, when *a* ranges from 1 to 4. The sum we wish to compute is *g*(1) + 2*g*(2) + 3*g*(3) + 4*g*(4) which can be written as 223 224 (*g*(1) + *g*(2) + *g*(3) + *g*(4)) + (*g*(2) + *g*(4)) + 2(*g*(3)) + 2(*g*(4)), 225 226 or 227 228  229 230 In general, we want to find coefficients *p**i* such that we can write  as . Equating coefficients of *g*(*a*) on both sides, we get that . (The mathematically versed reader will note that *p**i* = φ(*i*), Euler's totient function, but this is not necessary to solve the problem.) 231 232 We can thus precalculate all *p**i* in  using a recursive formula: . We can also precalculate  for each *l* ≤ 200000, so in order to output  after each query we should keep track of the values of the function *d*(*i*), the number of multiples of *i*. When receiving *c**i* flowers, we only need to update *d* for the divisors of *c**i* and add . If we precompute the list of divisors of every integer using a sieve or sqrt checking, each update requires *O*(*divisors*). 233 234 Thus the complexity of this algorithm is  or  preprocessing, and *O*((*n* + *q*)·*max*(*divisors*)). 235 236 **Code** 237 238 ``` 239 #include <bits/stdc++.h> 240 using namespace std; 241 242 typedef long long ll; 243 244 const ll MOD = 1000000007; 245 const int MAXN = 200005; 246 const int MAXA = 1000005; 247 int N, K, Q, A[MAXN]; 248 int use[MAXA], phi[MAXA], cnt[MAXA]; 249 vector<int> divisors[MAXA]; 250 ll bin[MAXN], res; 251 252 ll inv(ll a, ll p){ 253 if(a == 1) return 1; 254 return (p - p / a) * inv(p % a, p) % p; 255 } 256 257 void read(){ 258 scanf("%d%d%d", &N, &K, &Q); 259 for(int i = 0; i < N + Q; i++){ 260 scanf("%d", &A[i]); 261 use[A[i]] = 1; 262 } 263 } 264 265 void init(){ 266 iota(phi, phi + MAXA, 0); 267 for(int i = 1; i < MAXA; i++){ 268 for(int j = i; j < MAXA; j += i){ 269 if(i != j) phi[j] -= phi[i]; 270 if(use[j]) divisors[j].push_back(i); 271 } 272 } 273 bin[K - 1] = 1; 274 for(int i = K; i < MAXN; i++){ 275 bin[i] = bin[i - 1] * i % MOD * inv(i - K + 1, MOD) % MOD; 276 } 277 } 278 279 int main(){ 280 read(); 281 init(); 282 for(int i = 0; i < N + Q; i++){ 283 for(int d : divisors[A[i]]){ 284 res = (res + bin[cnt[d]] * phi[d]) % MOD; 285 cnt[d] += 1; 286 } 287 if(i >= N){ 288 printf("%dn", res); 289 } 290 } 291 } 292 ``` 293 294 ## [645G - Armistice Area Apportionment](/contest/645/problem/G "CROC 2016 - Elimination Round") 295 296 **Idea: [yummy](/profile/yummy "International Master yummy")** 297 298 Thanks to [EvenImage](/profile/EvenImage "Legendary Grandmaster EvenImage") and [Petr](/profile/Petr "Legendary Grandmaster Petr") for sharing a solution with me that is much more intuitive than the one I originally had in mind! It works as follows: 299 300 First, let’s try to solve the smaller case where we only have two points. Let  be the line passing through *x**i* and *x**j*. We want to compute the difference of  relative to *P* and *Q*. Define *P*’ as the reflection of *P* over . By the triangle inequality, we have |*PX* - *QX*| = |*P*’*X* - *QX*| ≤ *P*’*Q*. Equality can be achieved when *X*, *P*’ and *Q* are collinear—that is, when *X* is the intersection of  and line *P*’*Q*. (If  and *P*’*Q* are parallel, we can imagine that they intersect at infinity.) Therefore, the difference of a line  relative to *P* and *Q* is the distance from *P*’ to *Q*. 301 302 We can also think about *P*’ in a different way. Let *C**i* be the circle with center *x**i* that pases through *P*. Then *P*’ is the second intersection of the two circles *C**i* and *C**j*. Thus our problem of finding a line with minimum difference becomes equivalent to finding the intersection among {*C**i*} that lies closest to *Q*. This last part we can do with a binary search. 303 304 Consider the problem of checking if two circles *C**i* and *C**j* intersect at a point within a distance *r* of *Q*. In other words, we wish to check if they intersect inside a circle *S* of radius *r* centered at *Q*. Let *A**i* and *A**j* be the arcs of *S* contained by *C**i* and *C**j*, respectively. Observe that *C**i* and *C**j* intersect inside the circle if and only if the two arcs overlap, but do not contain each other. Thus we can verify this condition for all pairs of points with a radial sweep line along the circle. Due to the binary search and the sorting necessary for the sweep line, this solution runs in , where *P* is the precision required. 305 306 One might also wonder if precision will be an issue with all the calculations that we’re doing. It turns out that it won’t be, since our binary search will always stabilize the problem and get us very close to the answer. 307 308 Here’s my original solution using a projective transformation: 309 310 We begin by binary searching on the the minimum possible difference. Thus we wish to solve the decision problem "Can a difference of *k* be achieved?" Consider the hyperbola |*PX* - *QX*| = *k*. Note that our answer is affirmative if and only if a pair of outposts defines a line that does not intersect the hyperbola. 311 312 Our next step is a reduction to an equivalent decision problem on a circle through a projective transformation. We express this transformation as the composition of two simpler operations. The first is an affine map that takes the hyperbola |*PX* - *QX*| = *k* to the unit hyperbola. The second maps homogenous coordinates (*x*, *y*, *z*) to (*z*, *y*, *x*). Under the latter, the unit hyperbola *x*2 - *y*2 = *z*2 goes to the unit circle *x*2 + *y*2 = *z*2. 313 314 Because projective transformations preserve collinearity, a line intersecting the hyperbola is equivalent to a line intersecting the circle. Thus we want to know if any pair of the outposts' images defines a line that does not intersect the circle. We now map the image of each outpost to the minor arc on the unit circle defined by its tangents. (We disregard any points lying inside the circle.) Observe that our condition is equivalent to the existence of two intersecting arcs, neither of which contains the other. Verifying that two such arcs exist can be done with a priority queue and a radial sweep line in . 315 316 The total complexity of our solution is therefore , where *P* is the precision that we need. It turns out that the implementation of this algorithm is actually pretty neat: 317 318 **Code** 319 320 ``` 321 #include <bits/stdc++.h> 322 using namespace std; 323 324 typedef long double ld; 325 326 const ld EPS = 1e-12; 327 const ld PI = acos(-1); 328 const int MAXN = 100005; 329 int N; 330 ld A, X[MAXN], Y[MAXN]; 331 332 bool check(ld m){ 333 ld u = m / 2; 334 ld v = sqrt(A * A - u * u); 335 vector<pair<ld,ld>> ev; 336 for(int i = 0; i < N; i++){ 337 ld x = 1, y = Y[i] / v, alpha; 338 if(X[i] != 0){ 339 x *= u / X[i], y *= u / X[i]; 340 ld r = sqrt(x * x + y * y); 341 if(r < 1) continue; 342 alpha = acos(1 / r); 343 } else { 344 alpha = PI / 2; 345 } 346 ld base = atan2(y, x) - alpha; 347 if(base < 0) base += 2 * PI; 348 ev.push_back({base, base + 2 * alpha}); 349 } 350 priority_queue<ld, vector<ld>, greater<ld>> pq; 351 sort(ev.begin(), ev.end()); 352 for(int i = 0; i < 2; i++){ 353 for(int j = 0; j < ev.size(); j++){ 354 while(pq.size() && pq.top() < ev[j].first) pq.pop(); 355 if(pq.size() && pq.top() < ev[j].second) return 1; 356 pq.push(ev[j].second); 357 ev[j].first += 2 * PI; 358 ev[j].second += 2 * PI; 359 } 360 } 361 return 0; 362 } 363 364 int main(){ 365 ios::sync_with_stdio(0); 366 cin >> N >> A; 367 for(int i = 0; i < N; i++){ 368 cin >> X[i] >> Y[i]; 369 } 370 ld lo = 0, hi = 2 * A; 371 while(hi - lo > EPS){ 372 ld mid = (lo + hi) / 2; 373 (check(mid) ? hi : lo) = mid; 374 } 375 cout << fixed << setprecision(10); 376 cout << (lo + hi) / 2 << 'n'; 377 } 378 ```