Введение
Уже в октябре 2018 мы с радостью вспомнили адвент-календарь с задачами 2017 года (условия здесь) и начали думать, что можно сделать в этом году. Из нескольких достойных идей выбрали вариант, в котором подберём разноплановые «цепляющие» задачи, объединенные красивой новогодней историей.
Оставалось всего ничего: собственно, подобрать задачи, сочинить историю, сделать сайт с лидербордом, красивый и крепко провязанный с Яндекс.Контестом, и запуститься в начале декабря :-)
Результат
Как известно, аппетит приходит во время еды, и мы с головой погрузились в процесс проработки содержания задач и их технической реализации. Каждая удачная находка вдохновляла на дальнейшие улучшения. В итоге для одной из задач подняли отдельный сервер, другую сделали оптимизационной (точного ответа у нас самих так и нет), сами записывали музыку, восстанавливали распределения — вообще не скучали!
В результате получилось:
- 11 задач (+1 бонусная) разной сложности, все с проверкой в Контесте;
- внешний сайт для участников ;
- 11 дней (с 7 по 17 декабря включительно) на решение задач.
Интересные факты и истории
780 участников зарегистрировались, 333 человека приступили к решению, 203 человека сдали успешно хотя бы две задачи.
Изначально мы оценили чистое время на решение всех задач в семь дней для неподготовленного участника и в два дня для очень опытного (aka свежий выпускник CS центра). Первый правильно решивший все одиннадцать задач помощник Деда Мороза уложился примерно в сутки, ещё двое справились на вторые!
Письмо одного из участников: «Добрый день! Из-за вашего контеста я остановил работу офиса (40 человек) конкретно второй задачей про кофе деда мороза, дайте еще подсказку пожалуйста. Мы все очень мучаемся.»
Разбор задач
Условия тут.
Задача D «Музыкальное послание» (Михаил Плоткин)
Совсем просто решить задачу, имея минимальное музыкальное образование.
Попытка найти разгадку в ритмическом рисунке к успеху не привела. Следующей идеей было сесть за фортепиано и подобрать прослушанную мелодию. Получилось ля, до, ми, си, ля, ре, соль, ми. В скрипичном ключе так:
После первых трёх нот следовала небольшая пауза, как бы разделяющая музыкальную фразу на два слова. Оставалось только записать ноты в традиционной буквенной нотации (A=ля, B=си, С=до, D=ре, E=ми, F=фа, G=соль) и два слова открылись: ACE BADGE.
Без каких-либо познаний в музыкальной грамоте решить задачу сложнее. Например, можно было воспользоваться какой-нибудь программой для обработки звука и выяснить либо сразу сами ноты, либо частоты звуков в герцах, а затем найти, каким частотам соответствуют какие ноты.
В задании требовалось записать буквы слитно без разделителей, поэтому ответ: ACEBADGE.
Попытка найти разгадку в ритмическом рисунке к успеху не привела. Следующей идеей было сесть за фортепиано и подобрать прослушанную мелодию. Получилось ля, до, ми, си, ля, ре, соль, ми. В скрипичном ключе так:
После первых трёх нот следовала небольшая пауза, как бы разделяющая музыкальную фразу на два слова. Оставалось только записать ноты в традиционной буквенной нотации (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
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, построен на схеме лондонского метро :)
Для решения этой задачи воспользуемся модифицированной версией поиска в ширину. Заведем мнимую вершину (исток), от которой проведём рёбра нулевого веса в каждую вершину графа. Каждое состояние однозначно определяется пройденным от истока путём. Дополнительно будем хранить затраченное время и полученную радость.
Заведем очередь с приоритетами с фиксированным размером, в которую будем помещать состояния. В качестве оценки состояний, находящихся в очереди, будем использовать отношение полученного счастья к затраченному времени. Эта оценка не является корректной, но показала неплохие результаты в этой задаче.
На каждом шаге будем доставать из очереди состояние с лучшей оценкой и помещать в очередь состояния, образованные от него. При таком подходе потребуется много времени для получения конечного результата.
Для ускорения решения будем искать ответ поэтапно. На каждом шаге для поиска следующей в пути вершины будем очищать очередь и помещать в неё текущее состояние. Затем проделаем фиксированное количество шагов, попутно обновляя состояние, дающее наибольшее количество радости. В качестве следующей вершины пути возьмем вершину, следующую за последней вершиной текущего состояния в пути полученного состояния, дающего наибольшее количество радости. Повторяем проделанные действия до тех пор, пока можем улучшить текущее состояние.
Возможные улучшения
Эти изменения не дали значительных улучшений, скорее всего, из-за того, что был всего один закрытый тест, а не группа различных сгенерированных тестов.
Для решения этой задачи воспользуемся модифицированной версией поиска в ширину. Заведем мнимую вершину (исток), от которой проведём рёбра нулевого веса в каждую вершину графа. Каждое состояние однозначно определяется пройденным от истока путём. Дополнительно будем хранить затраченное время и полученную радость.
Заведем очередь с приоритетами с фиксированным размером, в которую будем помещать состояния. В качестве оценки состояний, находящихся в очереди, будем использовать отношение полученного счастья к затраченному времени. Эта оценка не является корректной, но показала неплохие результаты в этой задаче.
На каждом шаге будем доставать из очереди состояние с лучшей оценкой и помещать в очередь состояния, образованные от него. При таком подходе потребуется много времени для получения конечного результата.
Для ускорения решения будем искать ответ поэтапно. На каждом шаге для поиска следующей в пути вершины будем очищать очередь и помещать в неё текущее состояние. Затем проделаем фиксированное количество шагов, попутно обновляя состояние, дающее наибольшее количество радости. В качестве следующей вершины пути возьмем вершину, следующую за последней вершиной текущего состояния в пути полученного состояния, дающего наибольшее количество радости. Повторяем проделанные действия до тех пор, пока можем улучшить текущее состояние.
Возможные улучшения
- Использовать лучшую эвристику.
- При такой реализации алгоритма будут появляться лишние состояния, так как на каждом шаге мы будем добавлять все состояния, которые могли получиться от текущего. Для предотвращения этого можно предварительно с помощью алгоритма Дейкстры для каждой вершины графа построить дерево кратчайших путей до всех остальных вершин и совершать переходы не в один шаг, а по построенному дереву до тех пор пока мы не дойдем до вершин в которых мы ни разу не были.
Эти изменения не дали значительных улучшений, скорее всего, из-за того, что был всего один закрытый тест, а не группа различных сгенерированных тестов.
Задача I «Медведи-оцифровщики» (Александр Самофалов)
Посмотрим на исходный код сервиса.
Список всех доступных для пользователя id можно получить по адресу
Если есть id, то данные можно получить с помощью запроса на адрес
Для доступа к данным сервис требует токен для аутентификации. У нас есть доступный токен, но у него истёк срок годности, и сервис его больше не принимает.
Посмотрим в коде, как эти токены генерируются. Токен получается шифрованием JSON вида
Сделаем запрос: e = 30593, n = 66043. Т.к. n достаточно маленькое, то мы легко можем посчитать приватный ключ.
Для этого разложим n на простые множители: 211 * 313.
Вычислим функцию Эйлера от n: ?(n) = (211 — 1)(313 — 1) = 65520.
Получим d = e-1(mod ?(n)) = 257.
Обратный элемент по модулю можно посчитать с помощью расширенного алгоритма Эвклида.
Вычислив приватный ключ, расшифруем доступный нам токен.
Получим следущий JSON:
Заметим, что сервису достаточно, чтобы пользователь с данным userId существовал и expireDate был меньше, чем текущее время на сервере.
То есть, зная userId, мы можем сгенерировать новый валидный токен.
Для этого возьмем expireDate достаточно большим, чтобы пройти проверку — например
Шифруем наш новый токен с помощью публичного ключа.
Сделав запрос к
Переберем их все.
Среди них чудо-фраза: Новый год стучится в дверь, открывай ему скорей!.
Список всех доступных для пользователя 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 «Морозный узор»
Для решения данной задачи можно выбрать любой удобный треугольник, например правильный, и вычислить ответ для него.
Благодарности
Весь процесс от идеи до реализации драйвила и координировала Катя Лебедева. Задачи ей помогали составить Катя Артамонова, Алина Можина, Саша Комиссаров и я. Лёша Толстиков написал три сложных чекера, Саша Комиссаров вместе с Серёжей Жеревчуком сделали сервер, Свят и Серёжа самоотверженно в сжатые сроки сделали красивый сайт с тесной интеграцией с задачами: каждому участнику был виден его прогресс и лидерборд.