Codeforces Round #367 (Editorial)

Revision en1, by NBAH, 2016-08-11 23:45:01

## 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).

## 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 \$n4. 2) Otherwise, the answer is c[m].

Time Complexity: O(n+q).

## 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).

## 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 RRF 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)).

## E

Обнесем матрицу рамкой из фиктивных элементов. В каждом элементе матрицы и рамки храним значение элемента номер элемента соседнего справа и номер элемента соседнего слева. Когда приходит запрос поменять местами прямоугольники надо поменять значения элементов только по периметру прямоугольников.

Асимптотика O(q*(n+m)).

#### History

Revisions

Rev. Lang. By When Δ Comment
ru7 NBAH 2016-08-12 14:14:05 49
ru6 NBAH 2016-08-12 14:13:31 192
en7 NBAH 2016-08-12 14:10:10 241
ru5 NBAH 2016-08-12 14:01:30 340
en6 NBAH 2016-08-12 14:00:03 345
ru4 NBAH 2016-08-12 11:17:18 60
ru3 NBAH 2016-08-12 11:15:17 6
en5 NBAH 2016-08-12 11:13:36 4
en4 NBAH 2016-08-12 11:13:14 54
en3 NBAH 2016-08-12 11:07:57 4 Tiny change: ' can look RRF in the i-' -> ' can look XOR in the i-'
ru2 NBAH 2016-08-11 23:50:55 8 Мелкая правка: 'оседнего слева. Когда пр' -> 'оседнего снизу. Когда пр'
en2 NBAH 2016-08-11 23:50:19 541 (published)
en1 NBAH 2016-08-11 23:45:01 2129 Initial revision for English translation (saved to drafts)
ru1 NBAH 2016-08-11 22:31:18 2288 Первая редакция (опубликовано)