Привет, Codeforces!

Полным ходом идёт HFT Battle 2017 – соревнование биржевых алгоритмов, на время которого каждый участник сможет примерить на себя роль разработчика HFT-стратегий. Задача участников – написать стабильно зарабатывающий HFT-алгоритм, исследуя микроструктуру рынка и поведение финансового инструмента. В мае на базе этих алгоритмов состоится дополнительное 24-часовое соревнование по ускорению и оптимизации кода, которое должно особенно понравиться участникам Codeforces.

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

Кроме того, есть несколько существенных отличий от соревнования прошлого года:

• Добавлена возможность разработки стратегий не только на C++, но и на Python.
• Можно участвовать командой с одного аккаунта: достаточно при регистрации указать данные одного из участников.
• Возможность вызвать другого участника на дуэль, в котором ваши стратегии будут видеть и влиять на действия друг друга.

С чего начать

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

Мы предлагаем вам начать с краткой документации, которой будет достаточно для знакомства с системой. Кроме того, мы разработали пакет для локальной разработки стратегий.

Соревнование продлится до 30 апреля 2017, после чего мы проведём финальное тестирование на наборе из 20 новых торговых сессий.

В этом году мы наградим ТОП-20 призёров соревнования. А лучшие участники также получат возможность пройти собеседование в AIM Tech и присоединиться к нашей дружной команде.

Мы будем рады обратной связи! Отзывы лучше всего оставлять через кнопку "Помощь" ("Support") в интерфейсе системы, либо писать нам на почту help@hftbattle.com. Присоединяйтесь к бурному обсуждению соревнования в нашем канале в Telegram!

Для создания стратегии не требуется специальных экономических знаний и достаточно базовых навыков программирования на C++ или Python. Мы уверены, что многие участники Codeforces смогут добиться положительных результатов!

Желаем всем высокого рейтинга и отличных результатов в HFT Battle 2017!

Hey, guys!

I'm excited to invite you to participate in 101 Hack June 2016! The contest will start at 16.30 UTC, June 20.

I'm the problemsetter of this round. You may have seen my tasks on previous HackerRank contests or may have participated in Codeforces Round 319 (Div. 1) or Codeforces Round 319 (Div. 2).

There will be five tasks and two hours for you to solve them. Top-10 contestants on the leaderboard will receive awesome HackerRank T-shirts! (I'm really jealous, since I don't have one)

I'd like to thank wanbo for his invaluable help and testing all the problems, danilka.pro for testing one of the problems and his cool proof of author's solution, Zlobober for his help in estimation of one of the tasks difficulty, and sankear, he did nice job sitting in the bar with me and discussing the problems.

I hope you will enjoy the tasks. Please read all of the problem statements during contest, as it may be essential for your final place.

Good luck!

UPD. The contest has ended. Special congratulations to Lewin: the only contestant who solved the last task!

Top-10:

1). Lewin

2). I_love_Tanya_Romanova

3). Errichto

4). tourist

5). Temirulan

6). Kostroma

7). Deemo

8). riadwaw

9). uwi

10). mgch

Задача A. Div2.

Заметим, что число x может встречаться в столбце i только один раз — в строке x / i. Переберем столбец i, проверим, что x делится нацело на i, а также x / i ≤ n. Если все условия выполнены, обновим ответ.

Асимптотика — O(n)

Код

Задача B. Div2.

Рассмотрим два случая: n > m и n ≤ m.

Пусть n > m, рассмотрим суммы на префиксах. По принципу Дирихле, найдутся две равные суммы по модулю m. Пусть S_lmodm = S_rmodm. Тогда сумма чисел на отрезке с l + 1 по r по модулю m равна нулю, то есть ответ точно "YES".

Пусть n ≤ m, то решим задачу динамикой за O(m²). Пусть can[i][r] — можем ли мы, используя первые i предметов, получить остаток r от деления на m. Переходы в динамике понятны: либо мы берем предмет и переходим в состояние can[i + 1][(r + a_i) mod m], либо не берем и переходим в состояние can[i + 1][r].

Асимптотика — O(m²).

Код

Задача A. Div1.

Пусть Петя не спросил число p^k, где p — простое, а k ≥ 1. Тогда, Петя не сможет отличить число p^k - 1 от числа p^k.

Значит, нужно спросить все числа вида p^k, где p — простое, а k ≥ 1. Несложно убедиться, что это позволит угадать и все остальные числа.

Асимптотика O(N^1.5) или O(NloglogN) в зависимости от теста на простоту.

Код

Задачи B. Div1.

Рассмотрим дерево-ответ. Заметим, что центры этого дерева могут перейти только в центры при применении перестановки. Это означает, что в перестановке обязательно должен быть цикл длины 1 или 2.

Пусть в перестановке есть неподвижная точка. Тогда мы можем подсоединить ребрами к этой вершине все остальные. Несложно убедиться, что это корректный ответ.

Например, пусть дана перестановка (4, 2, 1, 3). В перестановке есть неподвижная точка 2, поэтому подсоединим ко второй вершине все остальные. Получатся ребра дерева (1, 2), (2, 3), (2, 4).

Пусть в дереве-ответе есть два центра. Удалим ребро между ними, дерево разобьется на две компоненты. Несложно понять, что они должны перейти друг в друга при применении перестановки. Это означает, что все циклы перестановки должны быть четной длины.

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

Например, рассмотрим перестановку (6, 5, 4, 3, 1, 2). В перестановке есть два цикла: (3, 4) и (1, 6, 2, 5). Соединим ребром вершины (3, 4), все вершины другого цикла присоединим по очереди к этим двум вершинам, получим ребра (1, 3), (6, 4), (2, 3), (5, 4).

Асимптотика — O(N).

Код

Задача C. Div1.

Разобьем квадрат 10⁶ × 10⁶ вертикальными линиями на 1000 прямоугольников 10³ × 10⁶. Пронумеруем эти прямоугольники от 1 до n в порядке слева направо. Обойдем их тоже слева направо, а внутри каждого прямоугольника обойдем точки по возрастанию y-координаты, если это четный по номеру прямоугольник, и по убыванию, если нечетный.

Посчитаем длину такого пути, будем считать независимо по каждой координате. По y-координате мы пройдем суммарно 1000 прямоугольников от 0 до 10⁶, то есть суммарно 10⁹, По x-координате, чтобы дойти до следующей точки внутри прямоугольника, мы потратим не более 1000 на точку, и 1000 раз пройдем не более 2000 до следующего прямоугольника, то есть суммарно 10⁹ + 2000000.

Итого, длина пути не более 2 * 10⁹ + 2000000, что подходит под ограничения на длину.

Асимптотика — O(n * log(n))

Код

Задача D. Div1.

Будем оптимизировать первое же решение, которое приходит в голову за O(m * d_max): посчитаем can[t][v] — можно ли добраться до вершины v, пройдя по ровно t ребрам.

Теперь заметим, что множество ребер, по которому мы можем ходить меняется только m раз. Отсортируем ребра в порядке возрастания d_i, т.е. для всех i d_i ≤ d_i + 1. Будем считать динамику can[t][v] только для t = d_i. Пусть мы хотим перейти от can[d_i] к can[d_i + 1]. Поскольку набор ребер не меняется с момента d_i до d_i + 1, мы можем возвести матрицу смежности в степень d_i + 1 - d_i и применить ее к can[d_i].

Пусть мы насчитали все can[d_i][v]. Теперь зафиксирует ребро с максимальным d_i, по которому мы пройдем в нашем кратчайшем пути. Мы знаем все вершины, в которых мы можем находиться в момент d_i, далее нужно найти кратчайший путь из них в вершину m по открытым для нас ребрам и обновить ответ. Матрицу кратчайших расстояний можно посчитать Флойдом, поэтому обновление ответа не составит труда.

Получилось решение за O(m * n³ * log(d_max)), которое, к сожалению, работает долго.

Далее нужно заметить, что матрица смежности состоит из ноликов и единичек, поэтому её можно возводить в степень битовым сжатием за O(n³ / 32). Это дает решение за O(m * n³ * log(d_max) / 32), что спокойно заходит по времени.

Код

Задача E. Div1.

Сначала решим чуть более простую задачу: пусть вне зависимости от двудольности/недвудольности запросы выполняются, а от нас требуется лишь ответить, будет ли граф двудольным/недвудольным после запроса.

Тогда мы могли бы применить решение, похожее на решение задачи Dynamic Connectivity Offline за O(nlog²ⁿ). Опишем его подробнее:

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

Теперь пусть ребра иногда удаляются. Для каждого ребра и каждого цвета мы знаем отрезки запросов, когда это ребро будет в графе заданного цвета. Давайте построим дерево отрезков на запросах, в каждой вершине будем хранить список ребер, которые будут включены на этом подотрезке. Каждый отрезок дерево отрезков разобьет на log кусочков, поэтому в сумме количество добавлений ребер на кусочке будет порядка n * log.

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

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

Зато мы можем сделать следующее. Изначально применим операцию до первого момента появления ребра в запросах. Теперь, когда мы находимся в листе, мы узнали, какого цвета это ребро будет до следующего его появления в запросах. Поэтому, давайте сделаем обновление на отрезке со следующего запроса до следующего появления этого ребра. Для каждого листа мы сделаем не более одного обновления, поэтому суммарное время работы O(nlog²n).

Асимптотика — O(nlog²n).

Код

Если что-то неясно, непонятно или невнятно написано, задавайте любые вопросы.

Всем привет!

Сегодня в 19.30 по московскому времени состоится Codeforces Round #319, который настоятельно не рекомендуется кому-либо пропускать.

Автор раунда — я, меня зовут Дима Горбунов, и это мой первый раунд на Codeforces. Я очень надеюсь, что вам понравится раунд, и каждый найдет себе задачу по вкусу. Для того, чтобы увеличить вероятность этого события, пожалуйста, прочтите все задачи этого контеста.

Как всегда, благодарю Zlobober за неоценимую помощь при подготовке контеста и утонченный юмор, sankear за написание перекрестных решений, Delinur за перевод условий на английский язык и MikeMirzayanov за потрясающие системы Codeforces и Polygon.

У вас будет два часа на то, чтобы решить 5 задач. Успехов!

UPD. Разбалловка в первом дивизионе — 500-1250-1250-2000-2750.

Во втором — 500-1250-1500-2250-2250.

UPD2. Из-за тестов большого размера по некоторым задачам, системное тестирование будет идти медленно (возможно, займёт несколько часов). Благодарим за терпение!

UPD3. Разбор можно найти по ссылке.

UPD4. Winners!

Div1:

1). Marcin_smu

2). mnbvmar

3). I_love_Tanya_Romanova

Div2:

1). latisel

2). wrong_order

3). ntitry826

Отдельный респект al13n за правильное решение задачи Div1.E во время контеста!