665.md (16624B)
1 Source: https://codeforces.com/blog/entry/44466 2 3 ### [665A - Buses Between Cities](/contest/665/problem/A "Educational Codeforces Round 12") 4 5 The problem was suggested by Sergey Erlikh [unprost](/profile/unprost "Expert unprost"). 6 7 Consider the time interval when Simion will be on the road strictly between cities (*x*1, *y*1) (*x*1 = 60*h* + *m*, *y*1 = *x*1 + *t**a*). Let's iterate over the oncoming buses. Let (*x*2, *y*2) be the time interval when the oncoming bus will be strictly between two cities. If the intersection of that intervals (*x* = *max*(*x*1, *x*2), *y* = *min*(*y*1, *y*2)) is not empty than Simion will count that bus. 8 9 **С++ solution** 10 11 ``` 12 int a, ta; 13 int b, tb; 14 int h, m; 15 16 bool read() { 17 if (!(cin >> a >> ta)) return false; 18 assert(cin >> b >> tb); 19 assert(scanf("%d:%d", &h, &m) == 2); 20 return true; 21 } 22 23 void solve() { 24 int x1 = h * 60 + m; 25 int y1 = x1 + ta; 26 27 int ans = 0; 28 for (int x2 = 5 * 60 + 0; x2 < 24 * 60; x2 += b) { 29 int y2 = x2 + tb; 30 int x = max(x1, x2), y = min(y1, y2); 31 if (x < y) 32 ans++; 33 } 34 cout << ans << endl; 35 } 36 ``` 37 38 Complexity: *O*(1). 39 40 ### [665B - Shopping](/contest/665/problem/B "Educational Codeforces Round 12") 41 42 The problem was suggested by Ayush Anand [JeanValjean01](/profile/JeanValjean01 "Newbie JeanValjean01"). 43 44 In this problem you should simply do what was written in the problem statement. There are no tricks. 45 46 **C++ solution** 47 48 ``` 49 const int N = 111; 50 51 int n, m, k; 52 int p[N]; 53 int a[N][N]; 54 55 bool read() { 56 if (!(cin >> n >> m >> k)) return false; 57 forn(i, k) { 58 assert(scanf("%d", &p[i]) == 1); 59 p[i]--; 60 } 61 forn(i, n) 62 forn(j, m) { 63 assert(scanf("%d", &a[i][j]) == 1); 64 a[i][j]--; 65 } 66 return true; 67 } 68 69 void solve() { 70 int ans = 0; 71 forn(i, n) 72 forn(j, m) { 73 int pos = int(find(p, p + k, a[i][j]) - p); 74 ans += pos + 1; 75 nfor(l, pos) p[l + 1] = p[l]; 76 p[0] = a[i][j]; 77 } 78 cout << ans << endl; 79 } 80 ``` 81 82 Complexity: *O*(*nmk*). 83 84 ### [665C - Simple Strings](/contest/665/problem/C "Educational Codeforces Round 12") 85 86 The problem was suggested by Zi Song Yeoh [zscoder](/profile/zscoder "Candidate Master zscoder"). 87 88 There are two ways to solve this problem: greedy approach and dynamic programming. 89 90 The first apprroach: Considerr some segment of consecutive equal characters. Let *k* be the length of that segment. Easy to see that we should change at least  characters in the segment to remove all the pairs of equal consecutive letters. On the other hand we can simply change the second, the fourth etc. symbols to letter that is not equal to the letters before and after the segment. 91 92 **Greedy approach on C++** 93 94 ``` 95 const int N = 200200; 96 97 int n; 98 char s[N]; 99 100 bool read() { 101 if (!gets(s)) return false; 102 n = int(strlen(s)); 103 return true; 104 } 105 106 void solve() { 107 for (int i = 0, j = 0; i < n; i = j) { 108 while (j < n && s[j] == s[i]) j++; 109 char c = 'a'; 110 while (c == s[i] || (i > 0 && c == s[i - 1]) || (j < n && c == s[j])) 111 c++; 112 fore(k, i, j) 113 if ((i + k) & 1) 114 s[k] = c; 115 } 116 puts(s); 117 } 118 ``` 119 120 The second approach: Let *z**ka* be the minimal number of changes so that the prefix of length *k* has no equal consecutive letters and the symbol *s*'*k* equals to *a*. Let's iterate over the letter on the position *k* + 1 and if it is not equal to *a* make transition. The cost of the transition is equal to 0 if we put the same letter as in the original string *s* on the position *k* + 1. Otherwise the cost is equal to 1. 121 122 **DP solution on C++** 123 124 ``` 125 const int N = 1200300, A = 27; 126 127 int n; 128 char s[N]; 129 130 bool read() { 131 if (!gets(s)) return false; 132 n = int(strlen(s)); 133 return true; 134 } 135 136 int z[N][A]; 137 int p[N][A]; 138 char ans[N]; 139 140 void solve() { 141 memset(z, 63, sizeof(z)); 142 143 z[0][A - 1] = 0; 144 forn(i, n) { 145 int c = int(s[i] - 'a'); 146 forn(j, A) { 147 int dv = z[i][j]; 148 if (dv > INF / 2) continue; 149 forn(nj, A - 1) { 150 if (nj == j) continue; 151 int ct = nj != c; 152 if (z[i + 1][nj] > dv + ct) { 153 z[i + 1][nj] = dv + ct; 154 p[i + 1][nj] = j; 155 } 156 } 157 } 158 } 159 160 int idx = int(min_element(z[n], z[n] + A) - z[n]); 161 162 for (int i = n, j = idx; i > 0; j = p[i][j], i--) 163 ans[i - 1] = char('a' + j); 164 ans[n] = 0; 165 166 cerr << z[n][idx] << endl; 167 puts(ans); 168 } 169 ``` 170 171 Complexity: *O*(*n*). 172 173 ### [665D - Simple Subset](/contest/665/problem/D "Educational Codeforces Round 12") 174 175 The problem was suggested by Zi Song Yeoh [zscoder](/profile/zscoder "Candidate Master zscoder"). 176 177 Consider the subset *A* that is the answer to the problem. Let *a*, *b*, *c* be the arbitrary three elements from *A* and let no more than one of them is equal to 1. By the pigeonhole principle two of three elements from *a*, *b*, *c* have the same parity. So we have two integers with even sum and only one of them is equal to 1, so their sum is also greater than 2. So the subset *A* is not simple. In this way *A* consists of only two numbers greater than one (with a prime sum) or consists of some number of ones and also maybe other value *x*, so that *x* + 1 is a prime. 178 179 We can simply process the first case in *O*(*n*2) time. The second case can be processed in linear time. Also we should choose the best answer from that two. 180 181 To check the value of order 2·106 for primality in *O*(1) time we can use the simple or the linear Eratosthenes sieve. 182 183 **C++ solution** 184 185 ``` 186 const int N = 1010, X = 2100300; 187 188 int n, a[N]; 189 190 bool read() { 191 if (!(cin >> n)) return false; 192 forn(i, n) assert(scanf("%d", &a[i]) == 1); 193 return true; 194 } 195 196 int szp, p[X]; 197 int mind[X]; 198 199 void prepare() { 200 fore(i, 2, X) { 201 if (!mind[i]) { 202 p[szp++] = i; 203 mind[i] = i; 204 } 205 for (int j = 0; j < szp && p[j] <= mind[i] && i * p[j] < X; j++) 206 mind[i * p[j]] = p[j]; 207 } 208 } 209 210 void printAns(int cnt1, int a = -1, int b = -1) { 211 vector<int> ans; 212 forn(i, cnt1) ans.pb(1); 213 if (a != -1) ans.pb(a); 214 if (b != -1) ans.pb(b); 215 assert(!ans.empty()); 216 random_shuffle(all(ans)); 217 218 cout << sz(ans) << endl; 219 forn(i, sz(ans)) { 220 if (i) putchar(' '); 221 printf("%d", ans[i]); 222 } 223 puts(""); 224 } 225 226 void solve() { 227 int cnt1 = (int) count(a, a + n, 1); 228 229 function<bool(int)> isPrime = [](int p) { return mind[p] == p; }; 230 231 if (cnt1 > 0) 232 forn(i, n) 233 if (a[i] != 1 && isPrime(a[i] + 1)) { 234 printAns(cnt1, a[i]); 235 return; 236 } 237 238 if (cnt1 > 1) { 239 printAns(cnt1); 240 return; 241 } 242 243 forn(i, n) 244 forn(j, i) 245 if (isPrime(a[i] + a[j])) { 246 printAns(0, a[i], a[j]); 247 return; 248 } 249 250 printAns(0, a[0]); 251 } 252 ``` 253 254 Complexity: *O*(*n*2 + *X*), where *X* is the maximal value in *a*. 255 256 ### [665E - Beautiful Subarrays](/contest/665/problem/E "Educational Codeforces Round 12") 257 258 The problem was suggested by Zi Song Yeoh [zscoder](/profile/zscoder "Candidate Master zscoder"). 259 260 The sign  is used for the binary operation for bitwise exclusive or. 261 262 Let *s**i* be the xor of the first *i* elements on the prefix of *a*. Then the interval (*i*, *j*] is beautiful if . Let's iterate over *j* from 1 to *n* and consider the values *s**j* as the binary strings. On each iteration we should increase the answer by the value *z**j* — the number of numbers *s**i* (*i* < *j*) so . To do that we can use the [trie](https://ru.wikipedia.org/wiki/Trie) data structure. Let's store in the trie all the values *s**i* for *i* < *j*. Besides the structure of the trie we should also store in each vertex the number of leaves in the subtree of that vertex (it can be easily done during adding of each binary string). To calculate the value *z**j* let's go down by the trie from the root. Let's accumulate the value *cur* equals to the xor of the prefix of the value *s**j* with the already passed in the trie path. Let the current bit in *s**j* be equal to *b* and *i* be the depth of the current vertex in the trie. If the number *cur* + 2*i* ≥ *k* then we can increase *z**j* by the number of leaves in vertex , because all the leaves in the subtree of tha vertex correspond to the values *s**i* that for sure gives . After that we should go down in the subtree *b*. Otherwise if *cur* + 2*i* < *k* then we should simply go down to the subtree  and recalculate the value *cur* = *cur* + 2*i*. 263 264 **C++ solution** 265 266 ``` 267 const int N = 1200300, LOGN = 30, V = N * LOGN; 268 269 int n, k; 270 int a[N]; 271 272 bool read() { 273 if (!(cin >> n >> k)) return false; 274 forn(i, n) assert(scanf("%d", &a[i]) == 1); 275 return true; 276 } 277 278 int tsz; 279 int nt[V][2]; 280 int cnt[V]; 281 282 void clear() { 283 forn(i, V) { 284 nt[i][0] = nt[i][1] = -1; 285 cnt[i] = 0; 286 } 287 tsz = 1; 288 } 289 290 void add(int x) { 291 int v = 0; 292 cnt[v]++; 293 294 nfor(i, LOGN) { 295 int b = (x >> i) & 1; 296 if (nt[v][b] == -1) { 297 assert(tsz < V); 298 nt[v][b] = tsz++; 299 } 300 v = nt[v][b]; 301 cnt[v]++; 302 } 303 } 304 305 int calc(int x) { 306 int v = 0; 307 int ans = 0; 308 309 auto getCnt = [](int v) { return v == -1 ? 0 : cnt[v]; }; 310 311 int cur = 0; 312 nfor(i, LOGN) { 313 if (v == -1) break; 314 int b = (x >> i) & 1; 315 if ((cur | (1 << i)) >= k) { 316 ans += getCnt(nt[v][b ^ 1]); 317 v = nt[v][b]; 318 } else { 319 v = nt[v][b ^ 1]; 320 cur |= (1 << i); 321 } 322 } 323 if (cur >= k) ans += getCnt(v); 324 return ans; 325 } 326 327 void solve() { 328 clear(); 329 330 add(0); 331 332 li ans = 0; 333 int s = 0; 334 forn(i, n) { 335 s ^= a[i]; 336 li cur = calc(s); 337 ans += cur; 338 add(s); 339 } 340 cout << ans << endl; 341 } 342 ``` 343 344 Comlpexity by the time and the memory: *O*(*nlogX*), where *X* is the maximal xor on the prefixes. 345 346 ### [665F - Four Divisors](/contest/665/problem/F "Educational Codeforces Round 12") 347 348 The editorial for this problem is a little modification of the materials from the lecture of Mikhail Tikhomirov [Endagorion](/profile/Endagorion "International Grandmaster Endagorion") of the autumn of 2015 in Moscow Institute of Physics and Technology. Thanks a lot to [Endagorion](/profile/Endagorion "International Grandmaster Endagorion") for that materials. 349 350 Easy to see that only the numbers of the form *p*·*q* and *p*3 (for different prime *p*, *q*) have exactly four positive divisors. 351 352 We can easily count the numbers of the form *p*3 in , where *n* is the number from the problem statement. 353 354 Now let *p* < *q* and π(*k*) be the number of primes from 1 to *k*. Let's iterate over all the values *p*. Easy to see that . So for fixed *p* we should increase the answer by the value . 355 356 So the task is ot to find  — the number of primes not exceeding , for all *p*. 357 358 Denote *p**j* the *j*-th prime number. Denote *dp**n*, *j* the number of *k* such that 1 ≤ *k* ≤ *n*, and all prime divisors of *k* are at least *p**j* (note that 1 is counted in all *dp**n*, *j*, since the set of its prime divisors is empty). *dp**n*, *j* satisfy a simple recurrence: 359 360 1. *dp**n*, 1 = *n* (since *p*1 = 2) 361 2. *dp**n*, *j* = *dp**n*, *j* + 1 + *dp*⌊ *n* / *p**j*⌋, *j*, hence *dp**n*, *j* + 1 = *dp**n*, *j* - *dp*⌊ *n* / *p**j*⌋, *j* 362 363 Let *p**k* be the smallest prime greater than . Then π(*n*) = *dp**n*, *k* + *k* - 1 (by definition, the first summand accounts for all the primes not less than *k*). 364 365 If we evaluate the recurrence *dp**n*, *k* straightforwardly, all the reachable states will be of the form *dp*⌊ *n* / *i*⌋, *j*. We can also note that if *p**j* and *p**k* are both greater than , then *dp**n*, *j* + *j* = *dp**n*, *k* + *k*. Thus, for each ⌊ *n* / *i*⌋ it makes sense to keep only  values of *dp*⌊ *n* / *i*⌋, *j*. 366 367 Instead of evaluating all DP states straightforwardly, we perform a two-step process: 368 369 1. Choose *K*. 370 2. Run recursive evaluation of *dp**n*, *k*. If we want to compute a state with *n* < *K*, memorize the query ``count the numbers not exceeding *n* with all prime divisors at least *k*''. 371 3. Answer all the queries off-line: compute the sieve for numbers up to *K*, then sort all numbers by the smallest prime divisor. Now all queries can be answered using RSQ structure. Store all the answers globally. 372 4. Run recurisive evaluation of *dp**n*, *k* yet again. If we want to compute a state with *n* < *K*, then we must have preprocessed a query for this state, so take it from the global set of answers. 373 374 The performance of this approach relies heavily on *Q* — the number of queries we have to preprocess. 375 376 *Statement*. . 377 378 *Proof*: 379 380 Each state we have to preprocess is obtained by following a *dp*⌊ *n* / *p**j*⌋, *j* transition from some greater state. It follows that *Q* doesn't exceed the total number of states for *n* > *K*. 381 382  383 384 The preprocessing of *Q* queries can be done in , and it is the heaviest part of the computation. Choosing optimal , we obtain the complexity . 385 386 **C++ solution** 387 388 ``` 389 li n; 390 391 bool read() { 392 return !!(cin >> n); 393 } 394 395 const int K = 10 * 1000 * 1000; 396 const int N = K; 397 const int P = 700100; 398 const int Q = 25 * 1000 * 1000; 399 400 int szp, p[P]; 401 int mind[N]; 402 403 void prepare() { 404 szp = 0; 405 forn(i, N) mind[i] = -1; 406 fore(i, 2, N) { 407 if (mind[i] == -1) { 408 assert(szp < P); 409 mind[i] = szp; 410 p[szp++] = i; 411 } 412 for (int j = 0; j < szp && j <= mind[i] && i * p[j] < N; j++) 413 mind[i * p[j]] = j; 414 } 415 } 416 417 inline int getk(li n) { 418 int lf = 0, rg = szp - 1; 419 while (lf != rg) { 420 int md = (lf + rg) >> 1; 421 if (p[md] * 1ll * p[md] > n) rg = md; 422 else lf = md + 1; 423 } 424 assert(p[lf] * 1ll * p[lf] > n); 425 return lf; 426 } 427 428 int t[K]; 429 void inc(int i, int val) { 430 for ( ; i < K; i |= i + 1) 431 t[i] += val; 432 } 433 int sum(int i) { 434 int ans = 0; 435 for ( ; i >= 0; i = (i & (i + 1)) - 1) 436 ans += t[i]; 437 return ans; 438 } 439 440 int szq; 441 pti q[Q]; 442 int ans[Q]; 443 vector<int> vs[P]; 444 445 void process() { 446 sort(q, q + szq, greater<pti> ()); 447 memset(t, 0, sizeof(t)); 448 449 forn(i, szp) vs[i].clear(); 450 fore(i, 2, K) 451 vs[mind[i]].pb(i); 452 453 inc(1, +1); 454 455 int p = szp - 1; 456 for (int i = 0, j = 0; i < szq; i = j) { 457 while (p >= q[i].x) { 458 for (auto v : vs[p]) 459 inc(v, +1); 460 p--; 461 } 462 463 while (j < szq && q[j].x == q[i].x) { 464 ans[j] = sum(q[j].y); 465 j++; 466 } 467 } 468 } 469 470 map<pair<li, int>, li> z; 471 472 li solve(li n, int jj, bool fs) { 473 if (!n) return 0; 474 int j = min(jj, getk(n)); 475 if (!j) return n + j - jj; 476 477 li ans = 0; 478 if (n < K) { 479 pti p(j, (int) n); 480 if (fs) { 481 assert(szq < Q); 482 q[szq++] = p; 483 ans = 0; 484 return 0; 485 } else { 486 int idx = int(lower_bound(q, q + szq, p, greater<pti> ()) - q); 487 assert(idx < szq && q[idx] == p); 488 ans = ::ans[idx]; 489 } 490 } else { 491 if (!z.count(mp(n, j))) { 492 ans = solve(n, j - 1, fs); 493 ans -= solve(n / p[j - 1], j - 1, fs); 494 z[mp(n, j)] = ans; 495 } else { 496 ans = z[mp(n, j)]; 497 } 498 } 499 500 ans += j - jj; 501 502 return ans; 503 } 504 505 inline li pi(li n, bool fs) { 506 int k = szp - 1; 507 return solve(n, k, fs) + k - 1; 508 } 509 510 void solve() { 511 szq = 0; 512 z.clear(); 513 for (int j = 0; p[j] * 1ll * p[j] <= n; j++) { 514 li nn = n / p[j]; 515 if (nn > p[j]) { 516 pi(n / p[j], true); 517 } 518 } 519 520 process(); 521 522 z.clear(); 523 li ans = 0; 524 for (int j = 0; p[j] * 1ll * p[j] <= n; j++) { 525 li nn = n / p[j]; 526 if (nn > p[j]) { 527 ans += pi(n / p[j], false); 528 ans -= j + 1; 529 } 530 } 531 532 for (int i = 0; i < szp && p[i] * 1ll * p[i] * 1ll * p[i] <= n; i++) 533 ans++; 534 535 cout << ans << endl; 536 } 537 ``` 538 539 Complexity: .