Codeforces Round #367 (Editorial)

A

We know that time=distance/speed. For each car we should find timei, 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