Google Code Jam - это всемирное онлайн-соревнование по программированию, которое ежегодно собирает от 30 000 до 60 000 участников. Участники решают набор задач по программированию в течение обычно 2,5 часа.

Мне нравится волнение, которое приносит каждый раунд, и то чувство, что вы отправляете правильное решение всего за несколько минут до крайнего срока. Я также чувствую, что каждый раз узнаю много хитрых трюков. И хотя я не думаю, что я достаточно хорош, чтобы попасть в 25 лучших и участвовать в Мировом финале, я раньше занимал 326-е место, что по-прежнему входит в 1% лучших участников.

В этой статье я представлю общие классы проблем из моего 8-летнего опыта работы с Code Jam. Если вы опытный программист и обладаете математическим мозгом, то использование этого руководства должно легко ввести вас во 2 раунд (лучшие 4500 участников) и дать вам хорошие шансы попасть в 3 раунд (1000 лучших участников, которые все выиграют t- рубашки). Все прошлые проблемы открыты для практики, что позволяет вам изучать их по своему желанию.

Вступление

Code Jam начинался как инструмент найма в Google для выявления талантливых инженеров, но, к сожалению, я не встречал ни одной немецкой компании, которая заботилась бы о моей работе в Code Jam. Как обычно, немецкие компании заботятся о многолетнем опыте и впечатлениях руководителей, а не о реальных навыках программирования.

На ныне не существующем сайте Go-Hero показано, что около 85% участников используют один из трех языков: C ++ (45%), Python (20%) и Java (20%). Как ни странно, процент C ++ только возрастает в более продвинутых раундах (до 80% +), подразумевая, что это может быть лучший инструмент для работы.

Смотреть на конкурсную заявку на C ++ - настоящий кошмар. Сначала дюжина строк директив препроцессора для сохранения пары нажатий клавиш (например, определение «long long» как «ll» и макроса «FOR (i, n)» для циклов). Имена переменных будут состоять из 1 или 2 букв для дальнейшего сохранения нажатий клавиш. И, конечно же, одно включение всего stdlib и никаких комментариев.

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

Python - хорошо спроектированный язык, но имеет один недостаток дизайна: округление (x,5) округляет до ближайшего четного числа, поэтому round (1.5) равен 2, а round (2.5) также равен 2. Итак, прежде чем продолжить, добавьте в свой набор инструментов следующее переопределение функции round:

round = lambda x: int(x + .5)

Жадный и добротный

Многие проблемы на раннем этапе (Q, 1A-1C) могут быть решены с помощью жадного алгоритма. Жадный алгоритм просто мгновенно выбирает лучший вариант на каждом этапе, не обращая внимания на все входные данные.

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

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

Примеры задач:
- Последнее слово
- Сенатская эвакуация
- Алфавитный торт
- Скорее озадачивающая разборка
- Ошибка округления : Немного сложно. Также требуется исправление round ().

Примеры решений:
- Ошибка округления

Числа треугольника

Число треугольника числа n просто определяется как сумма всех чисел от 1 до n, которая выглядит как треугольник, если вы нарисуете их в виде маленьких кружков:

Итак, tri (1) = 1, tri (2) = 3, tri (3) = 6, tri (4) = 10 и т. Д. Общая формула в Python:

tri = lambda n: n * (n + 1) // 2

У чисел-треугольников есть много применений. Например, tri (n-1) дает количество пар, которое можно составить для n человек. Это причина того, что большие команды разработчиков программного обеспечения терпят поражение, потому что с ростом n количество каналов связи между людьми (число треугольника) увеличивается квадратично по n.

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

.5 n**2 + .5 n = t
.5 n**2 + .5 n + (-1) t = 0

Решение с помощью формулы abc приводит к:

invtri = lambda t: int( (2 * t + .25)**.5 - .5 )

Int () «округляет в меньшую сторону», отображая [3, 4, 5] в 2 и [6, 7, 8, 9] в 3.

У нас все еще есть проблема: Мы используем поплавки. Это на самом деле укусило меня из-за проблемы с блинами и привело к тому, что я проиграл приз. Ограничения точности с плавающей запятой - это то, что каждый программист должен уметь анализировать, и Code Jam сознательно выбирает ограничения таким образом, что числа с плавающей запятой могут стать проблемой, поэтому я добавил еще один раздел о них ниже.

К счастью, целочисленные квадратные корни - это хорошо изученная проблема, которая существует в Python с 3.8. Поскольку в программе судейства используется версия 3.7, вам пока придется иметь дело с собственной реализацией. Нам просто нужно умножить все выражение на 2, чтобы избавиться от дробей:

(1) n**2 + (1) n + (-2) t = 0

Наконец-то:

invtri = lambda t: (math.isqrt(8 * t + 1) - 1) // 2

Теперь вы будете хорошо вооружены для решения любых задач с треугольными числами!

Примеры задач:
- Изящные жонглеры бензопилой: в сочетании с динамическим программированием. ЖЕСТКИЙ.
- Инкрементальный домик из блинов: числа в виде перевернутого треугольника. ЖЕСТКИЙ.

Бинарный поиск

Проблемы с двоичным поиском распространены, особенно на ранних этапах (Q, 1A-1C). Двоичный поиск позволяет индексировать значение внутри отсортированного списка, уменьшая вдвое интервал поиска на каждом шаге, что приводит к очень быстрому алгоритму. Поскольку они широко освещаются в университетах и ​​собеседованиях, я не ожидаю, что у кого-то возникнут трудности с ними.

Тем не менее, полезно иметь стандартную версию этого алгоритма, чтобы избежать единичных ошибок или ограничить количество ошибок, которые могут быть сложными. Я использую эту функцию:

# Search on the interval [lo,hi)                                vvvv
# Return first index where test_func is True  -> [False..False, True..True]
# This will fail when the list is all False
def bin_search(lo, hi, test_func):
    print('Calling bin_search with ', lo, hi)
    if lo == hi - 1:
        return lo
    mid = (hi+lo-1)//2
    if test_func(mid):
        return bin_search(lo, mid + 1, test_func)
    else:
        return bin_search(mid + 1, hi, test_func)

Пример использования (найдите индекс 1000):

a = [10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000]
assert bin_search(0, len(a), lambda i: a[i] >= 1000) == 2

Иногда Code Jam бросает вызов проблеме, не имея явного списка / массива, но требуя динамически вычисляемого значения, поскольку создание всего списка было бы слишком трудоемким (по сути, само линейное время, в этот момент вы выполнили линейный поиск, а не бинарный поиск). Вот почему я разработал свой помощник, который принимает функцию вместо массива, он более общий.

Двоичный поиск настолько эффективен, что его можно использовать даже для инвертирования любой монотонной функции, например, функции числа треугольников, описанной выше. Просто выполните двоичный поиск по значениям x и проверьте, совпадают ли вы с желаемым значением y. Это очень быстро как для целочисленных, так и для плавающих доменов (значения x), а также для примера динамически вычисляемого значения, как уже упоминалось. Итак, инвертируем tri (4) = 10:

tri = lambda n: n * (n + 1) // 2
assert bin_search(0, 20, lambda i: tri(i) >= 10) == 4

Обратите внимание, что это округляется в большую сторону, а не в меньшую, поэтому работает только с числами идеального треугольника. Полнофункциональная версия с округлением в меньшую сторону будет:

invtri = lambda t: bin_search(0, 10**10, lambda i: tri(i) > t) - 1

В более общем смысле:

def invert_monotonic_int_function(fct):
    return lambda y: bin_search(0, 10**20, lambda x: fct(x) > y) - 1
invtri = invert_monotonic_int_function(tri)

Примеры задач:
- Яблочко с завязанными глазами: сразу после интерактивной части.
- Стрижка
- Битовая вечеринка
- Кубический НЛО: Используется чтобы инвертировать функцию. Возможно и прямое решение линейной алгебры.

Примеры решений:
- Яблочко с завязанными глазами

Динамическое программирование

Динамическое программирование (DP) - это такой продукт Code Jam, что над ним даже пошутили:

Иногда наши панграммы содержат конфиденциальную информацию - например, CJ QUIZ: KNOW BEVY OF DP FLUX ALGORITHMS - поэтому нам необходимо обеспечить их безопасность.

Краткое объяснение заключается в том, что динамическое программирование может применяться к рекурсивным задачам с перекрывающимися подзадачами. Хитрость заключается в том, чтобы решать задачу «вперед» (от базового случая к полной проблеме), а не «назад».

Обычно это делается с помощью двухмерной таблицы. Но он так же хорошо работает с трехмерной таблицей (см. Примеры задач) или с одномерной таблицей. Я буду использовать числа Фибоначчи в качестве примера, чтобы объяснить DP, для которого на самом деле просто требуется одномерная таблица. Числа Фибоначчи определяются как:

def fib(n: int):
    if n <= 2: return 1
    return fib(n - 1) + fib(n - 2)

Это означает, что n-е число Фибоначчи является суммой двух предыдущих чисел Фибоначчи, 1-е и 2-е числа Фибоначчи равны 1. Однако это рекурсивное определение вызывает много ненужной работы:

units_of_work = 0
def fib(n: int):
    global units_of_work
    if n <= 2: return 1
    units_of_work += 1
    return fib(n - 1) + fib(n - 2)
fib(30)
assert units_of_work == 832039

Это потому, что подзадачи приходится вычислять много раз. Например, f (30) = f (29) + f (28) = f (28) + f (28) + f (27), поэтому мы должны вычислить f (28) дважды, а не один раз, что приведет к огромное дерево вычислений. Мы выполняем почти миллион единиц работы, фактически объем работы, который мы выполняем, равен самому 30-му числу Фибоначчи (832040).

Одно из исправлений - кэшировать вызовы с помощью lru_cache:

from functools import lru_cache
units_of_work = 0
@lru_cache()
def fib(n: int):
    global units_of_work
    if n <= 2: return 1
    units_of_work += 1
    return fib(n - 1) + fib(n - 2)
fib(30)
assert units_of_work == 28

Более явным является использование таблицы DP и выполнение вычислений «вперед», а не «назад»:

units_of_work = 0
fib = [1] * 31
for n in range(3, 31):
    units_of_work += 1
    fib[n] = fib[n-1] + fib[n-2]
assert units_of_work == 28

В 2D и при использовании Python все становится немного сложнее.

В типичной задаче DP каждая ячейка принимает не более двух предков (например, ячейка находится непосредственно наверху и непосредственно в верхнем левом углу). Затем мы перебираем все строки и применяем этот максимум для каждой ячейки. Обычно вам нужно будет инициализировать первую строку отдельно, а также убедиться, что предок не выходит за пределы (сложно в Python, поскольку отрицательные числа являются допустимыми индексами!).

Python обычно слишком медленный для этой задачи. Здесь на помощь приходит numpy. Если мы будем использовать массив numpy вместо списка списков и грамотно программировать, мы можем добиться большого ускорения. Что мы сделаем, так это рассмотрим каждую строку как массив numpy и применим к ней какую-то операцию numpy, например, сдвиг на 1 или даже просто добавим константу. Это по сути перемещает наши циклы for с Python на внутренний код C, который работает на дрожжах быстрее. Однако мы должны быть осторожны, чтобы избежать случайного использования медленной итерации Python (за исключением самого внешнего цикла) и операторов if.

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

Динамическое программирование (пример: Ant Stack)

В Ant Stack нам даны следующие параметры:
- Входные данные представляют собой последовательность муравьев, заданную в виде простого списка весов
- Найти стопку, в которой каждый муравей несет не более чем в 6 раз больше своего веса. вес
- Выходной стек должен быть подпоследовательностью входного
- Муравьи весом до 10 ** 9 миллиграммов

Сначала мы можем провести некоторый анализ пределов (обсуждается ниже), чтобы выяснить, что у нас никогда не может быть больше 139 муравьев в стопке, потому что даже самый тяжелый муравей не сможет нести больше. Точная причина не важна, но таким образом мы можем создать таблицу с размерами MAXANTS x NUMANTS = 139 x 10 ** 5. Для простоты (и поскольку я думаю, что у меня возникла ошибка ограничения памяти) мы будем хранить только самую последнюю строку размером 139 (по техническим причинам 141), во многих задачах DP вы можете просто сохранить последнюю строку вместо таблицы.

У нас получится таблица с такими осями:

    0   1   2   3  ... 140 (ants on stack)
__
W1
W2
W3
…
W10000
(input ant weights)

Ячейка (j, Wi) представляет собой вес самого лучшего / самого низкого по весу стека муравьев (муравьи с 1 по i) и (размер j) на данный момент. Знать, какие переменные на каких осях ставить - это искусство, но давайте продолжим. Как мы можем рекурсивно получить следующую строку из предыдущей? Мы хотим добавить муравья, если это возможно, и пропустить его в противном случае:

DP[i,j] = DP[i-1,j-1] + Wj if 6 * DP[i-1,j-1] <= Wj else DP[i-1,j]

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

Вы можете возразить, что это позволяет нам выбрать неоптимального муравья. Допустим, мы находимся в столбце j и выбираем муравья Wi, но W_i + 1 лучше, потому что он весит немного меньше, но все еще может поднять всех, кто выше. Когда мы позже обрабатываем W_i + 1, мы перезапишем это значение для j, поскольку мы рекурсивно переходим к случаю j-1 - вот почему так важно сохранить все столбцы с частичными проблемами.

Для входных данных [31, 30, 6, 6] идеальное решение - пропустить муравья с весом-31, потому что наш последний муравей с весом-6 может нести только вес-36, в результате получается стек с весом-42, состоящий из 3 муравьев. . Этот раствор красиво пузырится:

         0   1   2   3   4   5 (ants on stack)
_____    0 inf inf inf inf inf
W1=31    0  31 inf inf inf inf
W2=30    0  30  61 inf inf inf
W3= 6    0   6  36 inf inf inf
W4= 6    0   6  12  42 inf inf
(input ant weights)

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

def run(ants):
    n = len(ants)
    MAXANSWER = 139
    INFTY = MAXANSWER * 10**9 + 1
    num_cols = min(MAXANSWER+2, n+2)
    DP = numpy.full(num_cols, INFTY, dtype=int)
    DP[0] = 0
    for i in range(n):
        add_this_ant = (DP + ants[i]) + INFTY * (DP > 6 * ants[i])
        add_this_ant = numpy.concatenate((add_this_ant[-1:], add_this_ant[:-1]))
        DP = numpy.minimum(DP, add_this_ant)   # next row
    return numpy.argmax(DP >= INFTY) - 1   # finds first 'True'

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

Ознакомьтесь с:
- Проблема рюкзака: типичная проблема DP.

Примеры задач:
- Ant Stack: 2D таблица DP. Проблема обсуждалась выше, остальные посложнее
- Edgy Baking
- Red Tape Committee: 3D DP table
- Graceful Chainsaw Jugglers: 3D DP table

Модульная арифметика и простые числа

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

- Как проверить, является ли число n простым (вкратце: попробуйте разделить на все числа от 2 до квадратного корня из n по модулю)
- НОД и алгоритм Евклида. Знайте, что два числа взаимно просты, если их НОД равен 1.
- Тотальная функция Эйлера (подсчет простых чисел)
- Основная теорема арифметики
- Китайская теорема об остатках

Разберем на примере недавнюю проблему Сломанные часы. Мы нашли часы без надписи в подвале, что означает, что мы не знаем, какая стрелка является стрелкой секунд / минут / часов, а в более крупных тестовых случаях мы не знаем, в каком направлении находятся 12 часов, и нас спрашивают чтобы найти указанное время. Поскольку проблема гарантирует, что всегда есть одно решение, мы можем решить первую часть, просто попробовав все 6 различных назначений секунд / минут / часов для рук и проверив, какое из них является действительным.

Задача просит нас иметь дело с миллисекундным временем, поэтому в задаче «тик» определяется как наименьшее значение, на которое любая стрелка переместится за миллисекунду, в частности часовая стрелка, что означает, что требуется T = 12 * 60 * 60 * 10 ** 9 = 43200000000000 тиков для круглосуточного полного цикла. Каждая миллисекунда перемещает часовую стрелку на 1 деление, минутную стрелку на 12 делений, а секундную стрелку на 12 * 60 = 720 делений. Часовая стрелка всегда будет вращаться в первый раз, поскольку фактическое время находится между полуднем и полуночью, но другие стрелки могли пересекать 12 часов несколько раз, что привело к следующим уравнениям:

    t             =  hours_hand
    (12 t)  %  T  =  minutes_hand
    (720 t) %  T  =  seconds_hand

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

    t        ===T  hours_hand
    (12 t)   ===T  minutes_hand
    (720 t)  ===T  seconds_hand

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

В большом случае часы можно вращать в любую сторону, в результате чего каждая стрелка отключается на некоторое количество тактов r:

    r + t        ===T  hours_hand
    r + (12 t)   ===T  minutes_hand
    r + (720 t)  ===T  seconds_hand

Если вычесть первые два уравнения, мы получим

    (11 t)   ===T  minutes_hand - hours_hand

Обратите внимание, как исчезла буква r! Мы можем вычислить t прямо по стрелкам минут и часов.

Остается единственная задача - «разделить на 11» с обеих сторон. В модульной арифметике это можно сделать путем умножения на модульное обратное. Модульное обратное число M1 - это число M2 такое, что M1 M2 = 1. Наивный алгоритм поиска модульного обратного числа состоит в том, чтобы просто попробовать все числа от 0 до T-1 и проверить, какое из них дает 1 после умножения и по модулю. Более эффективный способ - использовать расширенный алгоритм Евклида, который я рекомендую изучить.

Для Python 3.8+ поиск модульного обратного фактически встроен прямо в язык:

>>> pow(11, -1, 43200000000000)
15709090909091

Таким образом, мы просто имеем

    t   ===T  15709090909091 (minutes_hand - hours_hand)
    r   ===T  hours_hand  -  t

К сожалению, судья использует Python 3.7, поэтому я пока жестко запрограммирую эту константу. Полное решение:

T = 12 * 60 * 60 * 10**9  # 43200000000000 ticks on the clock
modular_inverse_of_eleven = 15709090909091
def try_assignment(seconds, minutes, hours):
    t = ((minutes - hours) * modular_inverse_of_eleven) % T
    r = (hours - t) % T
    if not (
            (t + r) % T == hours and
            (12 * t + r) % T == minutes and
            (720 * t + r) % T == seconds
    ):
        return
    return (
        f'{t // (60 * 60 * 10**9)} '
        f'{(t // (60 * 10**9)) % 60} '
        f'{(t // 10**9) % 60} '
        f'{t % 10**9}'
    )
def run(data):
    a, b, c = data
    return (
            try_assignment(a, b, c) or
            try_assignment(a, c, b) or
            try_assignment(b, a, c) or
            try_assignment(b, c, a) or
            try_assignment(c, a, b) or
            try_assignment(c, b, a) or
            "no result found, this should never happen"
    )

Примеры проблем:

- Part Elf: относительно простое применение GCD
- Broken Clock: проблема из предыдущего раздела (модульная арифметика)
- Prime Time: эта проблема также связана с анализом пределов / границ
- Гольф-суслики

Пределы / Границы

Это своего рода мета-категория. Многие проблемы на самом деле не требуют очень умного или быстрого алгоритма и могут быть решены с помощью стандартного алгоритма, анализируя, какие максимальные значения возникают. По сути, вы анализируете, что НЕ нужно вычислять, поэтому части, которые вы можете пропустить.

Примеры проблем:

- Prime Time: на самом деле проблема с примерами.
- Ant Stack: на самом деле проблема DP.

Точность с плавающей запятой

Это еще одна мета-категория. Помните: У числа с плавающей запятой - 7 цифр точности, у двойного - 15 цифр. Например, в Инкрементальном доме блинов входные значения могут достигать 10 ** 18, это уже красный флаг, потому что это число состоит из 18 цифр, что на самом деле больше 15. Вы даже можете поиграть с этим в Python и видите, что 10 ** 18 и 10 ** 18 + 64 отображаются на одном и том же поплавке:

>>> float(10**18)
1e+18
>>> float(10**18 + 64)
1e+18
>>> float(10**18 + 65)
1.0000000000000001e+18

По возможности старайтесь использовать операции int и int. В Python это означает использование // вместо /, когда это необходимо. В этой конкретной проблеме ключевым было использование целочисленного квадратного корня вместо обычного квадратного корня с плавающей запятой.

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

>>> float(10**18 + 65) - float(10**18 + 64)
128.0

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

Примеры проблем:

- Детский бассейн: катастрофическая отмена
- Добавочный дом блинов

Интерактивные задачи

Интерактивные задачи не требуют, чтобы вы читали входной файл и создавали выходной файл, а вместо этого требуют, чтобы вы взаимодействовали с другой проблемой, читая и записывая по одной строке за раз. На мой взгляд, IP обычно имеют очень низкое количество попыток и правильных ответов по сравнению с их сложностью. Большинство IP на самом деле просты, но я думаю, что люди просто не могут понять, как использовать интерактивный бегун или отлаживать программу. Или, может быть, они боятся их вероятностной природы (вы получаете случайный ввод, и вам нужно быть лучше, чем некоторый порог, что трудно доказать). Мой совет: никогда не упускайте их! Они позволят вам превзойти конкурентов, приложив относительно небольшие усилия.

Примеры проблем:

- Магазин леденцов: Самый простой
- Гольф-суслики
- Гончарная лотерея
- Блоки цифр

Графики / Деревья

Алгоритмы построения графиков - это обширная область сама по себе. На чем вы должны сосредоточиться, так это на знании поиска в глубину (DFS) и деревьев, хотя большинство алгоритмов графов и деревьев, которые мне приходилось использовать в Code Jam, были довольно интуитивно понятными.

Один неочевидный алгоритм, с которым я встречался несколько раз, - это Венгерский алгоритм. Обратите внимание, что эксперт по Python ДЕЙСТВИТЕЛЬНО включает numpy и scipy, поэтому вы можете решать эти типы проблем с помощью scipy.optimize.linear_sum_assignment.

DFS:
- Лучшие друзья

Попытки:
- Alien Rhyme

Максимально-двудольное соответствие / Венгерский алгоритм:
- Техно-болтовня: очень прямолинейно
- Смена костюма
- Энергетические камни

Максимальный поток:
- Двуязычный