660.md (16585B)
1 Source: https://codeforces.com/blog/entry/44259 2 3 ### [660A - Co-prime Array](/contest/660/problem/A "Educational Codeforces Round 11") 4 5 The problem was suggested by Ali Ibrahim [C137](/profile/C137 "Specialist C137"). 6 7 Note that we should insert some number between any adjacent not co-prime elements. On other hand we always can insert the number 1. 8 9 **С++ solution** 10 11 ``` 12 const int N = 1010; 13 14 int n, a[N]; 15 16 bool read() { 17 if (!(cin >> n)) return false; 18 forn(i, n) assert(scanf("%d", &a[i]) == 1); 19 return true; 20 } 21 22 void solve() { 23 function<int(int, int)> gcd = [&](int a, int b) { return !a ? b : gcd(b % a, a); }; 24 25 vector<int> ans; 26 forn(i, n) { 27 ans.pb(a[i]); 28 if (i + 1 < n && gcd(a[i], a[i + 1]) > 1) 29 ans.pb(1); 30 } 31 32 cout << sz(ans) - n << endl; 33 forn(i, sz(ans)) { 34 if (i) putchar(' '); 35 printf("%d", ans[i]); 36 } 37 puts(""); 38 } 39 ``` 40 41 Complexity: *O*(*nlogn*). 42 43 ### [660B - Seating On Bus](/contest/660/problem/B "Educational Codeforces Round 11") 44 45 The problem was suggested by Srikanth Bhat [bharsi](/profile/bharsi "Expert bharsi"). 46 47 In this problem you should simply do what was written in the problem statement. There are no tricks. 48 49 **C++ solution** 50 51 ``` 52 int n, m; 53 54 bool read() { 55 return !!(cin >> n >> m); 56 } 57 58 const int N = 111; 59 60 int a[N][4]; 61 62 void solve() { 63 forn(i, n) { 64 a[i][0] = 2 * i; 65 a[i][1] = 2 * (n + i); 66 a[i][2] = 2 * (n + i) + 1; 67 a[i][3] = 2 * i + 1; 68 } 69 70 vector<int> ans; 71 forn(i, n) { 72 ans.pb(a[i][1]); 73 ans.pb(a[i][0]); 74 ans.pb(a[i][2]); 75 ans.pb(a[i][3]); 76 } 77 78 nfor(i, sz(ans)) // inverse order 79 if (ans[i] >= m) 80 ans.erase(ans.begin() + i); 81 82 forn(i, m) { 83 if (i) putchar(' '); 84 printf("%d", ans[i] + 1); 85 } 86 puts(""); 87 } 88 ``` 89 90 Complexity: *O*(*n*). 91 92 ### [660C - Hard Process](/contest/660/problem/C "Educational Codeforces Round 11") 93 94 The problem was suggested by Mohammad Amin Raeisi [Smaug](/profile/Smaug "Newbie Smaug"). 95 96 Let's call the segment [*l*, *r*] good if it contains no more than *k* zeroes. Note if segment [*l*, *r*] is good than the segment [*l* + 1, *r*] is also good. So we can use the method of two pointers: the first pointer is *l* and the second is *r*. Let's iterate over *l* from the left to the right and move *r* while we can (to do that we should simply maintain the number of zeroes in the current segment). 97 98 **C++ solution** 99 100 ``` 101 const int N = 1200300; 102 103 int n, k; 104 int a[N]; 105 106 bool read() { 107 if (!(cin >> n >> k)) return false; 108 forn(i, n) assert(scanf("%d", &a[i]) == 1); 109 return true; 110 } 111 112 void solve() { 113 int ansl = 0, ansr = 0; 114 int j = 0, cnt = 0; 115 forn(i, n) { 116 if (j < i) { 117 j = i; 118 cnt = 0; 119 } 120 121 while (j < n) { 122 int ncnt = cnt + !a[j]; 123 if (ncnt > k) break; 124 cnt += !a[j]; 125 j++; 126 } 127 128 if (j - i > ansr - ansl) 129 ansl = i, ansr = j; 130 131 if (cnt > 0) cnt -= !a[i]; 132 } 133 134 cout << ansr - ansl << endl; 135 fore(i, ansl, ansr) a[i] = 1; 136 forn(i, n) { 137 if (i) putchar(' '); 138 printf("%d", a[i]); 139 } 140 puts(""); 141 } 142 ``` 143 144 Complexity: *O*(*n*). 145 146 ### [660D - Number of Parallelograms](/contest/660/problem/D "Educational Codeforces Round 11") 147 148 The problem was suggested by Sadegh Mahdavi [smahdavi4](/profile/smahdavi4 "Expert smahdavi4"). 149 150 It's known that the diagonals of a parallelogram split each other in the middle. Let's iterate over the pairs of points *a*, *b* and consider the middle of the segment : . Let's calculate the value *cnt**c* for each middle. *cnt**c* is the number of segments *a*, *b* with the middle *c*. Easy to see that the answer is . 151 152 **C++ solution** 153 154 ``` 155 const int N = 2020; 156 157 int n; 158 int x[N], y[N]; 159 160 bool read() { 161 if (!(cin >> n)) return false; 162 forn(i, n) 163 assert(scanf("%d%d", &x[i], &y[i]) == 2); 164 return true; 165 } 166 167 inline li C2(li n) { return n * (n - 1) / 2; } 168 169 void solve() { 170 map<pti, int> cnt; 171 172 forn(i, n) 173 forn(j, i) { 174 int cx = x[i] + x[j]; 175 int cy = y[i] + y[j]; 176 cnt[{cx, cy}]++; 177 } 178 179 li ans = 0; 180 for (const auto& p : cnt) 181 ans += C2(p.y); 182 cout << ans << endl; 183 } 184 ``` 185 186 Complexity: *O*(*n*2*logn*). 187 188 ### [660E - Different Subsets For All Tuples](/contest/660/problem/E "Educational Codeforces Round 11") 189 190 The problem was suggested by Lewin Gan [Lewin](/profile/Lewin "International Master Lewin"). 191 192 Let's consider some subsequence with the length *k* > 0 (the empty subsequences we will count separately by adding the valye *m**n* at the end) and count the number of sequences that contains it. We should do that accurately to not count the same sequence multiple times. Let *x*1, *x*2, ..., *x**k* be the fixed subsequence. In the original sequence before the element *x*1 can be some other elements, but none of them can be equal to *x*1 (because we want to count the subsequence exactly one time). So we have *m* - 1 variants for each of the elements before *x*1. Similarly between elements *x*1 and *x*2 can be other elements and we have *m* - 1 choices for each of them. And so on. After the element *x**k* can be some elements (suppose there are *j* such elements) with no additional constraints (so we have *m* choices for each of them). We fixed the number of elements at the end *j*, so we should distribute *n* - *k* - *j* numbers between numbers before *x*1, between *x*1 and *x*2, \ldots, between *x**k* - 1 and *x**k*. Easy to see that we have  choices to do that (it's simply binomial coefficient with allowed repititions). The number of sequences *x*1, *x*2, ..., *x**k* equals to *m**k*. So the answer is . Easy to transform the last sum to the sum . Note the last inner sum can be calculating using the formula for parallel summing: . So the answer equals to . Also we can get the closed formula for the last sum to get logarithmic solution, but it is not required in the problem. 193 194 **C++ solution** 195 196 ``` 197 int n, m; 198 199 bool read() { 200 return !!(cin >> n >> m); 201 } 202 203 const int N = 1200300; 204 205 const int mod = 1000 * 1000 * 1000 + 7; 206 207 int gcd(int a, int b, int& x, int& y) { 208 if (!a) { 209 x = 0, y = 1; 210 return b; 211 } 212 int xx, yy, g = gcd(b % a, a, xx, yy); 213 x = yy - b / a * xx; 214 y = xx; 215 return g; 216 } 217 218 inline int inv(int a) { 219 int x, y; 220 assert(gcd(a, mod, x, y) == 1); 221 x %= mod; 222 return x < 0 ? x + mod : x; 223 } 224 225 inline int mul(int a, int b) { return int(a * 1ll * b % mod); } 226 inline int add(int a, int b) { return a + b >= mod ? a + b - mod : a + b; } 227 inline int sub(int a, int b) { return a - b < 0 ? a - b + mod : a - b; } 228 229 inline void inc(int& a, int b) { a = add(a, b); } 230 231 int fact[N], ifact[N]; 232 233 inline int C(int n, int k) { 234 if (k < 0 || k > n) return 0; 235 return mul(fact[n], mul(ifact[k], ifact[n - k])); 236 } 237 238 int pm[N], pm1[N]; 239 240 void solve() { 241 const int N = n + 1; 242 243 fact[0] = 1; fore(i, 1, N) fact[i] = mul(fact[i - 1], i); 244 forn(i, N) ifact[i] = inv(fact[i]); 245 246 pm[0] = 1; fore(i, 1, N) pm[i] = mul(pm[i - 1], m); 247 pm1[0] = 1; fore(i, 1, N) pm1[i] = mul(pm1[i - 1], sub(m, 1)); 248 249 int ans = pm[n]; 250 fore(s, 1, n + 1) { 251 int cur = 1; 252 cur = mul(cur, pm[s]); 253 cur = mul(cur, pm1[n - s]); 254 cur = mul(cur, C(n, s - 1)); 255 inc(ans, cur); 256 } 257 cout << ans << endl; 258 } 259 ``` 260 261 Complexity: *O*((*n* + *m*)*log* *MOD*), где *MOD* = 109 + 7. 262 263 ### [660F - Bear and Bowling 4](/contest/660/problem/F "Educational Codeforces Round 11") 264 265 The problem was prepared by Kamil Debowski [Errichto](/profile/Errichto "International Grandmaster Errichto"). The problem analysis is also prepared by him. 266 267 The key is to use divide and conquer. We need a recursive function `f(left, right)` that runs `f(left, mid)` and `f(mid+1, right)` (where *mid* = (*left* + *right*) / 2) and also considers all intervals going through *mid*. We will eventually need a convex hull of lines (linear functions) and let's see how to achieve it. 268 269 For variables *L*, *R* (, ) we will try to write the score of interval [*L*, *R*] as a linear function. It would be good to get something close to *a**L*·*x**R* + *b**L* where *a**L* and *b**L* depend on *L*, and *x**R* depends on *R* only. 270 271  272 273 For each *L* we should find a linear function *f**L*(*x*) = *a**L*·*x* + *b**L* where *a**L*, *b**L* should fit the equation ( * ): 274 275  276 277 Now we have a set of linear functions representing all possible left endpoints *L*. For each right endpoint *R* we should find *x**R* and *const**R* to fit equation ( * ) again. With value of *x**R* we can iterate over functions *f**L* to find the one maximizing value of *b**L* + *a**L*·*x**R*. And (still for fixed *R*) we should add *const**R* to get the maximum possible score of interval ending in *R*. 278 279 **Brute Force with functions** 280 281 ``` 282 #include<bits/stdc++.h> 283 using namespace std; 284 typedef long long ll; 285 const int nax = 1e6 + 5; 286 ll ans; 287 ll t[nax]; 288 289 struct Fun { 290 ll a, b; 291 ll getValue(ll x) { return a * x + b; } 292 }; 293 294 void rec(int first, int last) { 295 if(first == last) { 296 ans = max(ans, t[first]); 297 return; 298 } 299 int mid = (first + last) / 2; 300 301 rec(first, mid); // the left half is [first, mid] 302 rec(mid+1, last); // the right half is [mid+1, last] 303 304 // we must consider all intervals starting in [first,mid] and ending in [mid+1, last] 305 306 vector<Fun> functions; 307 ll sum_so_far = 0; // t[i]+t[i+1]+...+t[mid] 308 ll score_so_far = 0; // t[i]*1 + t[i+1]*2 + ... + t[mid]*(mid-i+1) 309 for(int i = mid; i >= first; --i) { 310 sum_so_far += t[i]; 311 score_so_far += sum_so_far; 312 functions.push_back(Fun{mid - i + 1, score_so_far}); 313 } 314 315 sum_so_far = 0; 316 score_so_far = 0; 317 for(int i = mid+1; i <= last; ++i) { 318 sum_so_far += t[i]; 319 score_so_far += t[i] * (i - mid); 320 for(Fun & f : functions) { 321 ll score = score_so_far + f.getValue(sum_so_far); 322 ans = max(ans, score); 323 } 324 } 325 } 326 327 int main() { 328 int n; 329 scanf("%d", &n); 330 for(int i = 1; i <= n; ++i) scanf("%lld", &t[i]); 331 rec(1, n); 332 printf("%lldn", ans); 333 return 0; 334 } 335 ``` 336 337 Now let's make it faster. After finding a set of linear functions *f**L* we should build a convex hull of them (note that they're already sorted by slope). To achieve it we need something to compare 3 functions and decide whether one of them is unnecessary because it's always below one of other two functions. Note that in standard convex hull of points you also need something similar (but for 3 points). Below you can find an almost-fast-enough solution with a useful function `bool is_middle_needed(f1, f2, f3)`. You may check that numbers calculated there do fit in `long long`. 338 339 **Almost fast enough** 340 341 ``` 342 #include<bits/stdc++.h> 343 using namespace std; 344 typedef long long ll; 345 const int nax = 1e6 + 5; 346 ll ans; 347 ll t[nax]; 348 349 struct Fun { 350 ll a, b; 351 ll getValue(ll x) { return a * x + b; } 352 }; 353 354 bool is_middle_needed(const Fun & f1, const Fun & f2, const Fun & f3) { 355 // we ask if for at least one 'x' there is f2(x) > max(f1(x), f3(x)) 356 assert(0 < f1.a && f1.a < f2.a && f2.a < f3.a); 357 358 // where is the intersection of f1 and f2? 359 // f1.a * x + f1.b = f2.a * x + f2.b 360 // x * (f2.a - f1.a) = f1.b - f2.b 361 // x = (f1.b - f2.b) / (f2.a - f1.a) 362 ll p1 = f1.b - f2.b; 363 ll q1 = f2.a - f1.a; 364 // and the intersection of f1 and f3 365 ll p2 = f1.b - f3.b; 366 ll q2 = f3.a - f1.a; 367 assert(q1 > 0 && q2 > 0); 368 // return p1 / q1 < p2 / q2 369 return p1 * q2 < q1 * p2; 370 } 371 372 void rec(int first, int last) { 373 if(first == last) { 374 ans = max(ans, t[first]); 375 return; 376 } 377 int mid = (first + last) / 2; 378 379 rec(first, mid); // the left half is [first, mid] 380 rec(mid+1, last); // the right half is [mid+1, last] 381 382 // we must consider all intervals starting in [first,mid] and ending in [mid+1, last] 383 384 vector<Fun> functions; 385 ll sum_so_far = 0; // t[i]+t[i+1]+...+t[mid] 386 ll score_so_far = 0; // t[i]*1 + t[i+1]*2 + ... + t[mid]*(mid-i+1) 387 for(int i = mid; i >= first; --i) { 388 sum_so_far += t[i]; 389 score_so_far += sum_so_far; 390 Fun f = Fun{mid - i + 1, score_so_far}; 391 while(true) { 392 int s = functions.size(); 393 if(s >= 2 && !is_middle_needed(functions[s-2], functions[s-1], f)) 394 functions.pop_back(); 395 else 396 break; 397 } 398 functions.push_back(f); 399 } 400 401 sum_so_far = 0; 402 score_so_far = 0; 403 for(int i = mid+1; i <= last; ++i) { 404 sum_so_far += t[i]; 405 score_so_far += t[i] * (i - mid); 406 for(Fun & f : functions) { 407 ll score = score_so_far + f.getValue(sum_so_far); 408 ans = max(ans, score); 409 } 410 } 411 } 412 413 int main() { 414 int n; 415 scanf("%d", &n); 416 for(int i = 1; i <= n; ++i) scanf("%lld", &t[i]); 417 rec(1, n); 418 printf("%lldn", ans); 419 return 0; 420 } 421 ``` 422 423 Finally, one last thing is needed to make it faster than *O*(*n*2). We should use the fact that we have built a convex hull of functions (lines). For each *R* you should binary search optimal function. Alternatively, you can sort pairs (*x**R*, *const**R*) and then use the two pointers method — check the implementation in my solution below. It gives complexity  because we sort by *x**R* inside of a recursive function. I think it's possible to get rid of this by sorting prefixes  in advance because it's equivalent to sorting by *x**R*. And we should use the already known order when we run a recursive function for smaller intervals. So, I think  is possible this way — anybody implemented it? 424 425 **Intended solution with two pointers** 426 427 ``` 428 // O(n log^2(n)) 429 #include<bits/stdc++.h> 430 using namespace std; 431 typedef long long ll; 432 const int nax = 1e6 + 5; 433 ll ans; 434 ll t[nax]; 435 436 struct Fun { 437 ll a, b; 438 ll getValue(ll x) { return a * x + b; } 439 }; 440 441 bool is_middle_needed(const Fun & f1, const Fun & f2, const Fun & f3) { 442 // we ask if for at least one 'x' there is f2(x) > max(f1(x), f3(x)) 443 assert(0 < f1.a && f1.a < f2.a && f2.a < f3.a); 444 445 // where is the intersection of f1 and f2? 446 // f1.a * x + f1.b = f2.a * x + f2.b 447 // x * (f2.a - f1.a) = f1.b - f2.b 448 // x = (f1.b - f2.b) / (f2.a - f1.a) 449 ll p1 = f1.b - f2.b; 450 ll q1 = f2.a - f1.a; 451 // and the intersection of f1 and f3 452 ll p2 = f1.b - f3.b; 453 ll q2 = f3.a - f1.a; 454 assert(q1 > 0 && q2 > 0); 455 // return p1 / q1 < p2 / q2 456 return p1 * q2 < q1 * p2; 457 } 458 459 void rec(int first, int last) { 460 if(first == last) { 461 ans = max(ans, t[first]); 462 return; 463 } 464 int mid = (first + last) / 2; 465 466 rec(first, mid); // the left half is [first, mid] 467 rec(mid+1, last); // the right half is [mid+1, last] 468 469 // we must consider all intervals starting in [first,mid] and ending in [mid+1, last] 470 471 vector<Fun> functions; 472 ll sum_so_far = 0; // t[i]+t[i+1]+...+t[mid] 473 ll score_so_far = 0; // t[i]*1 + t[i+1]*2 + ... + t[mid]*(mid-i+1) 474 for(int i = mid; i >= first; --i) { 475 sum_so_far += t[i]; 476 score_so_far += sum_so_far; 477 Fun f = Fun{mid - i + 1, score_so_far}; 478 while(true) { 479 int s = functions.size(); 480 if(s >= 2 && !is_middle_needed(functions[s-2], functions[s-1], f)) 481 functions.pop_back(); 482 else 483 break; 484 } 485 functions.push_back(f); 486 } 487 488 vector<pair<ll, ll>> points; 489 sum_so_far = 0; 490 score_so_far = 0; 491 for(int i = mid+1; i <= last; ++i) { 492 sum_so_far += t[i]; 493 score_so_far += t[i] * (i - mid); 494 points.push_back({sum_so_far, score_so_far}); 495 /*for(Fun & f : functions) { 496 ll score = score_so_far + f.getValue(sum_so_far); 497 ans = max(ans, score); 498 }*/ 499 } 500 501 sort(points.begin(), points.end()); 502 int i = 0; // which function is the best 503 for(pair<ll, ll> p : points) { 504 sum_so_far = p.first; 505 score_so_far = p.second; 506 while(i + 1 < (int) functions.size() 507 && functions[i].getValue(sum_so_far) <= functions[i+1].getValue(sum_so_far)) 508 ++i; 509 ans = max(ans, score_so_far + functions[i].getValue(sum_so_far)); 510 } 511 } 512 513 int main() { 514 int n; 515 scanf("%d", &n); 516 for(int i = 1; i <= n; ++i) scanf("%lld", &t[i]); 517 rec(1, n); 518 printf("%lldn", ans); 519 return 0; 520 } 521 ``` 522 523 Complexity: *O*(*nlog*2*n*).