Потому что в таком виде с ними боролись участники конференции и потому что английский был официальным языком Гидры. Выглядели задачки так:

Начало в 5:53, всего 4 минуты:

А вот как питчили своё решение те самые ребята с флипчартом:

На поверхности лежит такое решение: просуммировать веса всех реплик, сгенерировать случайное число от 0 до суммы всех весов, затем выбрать такую i-реплику, что сумма весов реплик от 0 до (i-1)-ой меньше случайного числа, а сумма весов реплик от 0 до i-ой — больше него. Так получится выбрать одну реплику, а чтобы выбрать следующую, нужно повторить всю процедуру, не рассматривая выбранную реплику. С таким алгоритмом сложность выбора одной реплики — O(N), сложность выбора K реплик — O(N·K) ~ O(N²).

Квадратичная сложность — это плохо, однако её можно улучшить. Для этого построим дерево отрезков ^[3] для сумм весов. Получится дерево глубиной lg N, в листьях которого будут веса реплик, а в остальных узлах — частичные суммы, вплоть до суммы всех весов в корне дерева. Далее генерируем случайное число от 0 до суммы всех весов, находим i-ую реплику, удаляем её из дерева и повторяем процедуру для поиска оставшихся реплик. С таким алгоритмом сложность построения дерева — О(N), сложность поиска i-ой реплики и удаления её из дерева — O(lg N), сложность выбора K реплик — O(N + K lg N) ~ O(N lg N).

Линейно-логарифмическая сложность приятнее квадратичной, особенно для больших K.

Именно этот алгоритм реализован в коде ^[4] библиотеки ClusterClient из проекта «Восток ^[5]». (Там дерево строится за O(N lg N), но на итоговую сложность алгоритма это не влияет.)

Начало в 34:50, всего 6 минут:

Решение на поверхности: отсортировать все документы (например, с помощью quicksort ^[6]), затем взять N+S документов. В таком случае сложность сортировки в среднем — O(M lg M), в худшем — O(M²).

Очевидно, что сортировать все M документов, чтобы затем взять только небольшую часть от них — неэффективно. Чтобы не сортировать все документы, подойдёт алгоритм quickselect ^[7], который выберет N+S нужных документов (их можно будет отсортировать любым алгоритмом). В этом случае сложность в среднем уменьшится до O(M), а худший случай останется тем же.

Однако, можно сделать ещё эффективнее — воспользоваться алгоритмом binary heap streaming ^[8]. В этом случае первые N+S документов складываются в min- или max-heap (в зависимости от направления сортировки), а затем каждый следующий документ сравнивается с корнем дерева, где содержится минимальный или максимальный на текущий момент документ, и при необходимости добавляется в дерево. В этом случае сложность в худшем случае, когда придётся постоянно перестраивать дерево — O(N lg N), сложность в среднем — O(N), как и при использовании quickselect.

Однако heap streaming оказывается эффективнее за счёт того, что на практике большую часть документов получается отбросить, не перестраивая кучу, после единственного сравнения с её корневым элементом. Такая сортировка реализована в документной in-memory базе данных Zebra, разработанной и используемой в Контуре.

Решение на поверхности: обменять состояния первого и второго элемента, затем первого и третьего, затем первого и четвёртого и так далее. После каждого обмена состояние одного элемента будет оказываться на нужной позиции. Придётся сделать O(N) перестановок и потратить O(N·M) времени.

Линейное время — это долго, поэтому можно обменивать состояния элементов попарно: первого со вторым, третьего с четвёртым и так далее. После каждого обмена состояния каждого второго элемента будет оказываться на нужной позиции. Придётся сделать O(lg N) перестановок и потратить O(M lg N) времени.

Однако, можно сделать сдвиг ещё эффективнее — не за линейное, а за константное время. Для этого на первом шаге нужно обменять состояние первого элемента с последним, второго с предпоследним и так далее. Состояние последнего элемента окажется на нужной позиции. А теперь нужно обменять состояние второго элемента с последним, третьего с предпоследним и так далее. После этого раунда обменов состояния всех элементов окажутся на нужной позиции. Всего будет сделано O(2M) ~ O(1) перестановок.

Такое решение совершенно не удивит математика, который ещё помнит, что поворот — это композиция двух осевых симметрий. Кстати, оно тривиально обобщается для сдвига не на одну, а на K < N позиций. (Напишите в комментариях, как именно.)