Блог пользователя Kenny_HORROR

Автор Kenny_HORROR, 12 лет назад, По-русски

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

Полный текст и комментарии »

  • Проголосовать: нравится
  • +58
  • Проголосовать: не нравится

Автор Kenny_HORROR, 13 лет назад, По-русски

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Полный текст и комментарии »

Разбор задач Codeforces Beta Round 90
  • Проголосовать: нравится
  • +18
  • Проголосовать: не нравится

Автор Kenny_HORROR, 13 лет назад, По-русски

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

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

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

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

Полный текст и комментарии »

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

Автор Kenny_HORROR, 13 лет назад, По-русски
Div 2. Задача А. Cifera
Если переформулировать задачу то необходимо было определить является ли число l, некоторой положительной степенью числа  k. Для этого можно делать одно из двух:
1) В 64-битном типе данных найти минимальную степень h числа k, такую что kh ≥ l. Если kh = l, то ответ YES, и число артиклей - h - 1, иначе NO.
2) Будем делить l на k, пока l делится на k и l ≠ 1. Если l = 1, то ответ - YES и число делений-1, иначе ответ NO.

Div 2. Задача B. PFAST Inc.
Задачу можно понимать следующим образом:
Дан граф, необходимо найти в нем клику наибольшего размера. Если взглянуть на ограничения n ≤ 16, то можно понять, что искомое подмножество вершин можно просто перебрать. Что мы и сделаем. Для удобства перебора можно воспользоваться бит. масками и просто перебрать до 216 чисел проверяя получаемый граф на то является ли он кликой. Единственное что остается - не забыть отсортировать имена при вводе.

Div 1. Задача A. Grammar Lessons
Данная задача скорее на аккуратную реализацию.
Половиной решения задачи является внимательное чтение условия. А именно - необходимо проверить набор слов который нам дается, на то  —  является ли он предложением в заданном нам языке. По условию корректным предложением является - 1 слово из нашей грамматики или же структура вида:
{ноль или несколько прилагательных} существительное {ноль или несколько глаголов}
Собственно авторское решение делало следующее:
Считаем все слова - если оно одно, то проверяем относится ли он к грамматике, иначе узнаем из первого слова - род. А дальше идем по всем словам проверяя, чтобы было согласование рода, наличие ровно 1 существительного, а также соблюдения порядка данного в условии.

Div 1. Задача B. Petr#
Данная задача имеет несколько решений. Начну с самого простого (правда которое с некоторой вероятностью можно взломать).
Первое решение. Посчитаем хеш-функцию от нашей строки. Тогда мы получаем возможность сравнивать подстроки за O(1). Далее пройдемся по всем позициям строки и найдем те в которых может начинаться begin, после чего для данной позиции найдем все подходящие позиции end которые подходят для данного begin, используя сравнение строк через хеши, после чего посчитаем число различных значений хеш-функции которые мы смогли получить (можно например используя массив для запоминания полученных хешей и сортировкой оного). Сложность - O(N2 Log N). Однако можно сделать более аккуратно, уменьшив вероятность коллизий. Для этого сначала найдем все возможные позиции начал, а после этого будем перебирать длину искомой подстроки и считать число уникальных хешей данной длины. Заметим что при этом мы все равно каждую подстроку переберем ровно 1 раз, однако коллизии будут возможно только между строками одной длинны, что менее вероятно, чем когда мы рассматриваем все строки.

Второе решение. В лоб найдем все возможные позиции начал и концов. После чего отобразим данную строку в число 0. После этого будем добавлять по 1 символу к имеющимся строкам и перенумеровывать строки данной длинны, т.е. уже строить для строк длины на 1 больше опять же отображения в целые неотрицательные числа. Заметим, что при этом у нас не будет никогда возникать более чем 2000 различных строк, поэтому мы их сможем спокойно перенумеровывать. Теперь учитывая, что мы знаем все концы строк, и различным строкам одной длины соответствуют разные числа, а одинаковым одинаковые, то мы без труда можем посчитать число различных подстрок указанной длины точно. Касательно сложности - O(N2 Log N), в силу того что всего у нас N итераций каждая из которых выполняется за время O(N Log N).

Третье решение. Используя суффиксный массив данную задачу можно решить за время O(N Log N). Построим суффиксный массив с LCP за O(N Log N). Далее найдем все вхождения строки end в нашу строку и запомним эти вхождения в отсортированном порядке в некотором массиве. Будем рассматривать последовательно наши суффиксы которые начинаются со строки begin (первое и последнее вхождение ищутся достаточно просто). Для начала рассмотрим первый суффикс который начинается с со строки begin. Для него любая строка закачивающаяся на end и такая что её длина больше чем max(|begin|, |end|) является искомой подстрокой, причем найти такую позицию строки end мы можем используя дихотомию по заранее посчитанному массиву вхождений концов (и тогда очевидным образом получаем сколько строк нам подходят). Рассмотрим следующий суффикс. Заметим что для следующего суффикса любая строка которая которая закачивается на расстоянии не больше чем LCP(i, i - 1) от начала строки (где i номер текущего суффикса), будет совпадать с некоторой подстрокой предыдущего суффикса, т.е. её мы посчитали. А любая строка заканчивающаяся после LCP(i, i - 1) (где i номер текущего суффикса) будет лексикографически больше любой рассмотренной ранее подстроки, а значит любое такое вхождение  —  новая подстрока. Используя дихотомию найдем в массиве концов - первый подходящий. Таким образом мы посчитали число различных подстрок в данных двух суффиксах. Продолжим делать таким образом пока не рассмотрим все суффиксы начинающиеся со строки begin. Таким образом мы получили ответ.
Теперь оценим сложность. На построение суффиксного массива мы потратили время O(N Log N). Построение массива концов - делается за O(N). Всего начал - не более чем N и при этом на каждой итерации мы тратим время O(Log N). Т.е. итоговая сложность O(N Log N).

Div. 1. Задача C. Double Happiness
В задаче необходимо было найти число простых чисел представимых в виде суммы двух квадратов натуральных чисел. Очевидно, что простые вида 4k + 3, не подходят, т.к. сумма двух квадратов не может быть сравнима с 3 по модулю 4. Что же касается простых вида 4k + 1, то можно доказать (ну а вообще это достаточно известный факт), что любое просто такого вида представимо в виде суммы двух квадратов натуральных чисел. Также необходимо не забыть про 2. Теперь касательно того как всё это можно сдать в систему. Очевидно, что совсем тупо писать решето Эратосфена не проходит по памяти, однако можно использовать блочное решето Эратосфена, которое работает за те же O(N Log Log N), однако использует в разы меньше памяти например . Помимо этого можно было использовать препросчет, и сократить объем работы до куска который влазит в память. Также участник Romka воспользовался идеей, что можно используя bit-mask уменьшить объем необходимой памяти для всего решета в 8 раз, что отлично влезло в ML. Так же неплохо при написании решета рассматривать, только нечетные числа.

Div. 1. Задача D. Museum
Для начала избавимся от того что у нас есть 2 человека, каждый из которых переходит в некоторую вершину. Для этого сделаем состоянием пару чисел (i, j) - которая обозначает, что Петя находится в комнате с номером i, а Вася в комнате с номером j. Тогда встрече в комнате i будет соответствовать состояние (i, i). Тогда исходя из этих данных несложно построить матрицу переходов - т.е. матрицу в которой для каждого состояния (i, j), известна вероятность перехода в состояние (x, y), где 1 ≤ i, j, x, y ≤ n. Так же понятно, что из состояния встречи мы переходим в это же состояние.
Теперь рассмотрим как решить данную задачу. Если бы нам было необходимо просто посчитать вероятность встречи в первой комнате, то можно было бы сделать следующим образом: построим систему линейных алгебраических уравнений:
, где a(i, j), (x, y) —  вероятность перехода из состояния (i,j) в состояние (x,y). При этом p(1, 1) = 1, а p(i, i) = 0 при i ≠ 1. При этом нас интересует p(a, b).
Данная СЛАУ легко решается методом Гаусса. Аналогичным образом можно решить для оставшихся вершин, однако при этом сложность выходит O(n7), что при данных ограничениях нас не очень устраивает. Однако можно заметить, что мы каждый раз решаем одну и ту же СЛАУ Ax = b (при условии, что у нас в матрице , единственное что меняется  —  вектор b), поэтому можно построить LU-разложение и пользуясь им получить сложность O(n6), однако можно не строить LU-разложения, просто решать матричное уравнение где b - матрица размерности n2 * n, а ответом является значение получившееся в строке соответствующей состоянию (a, b). При этом нетрудно видеть, что сложность получается опять же O(n6). Кроме этого можно решить задачу просто выразив все состояния через переменные соответствующие состояниям встреч.

Div. 1. Задача E. Sleeping
Введем функцию F(x) (где x - некоторый момент времени)  —  число моментов времени от 00..00:00..00 до x (т.е. x не переключается на следующий момент времени) когда сменится не менее чем k цифр. Тогда интересующим нас ответом будет являться F(h2: m2) - F(h1: m1), при этом мы учитываем что если h2: m2 < h1: m1, то F(h2: m2) будет на сутки больше.
Теперь научимся считать функцию F(x). Для начала посчитаем сколько наступит таких моментов без смены часа. Т.к. час у нас не меняется, то значит в минуте у нас должно поменяться не менее чем k цифр, но для того чтобы в числе поменялось не менее чем k цифр, необходимо, что наше число имело вид:
a..a99...9, где a - произвольные цифры, а на конце - k-1 девятка. Т.е. k цифр меняются каждое число кратное 10k - 1.
А значит в моменты в которые не меняется час у нас случилось таких событий , где hx и mx - число часов и минут в момент времени x, а [] - целая часть.
Теперь рассмотрим моменты когда меняется час. Если меняется час значит минут переходят из m - 1 в 0, и поэтому у нас уже отличается y цифр, где y - число не нулевых цифр числа m - 1. Значит нам надо аналогичным образом посчитать для часов, число моментов когда изменится не менее чем k - y цифр. k - y цифр меняется каждое число кратное 10max(0, k - y - 1), т.е. таких моментов  —  . Т.е. .

Если, что-то плохо описано или содержит опечатку/ошибку, отпишитесь в коментариях - исправлю.


Полный текст и комментарии »

Разбор задач Codeforces Beta Round 86 (Div. 1 Only)
Разбор задач Codeforces Beta Round 86 (Div. 2 Only)
  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится