Codeforces Round #340 (Div. 2) Editorial
Difference between en4 and ru1, changed 3,000 character(s)
It's first version of editorial. I will try to expand it and correct mistakes.↵
↵
[problem:617A]↵
↵
It's optimal to do the biggest possible step everytime. So elephant should↵
do several steps by distance 5 and one or zero step by smaller distance.↵
Answer equals to[problem:617A]↵
↵
Оптимально делать наибольший возможный шаг каждый раз. Поэтому слоник должен сделать сначала некоторое количество шагов на расстояние 5, а затем один или ноль шагов на меньшее расстояние. Следовательно, ответ равен $\lceil\frac{x}{5}\rceil$.↵
↵
[SolutionРешение](http://pastebin.com/eqrUdgxv)↵
↵
[problem:617B]↵
↵
We are given array which contains only ones and zeroes. We must divide it on parts with only one 1.↵
↵
Tricky case: when array contains only zeroes answer equals to 0.↵
↵
In general. Between two adjacent ones we must have only one separation.↵
So, answer equals to product of values $pos_i - pos_{i - 1}$ where $pos_i$ is position of i-th one.↵
↵
Bonus: what's the maximal possible answer forНам дан массив, состоящий только из нулей и единиц. Мы должны разделить его на части, в каждой из которых ровно одна единица.↵
↵
Особый случай: когда массив состоит только из нулей ответ равен нулю.↵
↵
Рассмотрим общий случай. Во-первых нули на префиксе относятся к первому куску, нули на суффиксе относятся ко второму куску. Во-вторых, между каждой парой соседних единиц должно быть одно и только одно разделение частей. Между соседними единицами с индексами $a < b$ всего $b - a$ вариантов разделения. Поэтому мы должны перемножить эти значения для всех пар соседних единиц.↵
↵
Бонус: каким является максимальный ответ при $n \leq 100$?↵
↵
[SolutionРешение](http://pastebin.com/LVtFbLKt)↵
↵
[problem:617C]↵
↵
First radius equals to zero or distance from first fountain to some flower.↵
Let's iterate over this numbers. Second radius equals to maximal distance from second fountain to flower↵
which doesn't belong to circle with first radius. Now we should choose variant with minimalПервый радиус равен нулю или расстоянию от первого фонтана до какого-то цветка. Переберем все эти числа. Второй радиус будет равен максимальному из расстояний от второго фонтана до цветка, который не принадлежит кругу с первым радиусом. Теперь мы должны выбрать вариант с минимальным $r_1^2 + r_2^2$.↵
↵
Bonus: It's $O(n^2)$ solution. Can you solve problem inБонус: Я описал решение за $O(n^2)$. Можете ли вы решить задачу за $O(n log n$)?↵
↵
[SolutionРешение O(n^2)](http://pastebin.com/cXrpikpT)↵
↵
[SolutionРешение O(nlogn)](http://pastebin.com/aMKZyQm1)↵
↵
[problem:617D]↵
↵
Answer equals to one if all coordinates x or y of points are same.↵
↵
When answer equals to two? Let's iterate over all pairs of points.↵
Let first point in pair is beginning of polyline, second point is end.↵
Only one or two such polylines with answer two exist. If third point is on the polyline↵
it belongs to rectangle with corners in first two points. We can just check it.↵
↵
Else answer equals to three. We can build vertical lines which contains the most left↵
and the most right point and horizontal line through third point. If we↵
erase some excess rays we will get polyline.↵
↵
[SolutionОтвет равен одному, когда все координаты x или все координаты y совпадают.↵
↵
Когда ответ равен двум? Переберем все пары точек. Пусть первая точка является началом ломаной, вторая концом ломаной. Только одна или две таких ломаных с двумя звеньями существуют. Они образуют прямоугольник с противоположными углами в первой и второй точке. Мы можем просто проверить принадлежность третьей точки прямоугольнику.↵
↵
Иначе ответ всегда равен трем. Давайте построим вертикальные прямые через самую левую и через самую правую точки. Через третью точку построим горизонтальную прямую. Теперь, если мы удалим некоторые лишние лучи, получим подходящую ломаную.↵
↵
[Решение](http://pastebin.com/BGFK1wxd)↵
↵
[problem:617E]↵
↵
We have arrayУ нас есть массив $a$.↵
↵
Let's calculate array $Давайте посчитаем массив $\relax pref$ ($\relax pref[0] = 0$, $pref[i] = pref[i - 1] \oplus a[i]$).↵
↵
Xor of subarray $подмассива $\relax a[l...r]$ equals toравен $pref[l - 1] \oplus pref[r]$.↵
↵
So query (l, r) is counting number of pairsТеперь запрос (l, r) заключается в подсчете количества пар $i$, $j$ ($\relax l - 1 \leq i < j \leq r$) $pref[i] \oplus pref[j] = k$.↵
↵
Let we know answer for query (l, r) and know for allПусть мы знаем ответ на запрос (l, r) и знаем для всех $v$ $cnt[v]$ &mdash; count of $v$ in $a[l-1...r]$.↵
We can update in O(1) answer and $cnt$ if we move left or right border of query on 1.↵
So we can solve problem offline in $O((n + m)\sqrt{n})$ with sqrt-decomposion (Mo's algorithm).↵
↵
[Solutionколичество вхождений $v$ в $\relax a[l-1...r]$.↵
↵
Мы можем обновить за $O(1)$ ответ и $cnt$ если мы изменим правую или левую границу запроса на 1.↵
↵
Поэтому мы можем решить задачу оффлайн за $O((n + m)\sqrt{n})$ с помощью корневой эвристики (алгоритм Мо).↵
↵
[Решение](http://pastebin.com/qggQDEu2)

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
ru2 Russian komendart 2016-01-24 11:57:00 289
en5 English komendart 2016-01-24 11:51:18 363 Tiny change: 'wer for $n[Solution]$?\n\nSolu' - 100$?\n\nSolu'
ru1 Russian komendart 2016-01-24 11:38:19 3000 Первая редакция перевода на Русский
en4 English komendart 2016-01-23 21:17:57 274 Tiny change: 'XrpikpT)\n[Solutio' -
en3 English komendart 2016-01-23 21:00:09 23 Tiny change: ' expand it.\n\n[prob' - (published)
en2 English komendart 2016-01-23 20:56:47 230 Tiny change: 'uals to $\ceil{x/5}$' -
en1 English komendart 2016-01-23 20:41:01 2204 Initial revision (saved to drafts)