codeforces-scrape

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

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 ![](https://espresso.codeforces.com/8841216dfdaa642aa0c0db509a3e75f55f32d890.png) 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 ![](https://espresso.codeforces.com/72166555a6db55785fc6fbe9a7c5bbe72be28db8.png) 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 ![](https://espresso.codeforces.com/411e143ca91d407a0ad77451d139684eb7a50a3b.png). 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 ![](https://espresso.codeforces.com/411e143ca91d407a0ad77451d139684eb7a50a3b.png). 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 ![](https://espresso.codeforces.com/8ba76b8ad2f610e07f595f49ca7ae1e951b79f45.png), because all the leaves in the subtree of tha vertex correspond to the values *s**i* that for sure gives ![](https://espresso.codeforces.com/411e143ca91d407a0ad77451d139684eb7a50a3b.png). 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 ![](https://espresso.codeforces.com/31c76bcf902bb3c7c000aa7ade771740fa51daff.png) 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 ![](https://espresso.codeforces.com/7acd26c81b1f055b12a3b1e53f7a9814fd517a81.png), 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 ![](https://espresso.codeforces.com/a2d33a6ed65c92067764bc76e8175e0aaf22497c.png). So for fixed *p* we should increase the answer by the value ![](https://espresso.codeforces.com/b64f8c1048622423a75385f56f8277d697b76560.png).
    355 
    356 So the task is ot to find ![](https://espresso.codeforces.com/b64f8c1048622423a75385f56f8277d697b76560.png) — the number of primes not exceeding ![](https://espresso.codeforces.com/0d34d6dfbd337b21e577dffcaf6e8d7d2c832388.png), 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 ![](https://espresso.codeforces.com/712f9a224d6c7824add37b6cd766c21f73a40d59.png). 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 ![](https://espresso.codeforces.com/712f9a224d6c7824add37b6cd766c21f73a40d59.png), then *dp**n*, *j* + *j* = *dp**n*, *k* + *k*. Thus, for each ⌊ *n* / *i*⌋ it makes sense to keep only ![](https://espresso.codeforces.com/a32a2f71941860c0d01511a979df0f1ef9de0323.png) 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*. ![](https://espresso.codeforces.com/762b66e17f1f8aa6b2f9cf73e0e26c2e1fe6655d.png).
    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 ![](https://espresso.codeforces.com/fc4fb4d21fd2ca866afc910d7b8882e403851ea3.png)
    383 
    384 The preprocessing of *Q* queries can be done in ![](https://espresso.codeforces.com/bae8ddfa068b64658fd25118f4396f2cf5a389e6.png), and it is the heaviest part of the computation. Choosing optimal ![](https://espresso.codeforces.com/f3b75e5f5e4a4fcd8ea73f701c4663606a2c32ef.png), we obtain the complexity ![](https://espresso.codeforces.com/cc7074dfac41a8cb3e43bad8fbaa7638ece8772c.png).
    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: ![](https://espresso.codeforces.com/cc7074dfac41a8cb3e43bad8fbaa7638ece8772c.png).