При написании сегодняшнего Codeforces Round #126 и решении задачи A столкнулся с несколько неожиданными поведением. А именно при использовании двумерных массивов размера 2048 x 2048 скорость доступа к данным оказалась на порядок хуже, чем скорость доступа в случае массивов 2048 x 2047 (или 2048 x 2049, или ещё какого-то другого размера) (см. посылки 1829297 и 1830397). Данное поведение оказалось для меня весьма неожиданным (казалось бы наоборот выравнивание данных должно было ускорить доступ). Посему возник вопрос, почему же оно медленее?

Для начала немного переформулируем нашу задачу. Рассмотрим, что значит то, что активировались все сферы. Это значит что если мы спроецируем все сферы на плоскость, то у них всех будет общая точка. В силу того, что проекцией сферы на плоскость является окружность, то наша задача состоит в нахождении минимального радиуса окружности такого, что все окружности имеют общую точку.

Будем отвечать на каждый запрос отдельно. Для ответа на запрос будем делать следующее:

1) Спроецируем все точки на плоскость.

2) Выполним преобразование поворота к плоскости, так чтобы она стала Oxy.

Итого мы получили следующую задачу:

Имеется N точек на плоскости и необходимо найти такой минимальный радиус окружности, чтобы окружности построенные вокруг заданных точек имели общую точку. Пускай мы нашли радиус R и общую точку (x₀, y₀). Тогда рассмотрим окружность построенную в точке (x₀, y₀), радуиса R. Заметим, она покрывает N исходных точек. Аналогично рассмотрев некоторое покрытие исходных точек при помощи какой-то окружности, получаем окружности имеющие общую точку. Т.е. задача минимизации R в данной задаче эквивалентна задаче нахождения минимальной покрывающей окружности. Научимся эффективно решать эту задачу в силу того, что очевидный алгоритм решения данной задачи приводит к решению за O(N⁴M), что очевидно не подходит для данных ограничений.

Рандомизированный алгоритм за O(N).

Не нарушая общности считаем что точек более чем одна. Перемешаем имеющиеся точки случайным образом после чего будем делать слещующее:

1) Выберем две произвольные точки и построим на них окружность как на диаметре. Будем идти по точкам. Если точка лежит внутри окружности, то ничего не меняем. Если же точка лежит вне окружности, то значит среди уже рассмотренных точек она должна быть на покрывающей окружности (в силу того что не лежит внутри покрывающей предыдущие). А тогда переходим к 2.

2) Необходимо найти минимальную покрывающую окружность с одной фиксированной точкой. Для этого перемешаем точки рассмотренные в 1 и поступим аналогично пункту 1. Т.е. вначале построим произвольную на окружность на фиксированной точке и некоторой произвольной из остальных. И будем рассматривать остальные. В итоге мы получим или что мы нашли ответ, или нам надо найти окружность с уже зафиксированными двумя точками. Т.е. переходим к 3.

3)   Необходимо найти минимальную покрывающую окружность с двумя фиксированной точкой. Для этого перемешаем точки рассмотренные в 2 и поступим аналогично пункту 1. Т.е. вначале построим окружность на фиксированных точках и будем рассматривать остальные. В итоге мы получим или что мы нашли ответ, или нам надо найти окружность на каких-то трёх точках. А данную окружность уже можно найти за О(1).

Выполнив все действия указанные выше мы найдем минимальную покрывающую окружность.

Нетрудно показать, что ожидаемая сложность алгортима - O(N). А значит сложность решения   - O(NM).  

Но в силу того что данный алгоритм, не может являтся авторским решением в силу того что не гарантирует решения задачи в указанное время рассмотрим следующий алгоритм.

Детерминированный алгоритм за O(N²).

Для простоты будем считать, что все точки различны. Если точка всего одна, то ответ - очевиден радиус 0 достигается в самой точке.

В противном случае делаем следующее:

1) Выберем произвольную точку C и положим радиус R окружности описанной в данной точке равным бесконечности. Очевидно, что это не оптимальное решение, и можно сделать нашу окружность меньше выбрав радиус равным расстоянием до самой удалённой точки.

2) После выбора такого радуиса у нас возможны следующие две ситуации:

a) На окружности есть хотя бы две точки. Тогда перейдем к шагу 3.

b) На окружности находится ровно одна точка. В таком случае будем двигать центр окружности уменьшая радиус пока на окружности не окажется ровно две точки (а такой момент наступит).

3) Рассмотрим окружность C и точки которые лежат на ней.

a) На ней есть дуга опирающая на угол больше чем π (пусть у неё концевые точки D и E), то окружность можно сделать меньше двигая её центр в направлении середины отрезка DE и уменьшая радиус окружности, пока на этой дуге не появится точка или же мы не получим, окружность у которой DE  - диаметр. Повторим 3) ещё раз.

b) Любая из дуг опирается на угол не больше чем π. А тогда мы нашли ответ в силу того что куда бы мы не двигали центр радиус будет только увеличиваться и т.к. функция радиуса   выпукла.

Заметим, что все 1), 2), 3) выполняются за линейное время. При этом нетрудно показать, что итераций 3) будет не больше чем N - 2, а тогда общее время работы - O(N²). Или же для исходной задачи:   O(MN²)  

В данный момент я учавствую в разработке одного проекта, где необходима возможность запуска пользовательского кода на стороне сервера (вообще говоря написанного на различных языках программирования). В связи с этим возник вопрос  —  как лучше всего реалиовать данный функционал, чтобы не иметь с ним проблем. В частности интересны следующие аспекты:

1. Обеспечение безопасности сервера (не будем забывать, что недобросовестных пользователей это прямо открытая возможно собрать и запустить вирус/эксплоит прямо на сервере).
2. Обеспечение достаточной производительности, а также введение некоторых ограничений на  исполняемый код (например ограничения на используемую память для процесса и т.п.)
3. О других возможных проблемах.

Вот такой вопрос.

PS: Было бы очень интересно услышать мнение и советы тех кто делал что-либо подбное/администрации данного ресурса (при условии что это не является комерческой тайной =) ).