Editorial of Educational Codeforces Round 16

Правка en1, от Edvard, 2016-08-29 23:57:58

710A - King Moves

Easy to see that there are only three cases in this problem. If the king is in the corner of the board the answer is 3. If the king is on the border of the board but not in a corner than the answer is 5. Otherwise the answer is 8.

С++ solution

Complexity: O(1).

710B - Optimal Point on a Line

The function of the total distance is monotonic between any pair of adjacent points from the input, so the answer is always in some of the given points. We can use that observation to solve the problem by calculating the total distance for each point from the input and finding the optimal point.

The other solution uses the observation that the answer is always is the middle point (by index) in the sorted list of the given points. The last fact is also can be easily proven.

C++ solution

Complexity: O(nlogn).

Теги educational round 16, editorial

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en6 Английский Edvard 2016-08-30 01:56:47 4835
en5 Английский Edvard 2016-08-30 01:11:02 1545
en4 Английский Edvard 2016-08-30 00:41:38 1965
en3 Английский Edvard 2016-08-30 00:04:38 2 Tiny change: 'ncorner than the answ' -> 'ncorner then the answ'
en2 Английский Edvard 2016-08-30 00:03:23 945
en1 Английский Edvard 2016-08-29 23:57:58 1839 Initial revision for English translation
ru4 Русский Edvard 2016-08-25 01:51:17 4900 Мелкая правка: 'ность: $O(slen\cdot logm)$, гд' -
ru3 Русский Edvard 2016-08-25 01:37:55 1633
ru2 Русский Edvard 2016-08-25 01:24:39 1967 Мелкая правка: 'уравнение получается решается ' -> 'уравнение решается '
ru1 Русский Edvard 2016-08-25 01:08:13 2829 Первая редакция (опубликовано)