895A - Pizza Separation

We can notice that if one of the sectors is continuous then all the remaining pieces also form a continuous sector.If angle of the first sector is equal to x then difference between angles of first and second sectors is |x - (360 - x)| = |2 * x - 360| = 2 * |x - 180|. So for each possible continuous sector we can count it's angle and update answer.

Time complexity O(n²) or O(n).

Solution

895B - XK Segments

First, we need to understand how to find the number of integers in [l, r] segment which are divisible by x. It is r / x–(l - 1) / x. After that we should sort array in ascending order. For each left boundary of the segment l = a[i] we need to find minimal and maximal index of good right boundaries. All right boundaries r = a[j] should satisfy the following condition a[j] / x–(a[i] - 1) / x = k. We already know (a[i] - 1) / x, a[j] / x is increasing while a[j] increases. So we can do binary search on sorted array to find minimal/maximal index of good right boundaries and that mean we can find the number of good right boundaries.

Time complexity O(n * log(n)).

Solution

895C - Square Subsets

We can notice that x is a perfect square of some integer if and only if each prime number enters decomposition of x into prime factors even times. There are only 19 prime numbers less than 70. Now we should find the bitmask for each integer in [1, 70] by the following way: There is 1 in bit representation of mask in k-th place if k-th prime number enters decomposition of that number odd times. Else there is 0. For each integer between 1 and 70 we need to find the number of ways we can take odd and even amount of it from a. Let f1[i], f0[i] be that number of ways relatively. Let dp[i][j] be the number of ways to choose some elements which are <= i from a, and their product has only those prime numbers in odd degree on whose index number j has 1 in binary representation. Initially dp[0][0] = 1.

dp[i + 1][j] +  = dp[i][j] * f0[i + 1]

The answer is dp[70][0].

Time complexity is O(max*2^cnt(max)), where max is maximal integer a[i], and cnt(max) is the number of prime numbers less than max.

Solution

895D - String Mark

Suppose that we can calculate the function f(s) equal to the number of permutations of the string a strictly less than s. Then the answer is f(b) - f(a) - 1. Now we need to understand how to find f(s). First we should count the number of occurrences of each letter in the string a, cnt[26].Than we can iterate through the position of the first different symbol in the permutation a and the string s and update the number of remaining symbols cnt[26]. For each such position, we need to iterate through the symbol in the permutation of a which will stand in this position. It must be less than the character at this position in the s string. For each such situation we can calculate and add to the answer the number of different permutations that can be obtained using symbols not currently involved. Their number is stored in cnt[26]. In its simplest form, this solution works in O(n * k²), where k is the size of the alphabet. Such a solution can't pass the tests, but it can be optimized to O(n * k), and that is enough to solve the problem.

Time complexity O(n * k), where k is the size of alphabet.

Solution

Arpa's solution

895E - Eyes Closed

For each position we need to maintain mathematical expectation of the value on it. Initially, for position i, it is a[i]. Let's process the query of the first type. Each number from the interval [l1, r1] remains on its place with probability (r1 - l1) / (r1 - l1 + 1). The probability that it will be replaced by a number from [l2, r2] is 1 / (r1 - l1 + 1). The mathematical expectation of the number to which it will be replaced is the arithmetic mean of sum of the mathematical expectation of numbers in [l2, r2], let it be x. Then, to update the expectation of a number from [l1, r1], we need to multiply it by (r1 - l1) / (r1 - l1 + 1) and add x / (r1 - l1 + 1) to it. That is, the query of the first type is reduced to the query multiplying all the numbers in a segment and adding to them a number. To process the second type query, you must find the sum of the numbers in the segment. All these queries can be processed with the help of segment tree.

Time complexity O(x + q * log(n))

Solution

Arpa's solution

Hi everyone!

Codeforces Round #448 (Div.2) takes place on 26th of November at 19:05 MSK. As usual, Div.1 participants can join out of competition.

This is my second round on Codeforces! I advise you to read all of the 5 problems. Hope everyone will find something interesting.

I'd like to thank vintage_Vlad_Makeev for coordination, igdor99 for helping me in developing problems. And, surely, thanks to Tommyr7, Arpa, 300iq for testing this round.

Of course, many thanks to MikeMirzayanov for great Codeforces and Polygon platforms.

Scoring: 500-1000-1750-2000-2250

High ratings to everybody!

UPD: Contest is finished. Editorial will be posted soon.

UPD: Editorial

Congratulations to the winners!!!

Div1

1. uwi

2. Benq

3. irkstepanov

4. dreamoon_love_AA

5. JustasK

6. eddy1021

7. yancouto

8. chemthan

9. Nephren_Ruq_Insania

10. KrK

Div2

1. Nephren_Ruq_Insania

2. Mahan_sh

3. lsrothy

4. ngfam

5. georgerapeanu

6. ZalBinHassan

7. mtkaya

8. Bodo

9. szhouan

10. fchirica

A

We know that time=distance/speed. For each car we should find time_i, than if it is less than answer we should update it.

Time Complexity: O(n).

Solution

B

Consider c[x] the number of stores in which the price per drink is x. We calculate this array prefix sum. Then the following options:

1) If the current amount of money m is larger than the size of the array with the prefix sums than answer is n.

2) Otherwise, the answer is c[m].

Time Complexity: O(n+q).

Solution

C

We will solve the problem with the help of dynamic programming. dp[i][j] is the minimum amount of energy that should be spent to make first i strings sorted in lexicographical order and i-th of them will be reversed if j = 1 and not reversed if j = 0. dp[i][j] is updated by dp[i - 1][0] and dp[i - 1][1]. It remains to verify that the i-th string is lexicographically greater than (i - 1)-th (if j = 1 then we should check reversed i-th string, similar to (i - 1)-th). Then we update dp[i][j] = min(dp[i][j], dp[i - 1][0] + c[i] * j), dp[i][j] = min(dp[i][j], dp[i - 1][1] + j * c[i]). The answer is a minimum of dp[n][0] and dp[n][1].

Time Complexity: O(n+sum_length).

Solution

D

Let's store each number in binary system (each number consists of 32 bits, 0 or 1) in such a data structure as trie.The edges will be the bits 1 and 0, and the vertices will be responsible for whether it is possible to pass the current edge. To reply to a query like "? X" will descend the forest of high-order bits to whether the younger and now we can look XOR in the i-th bit to get one, if we can, then move on, otherwise we go to where we can go.

Time Complexity: O(q*log(10^9)).

Solution

E

Let's surround the matrix with the frame of elements. In each element of the matrix, and frame we need to store value, the number of the right element and the number of down element. When a request comes we should change only values of the elements along the perimeter of rectangles.

Time Complexity: O(q*(n+m)).

Solution

Hi everyone!

Codeforces Round #367 (Div.2) takes place on 11th of August at 19:35 MSK. As usual, Div.1 participants can join out of competition.

This is my first round on Codeforces! I advise you to read all the problems. Hope everyone will find something interesting.

I'd like to thank GlebsHP for helping me in preparing this round, Yury_Bandarchuk and IvanVan for testing tasks. Of course, many thanks to MikeMirzayanov for great Codeforces and Polygon platforms.

UPD: Scoring is 500-1000-1500-2000-2500

UPD: Editorial

UPD: The contest is over. Congratulations to the winners!

Div.1 winners:

1.anta

2.W4yneb0t

3.sugim48

4.uwi

5.Kmcode

Div.2 winners:

1.jiangzixiao

2.Shining

3.BurningHuie

4.AwD

5.stjepanp