Новогодний контест

для друзей Андрея

О задачах Новогоднего контеста

1 января 2025 года я провёл свой первый Новогодний контест — в нём поучаствовало более 100 человек! Ниже я расскажу, какие были задачи и как их можно было решать. Если вы хотите присоединиться в этом году, регистрация открыта для всех желающих: 2026.andgein.ru!

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

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

01 a-plus-b

Задача «A + B», 200 уровней

Классика олимпиад по программированию! Я не мог не начать с задачи, с которой начинаются пробные туры всех олимпиад. Кроме того, это был отличный способ познакомить участников с форматом соревнования и системой. Задача стартует с тривиальных уровней — нужно просто сложить два целых числа. Вместе с тем, что в задаче будет 200 уровней, участники узнают и про API, которое помогает получать уровни и сдавать ответы автоматически. Я даже выдал код для работы с ним:

#!/usr/bin/env python3
import requests, time

URL = "https://2025.andgein.ru/api/tasks/a-plus-b"
HEADERS = {"Token": "Your Team Token"}

# Решаем столько уровней, сколько можем!
while True:
    # Получаем текущий уровень...
    task = requests.get(URL, headers=HEADERS).json()
    # Вам не надо парсить текст уровня, чтобы узнать числа, которые надо сложить:
    # входные данные к задачам всегда будут лежать в task["parameters"].
    # В данном случае там лежит {"A": "192836", "B": "837293"}.
    answer = int(task["parameters"]["A"]) + int(task["parameters"]["B"])

    # Отправляем ответ...
    r = requests.post(URL, headers=HEADERS, json={"level": task["current_level"], "answer": str(answer)}).json()
    # Если ответ неправильный, то лучше, пожалуй, выйти, чем продолжать его отправлять.
    if not r["is_correct"]:
        print(r["checker_output"])
        break

    print("Отлично, ещё один уровень позади:", task["current_level"])

    # Отдохнём чуть-чуть...
    time.sleep(0.1)

Просто запустив этот код или переписав его на ваш любимый язык программирования, можно пройти первые 40+ уровней. Неплохо!

Дальше, правда, это решение не работает, ведь очередной уровень просит сложить 1111010010100000001101010₂ и 11010010010110001111101110₂... Так мы понимаем, что на вход в этой задаче могут приходить числа, записанные в двоичной системе счисления. Исправляем код соответствующим образом и проходим ещё пару десятков уровней. В какой-то момент в уровнях появляются длинные числа (75205354748480883989811876184800672313572651799835041211739711421785781432735 + 99147694418509409465418140307673055197104449558121420831908040349553739802151), что может стать проблемой для некоторых языков программирования. Преодолеваем и эту сложность!

По ходу продвижения по уровням вас также ждут:

Степени: 20² + 25²
Вещественные числа: 0.1 + 0.2
Иррациональные константы: ℯ⁵ + 𝜋²
И даже комплексные константы: 𝜋 + 𝑖¹¹²

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

Идея решения

Достаточно правильно обработать все сценарии, которые появляются среди 200 уровней. Разумеется, это можно сделать на любом языке программирования. Конкретно в питоне я советую использовать встроенный тип decimal.Decimal, а достаточно точные значения чисел 𝜋 и ℯ брать из модуля mpmath.

lagrange

Задача «Сумма квадратов», 200 уровней

Задача начинается с уровня, который просит разложить 2025 на сумму квадратов целых чисел. Как удачно, что 2025 — это ровно 45²! На втором уровне просят разложить на сумму квадратов уже 20252025 (это, как нетрудно догадаться, 4500² + 45²), но дальше начинаются интересности...

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

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

Если разложить число на требуемое количество квадратов нельзя, нужно ответить «NO».

Идея решения

Если ~~погуглить~~ спросить LLM, то окажется, что существует теорема Лагранжа аж из XVIII века, утверждающая, что любое натуральное число можно разложить на сумму четырёх квадратов. Но как найти эти числа? И что делать, если квадратов должно быть два или три?

На второй вопрос ответ достаточно простой: на сумму двух квадратов можно разложить те натуральные числа, в разложении которых на простые множители нет такого множителя p ^ k, что p = 3 (mod 4), а k — нечётное. Почему? Потому что.

В свою очередь, на сумму трёх квадратов можно разложить все числа, кроме чисел вида 4 ^ a × (8b + 7). Потому что теорема Лежандра. В общем, всё уже доказано до нас.

Таким образом, проверить существование ответа достаточно легко. Остаётся его найти. Несмотря на то что многие участники написали собственные решения, я предполагал, что это будет задача на поиск уже готового, хорошо оптимизированного кода. Дело в том, что большинство решений в интернете — переборные, и для больших чисел они не подходят, однако хорошее решение всё-таки существует.

Одно из таких решений можно найти здесь (с комментариями на корейском!). Теоретическая основа алгоритма описана в статье Рабина и Шаллита 1986 года.

Другой метод описан в заметке Михаэля Бара и Дарио Альперна. Их код можно найти в репозитории последнего на гитхабе.

depicting

Задача «Объясни слово», 40 уровней

Задача проста: вам нужно прислать картинку, которая, будучи отправлена в ChatGPT с промтом «What is depicted in this picture? Answer in one word strictly, nothing more.», вернёт заданное английское слово.

Начинается всё безобидно и просто — со слов «Christmas» и «Winter», но в середине появляется «Nuance», а ближе к концу — «Antidisestablishmentarianism». Как выглядит Antidisestablishmentarianism?

Идея решения

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


magick -pointsize 50 label:{word} result.png

minify-yaml

Задача «Минимизация YAML», 137 уровней

Вам дан YAML-документ и число N. Ваша задача — прислать YAML-документ, эквивалентный заданному, но длина которого не превосходит N.

Идея решения

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

Во-первых, нужно было взять какой-нибудь YAML-сериализатор и начать его исправлять так, чтобы он выдавал более короткие документы. Например, строки во многих случаях можно выводить без кавычек, null заменить на ~ (объяснение), пробелы между двоеточием и значением (в большинстве случаев) убрать, длинные строковые константы не переносить и так далее.

Во-вторых, начиная с 18-го теста во входных данных встречается много повторяющихся фрагментов. Их надо заменять на YAML-якори вида &a и *a, так как это позволяет не дублировать большие куски документа. Имена якорей надо выбирать максимально короткие, но с учётом списка разрешённых символов.

Идея с якорями развивается в более поздних тестах, когда становится выгодно заменять на якори не только целые блоки, но и отдельные строки или числа. Например,


calendar: -5810438722.305
id003:
  education: -5810438722.305
  id007: -5810438722.305

можно превратить в


{calendar: &0 -5810438722.305,id003:{education: *0,id007: *0}}

regex

Задача «Сматчить всех», 23 уровня

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

Идея решения

Основная идея состоит в том, чтобы сгенерировать много маленьких кусочков регулярных выражений, которые подходят под какие-то строки из первого набора и не подходят ни под какие строки из второго набора. Затем какое-то количество таких кусочков нужно объединить через |.

Кусочки могут быть разными: например, вида "ab.*c", "a\db" или "[a-e].\w".

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

Авторское решение также использовало несколько дополнительных трюков и оптимизаций. Например, в самом конце можно попробовать выбросить какой-нибудь символ из ответа и проверить, что регулярное выражение всё ещё работает. Другая идея заключается в том, что иногда бывает выгодно поменять списки местами перед тем, как искать регулярное выражение, а затем навесить на него один большой negative lookahead. Для некоторых наборов строк также можно было также построить регистро-независимое регулярное выражение, а затем добавить в его начало (?i).

shuffled-image

Задача «Взболтать, но не смешивать», 12 уровней

Я зашифровал картинку. Для этого сначала разбил её на квадраты одинакового размера (например, 16 на 16 пикселей), а затем перемешал пиксели внутри каждого квадрата. Для простоты я использовал одну и ту же перестановку пикселей внутри каждого квадрата. Ваша задача — расшифровать картинку (использованная перестановка, разумеется, неизвестна!) и ответить на вопрос по этой картинке. Например, «сколько окон у самолёта»?

Идея решения

Может показаться, что, не зная перестановку, восстановить картинку невозможно. Да и на переборе далеко не уедешь, ведь вариантов очень и очень много... Однако на самом деле картинку можно восстановить достаточно точно!

Для этого воспользуемся алгоритмом имитации отжига. Идея в том, что, начав процесс в случайном состоянии, можно прийти к оптимальному, если совершать случайные движения и наблюдать за тем, как меняется картинка. В нашем конкретном случае случайным движением будет перестановка каких-то двух пикселей во всех квадратиках исходного изображения. Остаётся только после такой перестановки оценить, стала ли картинка «лучше» или «хуже» и насколько.

Чтобы ответить на этот вопрос, нужно ввести «функцию оценки» картинки. Чем более настоящей выглядит картинка, тем больше должно быть значение этой функции, а чем больше она похожа на суп из перемешанных пикселей, тем меньше. Заметим, что в правильной восстановленной картинке похожие пиксели, скорее всего, стоят рядом. Например, пиксели голубого неба стоят рядом с другими голубыми пикселями неба, а жёлтого солнца — с жёлтым солнцем. Поэтому функцию оценки можно считать как сумму разниц между значениями соседних пикселей. Остаётся лишь научиться эту функцию быстро пересчитывать после того, как пара пикселей в каждом квадратике меняется местами :-)

Смотрите также решение от Бори Минаева.

Понравилось?

Новогодний контест 2026 пройдёт 1 января, и вы ещё можете зарегистрироваться! Присоединяйтесь на 2026.andgein.ru.