Editorial of Educational Codeforces Round 16

Revision en1, by 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).

Tags educational round 16, editorial

History

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