Привет, Codeforces!

Я рад анонсировать, что компания Rocket Fuel Inc. снова будет проводить соревнование Rockethon! Контест подготовили сотрудники компании Эльдар Богданов, Антон Ломонос, Лаша Лакирбая, Александр Рафф, Никил Гоял и я, Евгений Соболев. Мы надеемся, что каждый из вас найдет для себя интересные задачи на контесте и от решения этих задач вы получите не меньше удовольствия, чем получили мы от их подготовки. Как и в прошлом году, лучшие участники получат ценные призы и футболки. Помимо этого, Rocket Fuel заинтересован в рекрутинге людей после соревнования, поэтому, пожалуйста, заполните простую форму при регистрации.

О Rocket Fuel

Rocket Fuel is building technology platform to do automatic targeting and optimization of ads across all channels — display, video, mobile and social. Our pitch to advertisers is very simple "If you can measure metrics of success of your campaign, we can optimize". We run campaigns for many large advertisers and our clients include many top companies within the following industries: autos, airlines, commercial banks, telecom, food services, insurance, etc. Examples include BMW, Pizza Hut, Brooks Running Shoes and many more!

We buy all our inventory through real time bidding on ad exchanges like Google and Yahoo. Ad exchanges are similar to stock exchanges except the commodity being traded is ad slots on web pages. Our serving systems currently process over 60B bid requests/ day with a response time requirement of 100ms. Our data platform has 64 PBs data that is used for analytics as well as modeling.

Our engineering team is still small (~150) enough for any one person like yourself to make a huge impact. The team represents many top schools in US and outside — Stanford, Carnegie Mellon, MIT, Wisconsin-Madison, IIT (India), Tsinghua (China).

Rocket Fuel has been named #4 on Forbes Most Promising Companies in America List in 2013 and #1 Fastest Growing Company in North America on Deloitte’s 2013 Tech Fast 500 and our CEO George John was recently named “Most Admired CEO” by the SF Business Times in 2014.

Мои впечатления

Около года назад я зашел на Codeforces и увидел объявление о Rockethon 2014. Моей первой мыслью было: "Круто! Еще одно соревнование от крупной компании!" Я поучаствовал, выступил достаточно неплохо, после чего со мной связались рекрутеры Rocket Fuel и назначили несколько собеседований. Я прошел собеседования и теперь я здесь, в Rocket Fuel.

Работа в Rocket Fuel — это отличная возможность изучить продвинутые вещи в software engineering, так как вокруг работают много умных людей, которые всегда готовы делиться своими знаниями. Конечно, наша деятельность не ограничивается только лишь написанием кода — мы играем в баскетбол, футбол, настольный теннис. Я приглашаю каждого из вас принять участие в соревновании и буду рад услышать если вы задумываетесь о трудоустройстве в Rocket Fuel.

Обзор соревнования

Контест начнется 7-го февраля в 20:00 МСК.

Продолжительность контеста — 3 часа.

Тестирование посылок будет производиться сразу же после их отправления и вердикты тестирования будут немедленно показаны авторам посылок.

В контесте будет 7 задач, каждая из которых может иметь от одной до трех подзадач. Каждая подзадача будет стоить некоторое фиксированное число баллов. Если несколько участников наберут одинаковое число баллов, выше будет стоять тот участник у которого будет меньше штрафное время, вычисляемое аналогично ACM-системе.

Призы

Три лучших участника получат следующие призы:

1) IPhone 6 (16 Gb)

2) Участник может выбрать Apple Watch или Samsung Gear S

3) Участник может выбрать Apple Watch или Samsung Gear S

Лучшие 150 участников получат футбоолки Rockethon с оригинальным дизайном соревнования.

Если вы не можете принять участие в соревновании, но заинтересованы в трудоустройстве в Rocket Fuel, мы будем обрабатывать резюме отправленные через специальную форму.

Всем привет!

Приглашаю всех принять участие в контесте 101 Hack March. Ссылка на время старта в разных регионах. В контесте будет пять задач на два часа. Автором задач являюсь я и, на мой взгляд, задачи очень интересные.

Внимательные люди могут заметить, что за полчаса до этого раунда начнется TopCoder SRM 614. Чтобы завлечь Вас поучаствовать в контесте именно на HackerRank, хочу отметить, что топ-10 участников получат футболки! В чем участвовать, в SRM-е или в 101 Hack March, решать Вам, однако, SRM-ов нынче по четыре в месяц, а на HackerRank-е есть шанс выиграть эксклюзивную футболку!

Повторюсь, на мой взгляд, задачи для раунда отличные, поэтому очень не хочется, чтобы они остались нерешенными :)

Заранее благодарю всех тех, кто примет участие в 101 Hack March!

Задача A. Утренний бег

В задаче требовалось найти математическое ожидание количества встреч между бегунами. Как это делать? Для начала, вспомним, что математическое ожидание линейно, поэтому исходная задача эквивалентна следующей: найти сумму математического ожидания количества встреч между каждой парой бегунов. Будем решать задачу именно в этой формулировке. Сделаем несколько наблюдений:

1. Пусть расстояние между двумя фиксированными бегунами ровно x и они бегут навстречу друг другу бесконечно (вероятность того, что они бегут навстречу, как нетрудно видеть, равняется 0.5·0.5 = 0.25). Тогда первая встреча произойдет в момент времени , следующая — , следующая — и так далее.

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

На основании этих наблюдений будем строить решение. Для начала разобьем t как t = k·l + p, где 0 ≤ p < l. Тогда, каждый из бегунов пробежит ровно k полных кругов. Что это означает? Так как всего пар бегунов ровно , то за k кругов в каждой из пар с вероятностью 0.5 произойдет ровно 2k встреч. Значит, к ответу нужно добавить .

Теперь как-то нужно обработать оставшиеся p секунд бега. Предположим, что расстояние между двумя бегунами ровно x и они бегут это расстояние навстречу друг другу. Тогда, между ними произойдет встреча, если , или x ≤ 2t. Между ними произойдет вторая встреча, если , или x ≤ 2t - l. Больше двух встреч произойти не может, так как p < l.

Зафиксируем какого-нибудь бегуна, тогда с помощью двоичного поиска мы можем найти количество бегунов, которые находятся на расстоянии не более x от данного. Выберем границу x как x = 2t, и тогда количество бегунов на расстоянии не более x будет означать количество бегунов, которые встретятся с зафиксированным. Если же мы выберем x = 2t - l, то сможем найти количество бегунов, с которыми произойдет вторая встреча. Умножаем полученные количества на 0.25 — вероятность встречи бегунов, и добавляем к ответу.

Сложность такого решения составляет . Ее можно улучшить, если вместо двоичного поиска использовать метод двух указателей.

Задача B. Контекстная реклама

В задаче требовалось найти максимальное количество слов, которое можно разместить в блоке размера r × c. Решим сначала следующую задачу: какое максимальное количество подряд идущих слов поместится в строке длины c, если первое слово имеет индекс i. Такую задачу можно решать двоичным поиском, или двигая указатель. Теперь создадим граф, где вершинами будут слова, а ориентированные ребра будут соединять вершины i и j, если слова с i по j - 1 помещаются в одну строку длины c, а слова с i по j уже не помещаются. Весом ребра будет величина j - i. Тогда исходную задачу можно переформулировать в терминах данного графа: требуется найти путь длины k, который имеет наибольший вес. Такую задачу можно решать со сложностью используя метод двоичного подъема, или за O(n) при помощи поиска в глубину.

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

Задача C. Память для массивов

Здесь нужно было найти максимальное количество массивов, которое можно разместить в имеющейся памяти. Для начала отметим следующее: пусть ответ на задачу — это число k, тогда одним из оптимальных решений будет размещение k самых маленьких по размеру массивов в памяти. Без ограничения общности, будем считать, что у нас есть массивы размера 1 и мы хотим их разместить, при этом, разместить их как можно больше. Тогда, если у нас есть участки памяти нечетного размера, то при размещении массива размера 1 на таком участке, мы получим участок памяти четного размера. С другой стороны, если размещать на участке массивы другого размера, то четность не поменяется, и если на участке не будет размещено ни одного массива размера 1, то в самом конце в нем будет хотя бы одна свободная ячейка. Значит, выгодно размещать массивы размера 1 на участках памяти нечетного размера. Сделаем это, пока можем. Возможны три ситуации:

1. У нас закончились участки памяти нечетного размера.

2. У нас закончились массивы размера 1.

3. У нас закончились и участки памяти нечетного размера и массивы размера 1.

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

Во втором случае, если мы сразу разделим все имеющиеся числа целочисленно на 2, и решим изначальную задачу, то ответ мы не ухудшим.

Третий случай аналогичен второму.

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

Сложность данного решения составляет .

Задача D. Теннисные ракетки

Участникам требовалось найти количество тупоугольных треугольников на данных вершинах, удовлетворяющих некоторым условиям. Сразу отметим, что авторское решение имеет сложность O(n²), но имеет ряд оптимизаций, благодаря чему решение укладывается в TL с большим запасом.

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

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

Введем координаты, так что вершина A треугольника имеет координаты (0,0). Вершина B (0,) и C(2,0). Тогда найдем координаты каждой из точек на сторонах и выпишем теорему косинусов. Получим некое соотношение, которое гарантирует нам, что треугольник будет тупоугольным. Один из возможных его видов таков: Если 1 ≤ i, j, k ≤ n — номера точек зафиксированных на сторонах, то треугольник тупоугольный тогда и только тогда, когда: f(i, j, k) = 2i² - i(n + 1) + 2j(n + 1) - ij - k(i + j) < 0. Заметим, что возрастает, поэтому можем использовать метод двигающегося указателя для перебора k. Тогда просто переберем i от m + 1 до , затем j от m + 1 до тех пор, пока верхняя граница для k не превосходит n - m + 1 и будем суммировать результаты.

Отметим, что все результаты нужно делать в типе int, что существенно ускоряет решение.

Задача E. Овечки

Эту задачу предлагается решать жадно. Будем следовать следующему алгоритму. Создадим для каждого отрезка 2 пометки Position_v и MaximalPosition_v.

Position_v — соответствует позиции v в искомой перестановке.

MaximalPosition_v — соответствует максимальной допустимой позиции v в текущий. момент.

Пусть у нас также имеется счетчик count изначально равный 0 и множество необработанных вершин S. Будем действовать по следующему алгоритму.

1. Двоичным поиском ищем минимальное возможное расстояние между самыми удаленными соединенными овцами. Для фиксированного расстояния K проверяем существует ли перестановка.

2. Отсортируем все отрезки по возрастанию r_i.

3. Position_i = 0, 1 ≤ i ≤ n, MaximalPosition_i = n, 1 ≤ i ≤ n, current = 1, count = 0.

4. Выполнить count = count + 1, Position_current = count, удаляем current из S, если S — пустое, то требуемая перестановка найдена.

5. Перебираем все отрезки, которые соединены с current, и обновляем MaximalPosition_v = min(MaximalPosition_v, Position_current + K)

6. Строим множества S(count, j) = {v|MaximalPosition_v ≤ count + j}. Если для всех j ≥ K - count + 1 выполнено |S(count, j)| ≤ j то переходим к шагу 7, иначе выводим, что искомой перестановки не существует.

7. Ищем минимальное j такое что |S(count, j)| = j. Выбираем оттуда вершину с наименьшим r_i и берем ее в качестве нового значения current, переходим к шагу 4.

Сначала обоснуем время работы представленного алгоритма. Зафиксируем расстояние K (всего будет итераций с фиксированным K).

Заметим, что шаги с 4 по 7 в худшем случае выполняются ровно n раз (каждый раз размер множества S уменьшается на 1). Каждый из шагов можно реализовать так, чтобы он выполнялся за O(n). Самый сложный шаг — это шаг 6. Но заметим, что нам не требуется явно строить эти множества, достаточно знать лишь их размеры. А это мы можем сделать за линейное время, просто посчитав сколько существует таких элементов, что MaximalPosition_v = i. Обозначим это число через C_i — тогда размер множества S(count, j) равен C₁ + C₂ + ... + C_{count + j}, что легко подсчитать при помощи массива частичных сумм.

Обоснуем теперь корректность алгоритма. Если алгоритм расставил позиции для всех вершин, то очевидно, что имеет требуемую перестановку. Предположим, что алгоритм заканчивает свое выполнение до того, как мы расставили все позиции, покажем, что тогда не существует искомой перестановки. Есть алгоритм закончил свое выполнение, это означает, что для некоторого count (рассмотрим найменьшее такое count), что есть такое j₀, что |S(count, j₀)| > j₀ на этом шаге. Покажем, что тогда |S(count, k)| > k. Докажем это от противного. Предположим, что это не так. Из определения count имеем |S(count - 1, j)| ≤ j для всех j ≥ k - count + 2. Тогда |S(count, j)| = |S(count - 1, j + 1)| - 1 ≤ j для всех j ≤ k - 1. При этом, S(count, j) = S(count, k) для k ≤ j < n - count = |S(count, j)| = |S(count, k)| ≤ j. В итоге |S(count, n - count)| = n - count. Тогда |S(count, j)| ≤ j для всех j, следовательно имеем противоречие. Значит, алгоритм преращает свою работу на шаге 6, |S(count, k)| > k. Это означает, что существует как минимум k + 1 вершина, которая до сих пор не имеет назначенной позиции после вершины, которая была отмечена как count. Значит, одна из вершин в S(count, k) должна быть с Position как минимум count + k + 1. Но все вершины в S(count, k) соединены с как минимум одной вeршиной с Position ≤ count. Следовательно, получаем, что искомомй перестановки не существует.

Разбор задач был подготовлен sdya и Seyaua.

A Div 2

Если a_j делится на a_i, то тогда a_i ≤ a_j. Тогда число, на которое будут делиться все остальные числа будет не более чем любое выбранное число. То есть единственный возможный кандидат — это минимум в массиве. Поэтому просто проверим, что все элементы массива делятся на минимальный элемент.

B Div 2

Легко видеть, что Ксюша не сможет закончить ее путешествие, если существует последовательность подряд идущих # длиное более чем k.

C Div 2 / A Div 1

Первое наблюдение: мы не будем волноваться о том, как выглядят строки на самом деле, вся информация, которая нам нужна — это количество пар-символов вида: {0, 0}, {0, 1}, {1, 0}, {1, 1}. Посчитаем эти количества и будем следовать следующему жадному алгоритму:

Для первого игрока: будем брать сначала {1, 1}, если их нет, то {1,0}. Если их нет, то {0, 1} и, в последнюю очередь, будем брать {0, 0}.

Для второго игрока похожая стратегия: сначала {1, 1}, потом {0, 1}, потом {1, 0} и, в последнюю очередь, {0, 0}.

После этого сравним у кого получилось больше единичек.

D Div 2 / B Div 1

Любой путь из верхней левой клетки в правую нижнюю состоит ровно из n + m - 1 клеток. И все они должны быть покрашены в разные цвета. Значит n + m - 1 ≤ k. Исходя из маленьких ограничений на k можно предположить, что брут-форс будет работать. Единственная оптимизация для получения действительно правильного решения — это некоторая канонизация раскрасок. Будем идти по всем клеткам в некотором порядке и красить их согласно следующим условиям. Если i > j, тогда цвет i встречается позже цвета j. После такого перебора мы получим примерно миллион различных шаблонов для максимального теста.

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

E Div 2 / C Div 1

После прочтения условия, можно понять, что все, что нам нужно — это посчитать количество решений уравнения (a + b + c)³ - a³ - b³ - c³ = n в положительных целых числах.

Ключевое наблюдение это: 3(a + b)(a + c)(b + c) = (a + b + c)³ - a³ - b³ - c³, после чего мы можем просто вычислять все делители числа и идти по всем делителям x = a + b, таким что ? далее будем идти по делителям y = (a + c) ≥ x, где и в конце будем вычислять z = (b + c), такое что .

После этого, решим систему a + b = x, a + c = y, b + c = z и добавим количество подходящих решений к ответу.

D Div 1

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

Для каждого x определим y_left, y_right таким образом, что все точки (x, y), где y_left ≤ y ≤ y_right лежат внутри многоугольника и отрезок [y_left, y_right] максимально возможный.

Теперь будем считать, что мы имеем a₁, a₂, ..., a_k различных точек для каждого фиксированного x (a₁ соответствует x =  - 10⁶, a₂ соответствует x =  - 10⁶ + 1 и так далее).

Теперь требуемый ответ это a₂a₁ + a₃(a₂ + 2²a₁) + a₄(a₃ + 2²a₂ + 3²a₁) + ...

Можно заметить, что

(a₂ + 2²a₁) - a₁ = a₂ + 3a₁,

(a₃ + 2²a₂ + 3²a₁) - (a₂ + 2²a₁) = a₃ + 3a₂ + 5a₁,

и так далее.

Поэтому достаточно предпросчитать частичные суммы вида a₂ + 3a₁, a₃ + 3a₂ + 5a₁, a₄ + 3a₃ + 5a₂ + 7a₁ (разность между двумя соседними суммами составляет 2(a_i + ... + a₁), поэтому мы можем делать это за O(k)).

После предпросчета достаточно сложить полученные результаты.

E Div 1

Будем считать что у нас есть структура данных, которая позволяет осуществлять следующие операции:

• добавить точку (x, y) в структуру;

• сдвинуть все точки структуры на вектор (dx, dy);

• узнать как много точек (x,y), удовлетворяющих x ≤ x_bound, y ≤ y_bound;

• получить все элементы, которые на данный момент находятся в структуре;

Для каждой вершины дерева мы будем хранить указатель на структуру такого вида.

ОБъясним, как нужно обновлять структуры. Мы будем обрабатывать все вершины в порядке обхода в глубине, и если мы находимся в листе, то мы будем создавать структуру с единственным элементом (0, 0).

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

После этого будем идти по всем сыновьям вершины и делать следующее:

• Сдвинем структуру на (1, вес ребра);

• Возьмем все элементы структуры;

• Для каждого элемента (x, y) ответим на запрос x_bound = L - x, y_bound = W - y (используем родительскую структуру);

• Добавим элементы по одному в структуру;

После этого ответим на запрос x_bound = L, y_bound = W и добавим элемент (0, 0).

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

Осталось только объяснить, как создать нужную нам структуру данных.

Существует несколько способов сделать это, один из них:

• Будем иметь маленькие подструктуры у которых размеры являются степенями двойки;

• Каждая структура — это двумерное дерево отрезков;

• Мы можем добавлять элемент следующим образом: если нет подструктуры размера 1, тогда создадим ее, иначе же возьмем все структуры размерами 1, 2, 4, ..., 2^k и перестроим в структуру размера 2^k + 1.

• Сдвиг: достаточно помнить вектор сдвига для каждой подструктуры;

• Ответ на запрос: идем по подструктурам и суммируем результаты.

Разбор задач был подготовлен sdya и Seyaua

Всем привет!

Сегодня состоится второй раунд Всероссийского Открытого Чемпионата по программированию "КРОК-2013". Раунд для вас готовили: sdya, Seyaua, Gerald и, как обычно, задачи на английский переводила Delinur.

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

Официальным участникам напоминаем, что:

• Все участники чемпионата должны быть не моложе 18 лет на момент регистрации
• Финал чемпионата состоится 16 и 17 мая в Москве в офисе компании КРОК (50 участников)
• Проживание во время финала будет оплачено компанией КРОК
• Для граждан Российской Федерации: организаторы покроют транспортные расходы по территории РФ, транспортные расходы не по территории РФ — по согласованию (возможно, частично)
• Финалисты должны подтвердить свое участие до 2 мая

И небольшой бонус: лучшие 200 официальных участников чемпионата получат футболки!

Желаем всем получить удовольствие от решения задач ну и, конечно, удачи!

UPD: Разбалловка по задачам сегодня будет немножко отличаться от стандартной: 500-1500-1500-2000-2500 для первого дивизиона и 500-1000-1500-2500-2500 для второго.

UPD2: Мы приносим свои извинения за технические неполадки во время раунда. Посовещавшись, мы решили, что соревнование должно быть рейтинговым. А результаты соревнования будут учитываться в отборе на финал чемпионата КРОК.

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

Дивизион 2, задача А. Петя и строки

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

Дивизион 2, задача B. Петя и квадрат

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

scanf("%d%d%d", &n, &x, &y);

n /= 2;

if ((x == n || x == n + 1) && (y == n || y == n + 1)) printf("NO\n"); else printf("YES\n");

Дивизион 2, задача С. Петя и неравенства (Дивизион 1, задача А)

Нетрудно видеть, что максимум суммы квадратов достигается, когда все числа, кроме одного равны 1. Теперь достаточно проверить, можем ли мы из заданного y набрать n положительных целых чисел и если можем, то проверить, что x ≤ 1 + 1 + ... + (y - (n - 1))².

Дивизион 2, задача D. Петя и делители (Дивизион 1, задача B)

Заведем массив used, такой, что в used[j] хранится номер последнего числа во входных данных, у которого есть делитель j. Тогда для каждого запроса будем последовательно перебирать делители числа x_i и для каждого делителя k числа x_i будем проверять является ли он «уникальным». После этого обновим пометку для делителя k в массиве used.

Дивизион 2, задача E. Петя и пауки (Дивизион 1, задача С)

Данная задача подразумевала множество решений. Следует отметить, что количество входных данных не так велико, поэтому можно было попытаться вручную разобрать все возможные входные данные. Можно было написать перебор, который при нужных отсечениях можно было сдать даже без предпросчета ответов. Однако большинство решений участников все же содержало в себе динамику по профилю. Здесь я приведу решение пользователя Zlobober.

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

Пусть D[k][pmsk][msk] - это минимальное количество центров, достаточное, чтобы собрать всех пауков с первых k столбцов, причём k-ый столбец имеет маску pmsk, а k + 1-ый - msk. Тогда за переход мы перебираем маску tmsk k - 1-ого столбца, и среди тех, для которых k-ый столбец может целиком разбежаться по центрам, выбираем тот, для которого D[k - 1][tmsk][pmsk] минимально.

Получается решение за O(n*2^3m), где n > m.

Дивизион 1, задача Д. Петя и раскраски

Заметим, что если m = 1, то ответ kⁿ, так как допустимы все возможные раскраски.

Теперь m > 1. Рассмотрим первый столбец доски (проведем вертикальную прямую справа от первого столбца). Пусть в нем x различных цветов. Тогда в оставшихся столбцах тоже x различных цветов по условию. Теперь если мы сдвинем нашу вертикальную прямую на 1 вправо, то количество цветов в левой части не уменьшится, а в правой не увеличится. Повторяя сдвиги, можем сделать вывод, что опять в левой части будет x различных цветов и в правой тоже x. Теперь мы получаем, что в крайних столбцах доски ровно по x различных цветов. Нетрудно видеть, что в остальных столбцах доски должны встречаться только те цвета, которые встречаются в пересечении цветов крайних столбцов доски.

Будем последовательно перебирать два числа x и y, где x - количество используемых цветов в каждом из крайних столбцов, y - количество общих цветов в крайних столбцах. При этом ясно, что на x и y накладываются некоторые ограничения в зависимости от размера доски.  Будем считать ответ для каждой такой пары, а затем все их просуммируем. Тогда для каждой пары (x,y) имеем, что надо сначала выбрать (2x-y) цветов из k данных цветов, которые мы будем использовать при раскраске. Поэтому ответ для пары нужно сразу умножить на C(k,2x-y). Далее, выберем (x-y) уникальных цветов, которые будут использоваться в первом столбце. Ответ умножается еще на C(2x-y,x-y). Выбирая (x-y) уникальных цветов для последнего столбца, имеем еще одно умножение ответа на C(x,x-y). Теперь надо знать, сколько существует способов раскрасить n клеток в x цветов. Это несложная динамика (при этом цвета учитываются лексикографически, что означает, что если на доске есть цвета a и b, при этом a<b, то цвет a встречается раньше чем b), которая пересчитывается по формуле: d[i][j]=j*d[i-1][j]+d[i-1][j-1]. Домножаем ответ для пары на d[n][x] (раскрашиваем первый столбец) и потом еще раз на d[n][x] (раскрашиваем последний столбец). После этого в каждом из крайних столбцов можно сделать перестановку цветов, поэтому нужно ответ умножить на (x!)². Теперь осталось домножить ответ на y^n(m-2), так как цвета в средних столбиках могут быть любыми из пересечения.

Можно привести простой код, который проверяет нужные нам пары:

long long ans=0;

for (int y=0; y<=n; y++){

      long long cur=powmod(y,n*(m-2));

      for (int x=y; x<=n; x++)

      if (2*x-y<=k)

      {

            long long tek=cnk[2*x-y];

            tek*=cnn[2*x-y][x-y], tek%=mod;

            tek*=cnn[x][x-y], tek%=mod;

            tek*=d[n][x], tek%=mod;

            tek*=d[n][x], tek%=mod;

            tek*=f[x], tek%=mod;

            tek*=f[x], tek%=mod;

            tek*=cur;

            ans+=tek;

            ans%=mod;

      }

}

cout<<ans<<endl;

Здесь, cnk[i] – это предпросчитанное C(k,i), cnn[a][b] – C(a,b), d[n][x] – динамика как в разборе, f[x] – x!.

Заметим, что у некоторых участников возникли проблемы с тайм лимитом, однако если аккуратно предпросчитать все C(k,i) и помнить, что нам никогда не понадобится более чем 2000 цветов из предложенных 1000000, то проблем со временем быть не должно. Следует отметить, что авторское решение работало менее 200 мс, при предложенном тайм лимите в 5 секунд.

Здесь приводится разбор всех задач прошедшего раунда. Вопросы и предложения задавайте в комментариях. Отдельное спасибо пользователю sdya за подготовку разборов задач D и E, которые я использовал в качестве авторского разбора.

Задача А

В данной задаче нужно уметь проверять всего четыре условия:
1) помещается ли N в тип byte

2) помещается ли N в тип short

3) помещается ли N в тип int

4) помещается ли N в тип long

Именно в таком порядке и нужно проверить эти условия. Если все они неверны – то ответ BigInteger.

Как проще всего проверить условия 1) – 4)? Проще всего хранить числа в виде строк и написать функцию сравнения двух строк как чисел. В Java можно было пользоваться встроенным типом BigInteger.

Задача B

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

Задача C

Понятно, что максимальное число файлов и максимальное число подпапок будет в каких-то из папок, находящихся непосредственно в корне каких-то дисков. Рассмотрим, чем характеризуется файл и чем характеризуется подпапка. Файл характеризуется путем, который записан в условии, а папка характеризуется частью пути до нее. То есть, к примеру, если есть путь: C:\folder1\folder2\1.txt, то отсюда нам надо выделить две папки и один файл, чтобы получить выражение для каждой из папок в данном пути и для файла. Имеем, что первой папке соответствует путь C:\folder1\, второй папке C:\folder1\folder2\, и файлу соответствует C:\folder1\folder2\1.txt. После того, как мы разделим так каждую строку из входных данных, у нас получится набор путей к папкам и отдельно набор путей к файлам. Решим задачу сначала для подпапок. Для этого соберем все пути к папкам, которые мы получили в результате предыдущей операции. Понятно, что некоторые пути могут встречаться там несколько раз. Отсортируем этот массив. Прежде чем удалить из него повторения, заметим, что ими можно воспользоваться для подсчета ответа по файлам. Для этого просто подсчитаем какая из строк встречается больше всего раз – это и будет ответом по файлам (подумайте почему). После, нужно удалить повторения – это можно сделать, отсортировав все строки-пути и пройдя один раз по полученному массиву. Теперь у нас остался отсортированный массив путей, без повторений. Пусть наш массив будет s. Будем идти по массиву и искать строку, в которой ровно два обратных слеша – это будет означать, что мы нашли папку, которая находится в корне какого-то диска. Пусть индекс этой строки в массиве k. Тогда рассмотрим все строки, начиная с k+1 по k+l, такие, что они содержат строку s[k] как подстроку, начиная с стартовой позиции. А s[k+l+1] уже не содержит. То есть, имеется в виду, что если s[k]=X:\folder1\, то все подпапки этой папки будут иметь вид X:\folder1\... И естественно они и только они содержат s[k] как подстроку, при этом начиная с начала (выделено жирным).

Тогда, мы получим, что у папки X:<span lang="EN-US">folder1\ будет ровно l подпапок. Аналогично, пройдя так до конца массива, мы найдем ответ по максимальному количеству вложенных подпапок. Также можно было решать эту задачу используя set, или map вместо сортировки.

Задача D

Выберем N различных простых чисел: p1, p2, …, pn. Пусть A=p1*p2*...*pn. Тогда, нетрудно видеть, что в качестве ответа подходят следующие числа: A/p1, A/p2, …, A/pn. Единственный особый случай, это N=2. Здесь ответа не существует.

Следует заметить, что для такого решения этой задачи нужна длинная арифметика, при этом из операций нужно лишь умножение (A/pi=p1*…*p(i-1)*p(i+1)*…*pn). Если выбрать в качестве p1, …, pn первые n простых чисел, то самое большое из чисел в ответе на n=100, будет содержать меньше 300 знаков.

Однако существует еще решение. Рассмотрим ответ для N=3 – 15, 10, 6. Тогда, для произвольного N>3 подходят следующие числа: 15, 10, 6, 15*2, 15*3, …, 15*(N-2).

Задача E

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

D1=a1-b1,

D2=(a1+a2)-(b1+b2),

D3=(a1+a2+a3)-(b1+b2+b3),

…

Dn=(a1+a2+…+an)-(b1+b2+…+bn);

Очевидно, что если какое-то из чисел Di меньше нуля, то от первой станции машина не сможет проехать круг против часовой стрелки. Также рассмотрим число D=min(Di) – оно нам пригодится в дальнейшем решении. Очевидно, если D<0, то первая станция не может быть стартовой. Таким образом, за время O(N) мы умеем проверять, может ли первая станция быть стартовой. Покажем теперь, как проверить за O(1), может ли быть вторая станция стартовой. Для этого рассмотрим числа:

E1=D1-(a1-b1),

E2=D2-(a1-b1),

…

En=Dn-(a1-b1).

Распишем эти числа в более развернутом виде:

E1=(a1-b1)-(a1-b1)=0=(a2+a3+…+an+a1)-(b2+b3+…+bn+b1) – так как сумма всех ai равна сумме всех bi по условию.

E2=(a1+a2)-(b1+b2)-(a1-b1)=a2-b2

E3=(a1+a2+a3)-(b1+b2+b3)-(a1-b1)=(a2+a3)-(b2+b3)

…

En=(a1+a2+…+an)-(b1+b2+…+bn)-(a1-b1)=(a2+…+an)-(b2+…+bn)

Но, мы видим, что числа E1 для второй станции имеют тот же смысл, что и числа D1 для первой станции. Поэтому достаточно лишь проверить условие min(Ei)>=0. Но как это быстро проверить? У нас есть числа Di и из всех их вычитается одинаковое число => если минимум среди Di было число Dk, то среди Ei минимумом будет число Ek=Dk-(a1-b1). Таким образом, на то, чтобы проверить подходит ли в качестве ответа вторая станция – нам уже нужно O(1) операций. Аналогичным образом, зная минимум для второй станции мы проверим, подходит ли к ответу третья станция и так далее. После этого нужно не забыть решить задачу в обратном направлении, когда машина двигается по часовой стрелке.