Editorial of Educational Codeforces Round 12

665A - Buses Between Cities

The problem was suggested by Sergey Erlikh unprost.

Consider the time interval when Simion will be on the road strictly between cities (x1, y1) (x1 = 60h + m, y1 = x1 + ta). Let's iterate over the oncoming buses. Let (x2, y2) be the time interval when the oncoming bus will be strictly between two cities. If the intersection of that intervals (x = max(x1, x2), y = min(y1, y2)) is not empty than Simion will count that bus.

Complexity: O(1).

665B - Shopping

The problem was suggested by Ayush Anand JeanValjean01.

In this problem you should simply do what was written in the problem statement. There are no tricks.

Complexity: O(nmk).

665C - Simple Strings

The problem was suggested by Zi Song Yeoh zscoder.

There are two ways to solve this problem: greedy approach and dynamic programming.

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.

The second approach: Let zka 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.

Complexity: O(n).

665D - Simple Subset

The problem was suggested by Zi Song Yeoh zscoder.

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.

We can simply process the first case in O(n2) time. The second case can be processed in linear time. Also we should choose the best answer from that two.

To check the value of order 2·106 for primality in O(1) time we can use the simple or the linear Eratosthenes sieve.

Complexity: O(n2 + X), where X is the maximal value in a.

665E - Beautiful Subarrays

The problem was suggested by Zi Song Yeoh zscoder.

The sign is used for the binary operation for bitwise exclusive or.

Let si 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 sj as the binary strings. On each iteration we should increase the answer by the value zj — the number of numbers si (i < j) so . To do that we can use the trie data structure. Let's store in the trie all the values si 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 zj 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 sj with the already passed in the trie path. Let the current bit in sj be equal to b and i be the depth of the current vertex in the trie. If the number cur + 2i ≥ k then we can increase zj by the number of leaves in vertex , because all the leaves in the subtree of tha vertex correspond to the values si that for sure gives . After that we should go down in the subtree b. Otherwise if cur + 2i < k then we should simply go down to the subtree and recalculate the value cur = cur + 2i.

Comlpexity by the time and the memory: O(nlogX), where X is the maximal xor on the prefixes.

665F - Four Divisors

The editorial for this problem is a little modification of the materials from the lecture of Mikhail Tikhomirov Endagorion of the autumn of 2015 in Moscow Institute of Physics and Technology. Thanks a lot to Endagorion for that materials.

Easy to see that only the numbers of the form p·q and p3 (for different prime p, q) have exactly four positive divisors.

We can easily count the numbers of the form p3 in , where n is the number from the problem statement.

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 .

So the task is ot to find — the number of primes not exceeding , for all p.

Denote pj the j-th prime number. Denote dpn, j the number of k such that 1 ≤ k ≤ n, and all prime divisors of k are at least pj (note that 1 is counted in all dpn, j, since the set of its prime divisors is empty). dpn, j satisfy a simple recurrence:

1. dpn, 1 = n (since p1 = 2)

2. dpn, j = dpn, j + 1 + dp⌊ n / pj⌋, j, hence dpn, j + 1 = dpn, j - dp⌊ n / pj⌋, j

Let pk be the smallest prime greater than . Then π(n) = dpn, k + k - 1 (by definition, the first summand accounts for all the primes not less than k).

If we evaluate the recurrence dpn, k straightforwardly, all the reachable states will be of the form dp⌊ n / i⌋, j. We can also note that if pj and pk are both greater than , then dpn, j + j = dpn, k + k. Thus, for each ⌊ n / i⌋ it makes sense to keep only values of dp⌊ n / i⌋, j.

Instead of evaluating all DP states straightforwardly, we perform a two-step process:

1. Choose K.

2. Run recursive evaluation of dpn, 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''.

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.

4. Run recurisive evaluation of dpn, 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.

The performance of this approach relies heavily on Q — the number of queries we have to preprocess.

Statement. .

Proof:

Each state we have to preprocess is obtained by following a dp⌊ n / pj⌋, j transition from some greater state. It follows that Q doesn't exceed the total number of states for n > K.

The preprocessing of Q queries can be done in , and it is the heaviest part of the computation. Choosing optimal , we obtain the complexity .

Complexity: .