Новогоднее соревнование CS центра 2018 +10


Введение


Уже в октябре 2018 мы с радостью вспомнили адвент-календарь с задачами 2017 года (условия здесь) и начали думать, что можно сделать в этом году. Из нескольких достойных идей выбрали вариант, в котором подберём разноплановые «цепляющие» задачи, объединенные красивой новогодней историей.

Оставалось всего ничего: собственно, подобрать задачи, сочинить историю, сделать сайт с лидербордом, красивый и крепко провязанный с Яндекс.Контестом, и запуститься в начале декабря :-)

Результат


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

В результате получилось:


Интересные факты и истории


780 участников зарегистрировались, 333 человека приступили к решению, 203 человека сдали успешно хотя бы две задачи.

Изначально мы оценили чистое время на решение всех задач в семь дней для неподготовленного участника и в два дня для очень опытного (aka свежий выпускник CS центра). Первый правильно решивший все одиннадцать задач помощник Деда Мороза уложился примерно в сутки, ещё двое справились на вторые!

Письмо одного из участников: «Добрый день! Из-за вашего контеста я остановил работу офиса (40 человек) конкретно второй задачей про кофе деда мороза, дайте еще подсказку пожалуйста. Мы все очень мучаемся.»

Разбор задач



Условия тут.

Задача D «Музыкальное послание» (Михаил Плоткин)
Совсем просто решить задачу, имея минимальное музыкальное образование.
Попытка найти разгадку в ритмическом рисунке к успеху не привела. Следующей идеей было сесть за фортепиано и подобрать прослушанную мелодию. Получилось ля, до, ми, си, ля, ре, соль, ми. В скрипичном ключе так:



После первых трёх нот следовала небольшая пауза, как бы разделяющая музыкальную фразу на два слова. Оставалось только записать ноты в традиционной буквенной нотации (A=ля, B=си, С=до, D=ре, E=ми, F=фа, G=соль) и два слова открылись: ACE BADGE.

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

В задании требовалось записать буквы слитно без разделителей, поэтому ответ: ACEBADGE.

Задача F «Мешок снежинок» (Михаил Плоткин)
Площадь исходного треугольника равна 1. Далее на n-м шаге добавляется t_n треугольников, каждый из которых имеет площадь s_n. Суммарная площадь полученной фигуры выражается в виде суммы бесконечного ряда:
S = 1 + ?(t_n * s_n), сумма по n от 0 до ? (1)
На нулевом шаге t_0 = 3, s_0 = 1/9, поскольку у треугольника 3 стороны, на каждой из которых строится треугольник со стороной в 3 раза меньше исходной, а значит площадью в 9 раз меньше площади исходного треугольника.
На каждом следующем шаге каждая сторона превращается в 4 стороны втрое меньшего размера, то есть
t_n = t_{n-1} * 4 = t_0 * 4n = 3 * 4n,
s_n = s_{n-1} * (1/9) = s_0 * (1/9)^n = 1/9 * (1/9)^n.

Следовательно, искомая площадь:
S = 1 + ?(t_n * s_n) = 1 + 1/3 * ?((4/9)^n), сумма по n от 0 до ? (2)

Второе слагаемое представляет собой сумму бесконечно убывающей геометрической прогрессии. Для её вычисления используем школьную формулу
?((4/9)^n) = 1 / (1 — 4/9) = 9/5.

Подставляя в формулу (2), получаем ответ:
S = 1 + 1/3 * 9/5 = 8/5 = 1.6

Задача G и L «Маршрут построен» (Артём Романов)
Спасибо Артёму mehrunesartem за решение! Кстати, граф, который использовался в задаче G, построен на схеме лондонского метро :)

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

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

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

Возможные улучшения

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

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

Задача I «Медведи-оцифровщики» (Александр Самофалов)
Посмотрим на исходный код сервиса.

Список всех доступных для пользователя id можно получить по адресу /data.
Если есть id, то данные можно получить с помощью запроса на адрес /data/id.
Для доступа к данным сервис требует токен для аутентификации. У нас есть доступный токен, но у него истёк срок годности, и сервис его больше не принимает.

Посмотрим в коде, как эти токены генерируются. Токен получается шифрованием JSON вида { “userId” : “id”, expireDate: “date”} и последующим кодированием его в base64. Сервис использует RSA для шифрования, и публичный ключ можно получить запросом по адресу /key.

Сделаем запрос: e = 30593, n = 66043. Т.к. n достаточно маленькое, то мы легко можем посчитать приватный ключ.

Для этого разложим n на простые множители: 211 * 313.
Вычислим функцию Эйлера от n: ?(n) = (211 — 1)(313 — 1) = 65520.
Получим d = e-1(mod ?(n)) = 257.
Обратный элемент по модулю можно посчитать с помощью расширенного алгоритма Эвклида.

Вычислив приватный ключ, расшифруем доступный нам токен.
Получим следущий JSON: {"userId":"448f0a79-e2d8-4ccd-9009-53858914dcaa","expireDate":"2018-12-06T14:38:00.898026+00:00"}

Заметим, что сервису достаточно, чтобы пользователь с данным userId существовал и expireDate был меньше, чем текущее время на сервере.
То есть, зная userId, мы можем сгенерировать новый валидный токен.
Для этого возьмем expireDate достаточно большим, чтобы пройти проверку — например
{"userId":"448f0a79-e2d8-4ccd-9009-53858914dcaa","expireDate":"2100-01-01T12:00:00.000000+00:00"}.

Шифруем наш новый токен с помощью публичного ключа.
Сделав запрос к /data, узнаем, что пользователь создал сообщения с идентификаторами от 1 до 4.
Переберем их все.
Среди них чудо-фраза: Новый год стучится в дверь, открывай ему скорей!.

Подсказки к решениям некоторых других задач (от Артёма Романова)

Задача A «Сейф с письмами»
Можно заметить, что через каждые двадцать шагов будет получаться одна и та же цифра.

Задача B «Секрет профессора»
Отсортируйте слова по убыванию популярности. Можно заметить, что каждое последующее слово встречается приблизительно в 2, 3, 4 и т.д. раз меньше чем самое популярное слово. Теперь можно восстановить ответ.

Задача C «Компьютерная катастрофа»
Вспомните про язык программирования Whitespace.

Задача J «Бенгальск»
Возможное размещение:


Задача K «Морозный узор»
Для решения данной задачи можно выбрать любой удобный треугольник, например правильный, и вычислить ответ для него.

Благодарности


Весь процесс от идеи до реализации драйвила и координировала Катя Лебедева. Задачи ей помогали составить Катя Артамонова, Алина Можина, Саша Комиссаров и я. Лёша Толстиков написал три сложных чекера, Саша Комиссаров вместе с Серёжей Жеревчуком сделали сервер, Свят и Серёжа самоотверженно в сжатые сроки сделали красивый сайт с тесной интеграцией с задачами: каждому участнику был виден его прогресс и лидерборд.




К сожалению, не доступен сервер mySQL