Боря программирует

London Underground.

Мой контест, о котором я писал в этом посте, теперь доступен на CodeForces!

Расскажу про мою любимую задачу из контеста. К сожалению, она довольно сложная (ее решило 5 команд), но зато у нее прикольное решение.

Вам дан (прямо файлом, можно скачать) граф реального Лондонского метро. В нем 426 станций и 505 перегонов между ними. Нужно посчитать (по модулю 998244353) количество назависимых подмножеств в этом графе. Т. е. посчитать сколько всего существует способов выбрать какие-то вершины так, чтобы не было двух, которые соединены напрямую перегоном.

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

Как вообще можно считать количество независимых множеств в графе? Допустим, нам нужно посчитать его на графе, который выглядит как решетка размера 10х100 (в нем всего 1000 вершин, и вершина (i, j) соединена с (i+1, j) и (i, j + 1)). Для такого графа можно воспользоваться техникой под названием динамическое программирование по изломаному профилю. Идея в следующем. Будем идти по вершинам слева направо и сохранять "состояние" (всего 2^10 различных) вершин в последнем посещенном столбце. "Состояние" это то, какие вершины мы взяли в набор. И для каждого состояния будем хранить, сколькимя способами мы могли в него прийти. Дальше мы пытаемся добавить новую вершину и для каждого из 2^10 новых различных состояний посчитать количество способов в нем оказаться.

Можно обобщить этот алгоритм для произвольного графа. Будем добавлять вершины по одной, хранить состояния "кого взяли в множество из интересных вершин", и для каждого состояния их количество. При этом "интересные вершины" это те, у которых есть ребра в еще не посещенные вершины. В случае с решеткой это как раз вершины в последнем столбце. За сколько будет работать такой алгоритм? Примерно за количество различных состояний. Если добавлять вершины в случайном порядке, то скорее всего многие из них будут соединены с еще не посещенными и где-то в середине работы алгоритма придется хранить 2^200 состояний, что не реалистично.

Однако можно добавлять вершины в каком-то умном порядке, чтобы уменьшить количество состояний. Например, если бы в графе с решеткой мы бы добавляли вершины не слева направо, а сверху вниз, то пришлось бы хранить 2^100 состояний. Так что порядок очень важен! Как найти хороший порядок вершин для графа Лондонского метро? Заметим, что если у нас есть какой-то фиксированный порядок, то можно быстро посчитать сколько состояний для него придется хранить. Еще можно вспомнить, что граф нам дан, так что можно заранее его как-то предподсчитать.

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

Stress testing. AI.

Мы недавно выложили документ с подробностями того, как разные модели OpenAI решают олимпиадные задачи. Там довольно много деталей, в том числе примеры кода, который модель генерирует и pass@1 для большого количества задач с CodeForces. Из интересного, можно заметить, что довольно часто модель может решить более сложные задачи, но при этом не справляется с простыми. Так что сложность задач очень субъективная вещь.

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

Для этого вы пишете еще одно решение задачи, но гораздо более простое. Например, пусть вы решаете такую задачу. Нам дали n=10^6 точек на плоскости и попросили найти две самые удаленные друг от друга. Изначально вы написали какое-то сложное решение, которое включает поиск выпуклой оболочки и метод двух указателей. Но в нем лего ошибиться. Тогда вы пишете другое решение, которое просто перебирает все пары точек и выбирает лучшую. Это буквально три строки кода, ошибиться сложно, но для n=10^6 работать не будет.

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

Так вот, модель никогда специально не учили писать стресс тесты. Но из-за того, что те цепочки рассуждений, которые делали стресс тест для проверки своих решений, чаще получили Accepted, во время Reinforcement Learning-а, такое поведение поощралось, и получилось, что итоговая модель, если не уверена в своем решении, сама его сверяет с более простым медленным способом. Если это не магия, то что тогда?

Universal Cup. Stage 27.

Почти год назад я подготовил свой контест и дал его на сборах по программированию, которые проходили в Хорватии. Я в него вложил много сил и считаю, что там много интересных задач. Сами задачи еще не доступны публично, но в ближайшую субботу (25 января) пройдет этап Universal Cup на тех же самых задачах.

В Universal Cup может участвовать кто угодно, но нужно заранее зарегистрировать (регистрации обрабатываются вручную) команду (как обычно в ICPС, до трех человек в команде). Так что если вы любите решать олимпиадные задачи — попробуйте порешать! По стилю задач я вдохновлялся знаменитыми Andrew Stankevich Contests и Petr Mitrichev Contests (насколько получилось — решать вам).

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

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

The Power of Two Random Choices

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

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

Интуитивно кажется, что этот метод почти не отличается от посылания запроса в случайный сервер. Условно, часто мы будем выбирать два уже нагруженных сервера, и добавлять нагрузку к ним. Но в реальности оказывается, что нагрузка на сервера становится очень равномерной. Например, в случае с 1М запросов и 1000 серверами, максимально нагруженный сервер обработает ~1002 запроса.

Если нужно еще поддерживать добавление серверов "на лету", можно использовать consistent hashing из предыдущего поста + идею с выбором одного из двух серверов. И это приводит к максимальной нагрузке в ~1007 запросов в симуляции, которую я написал.

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

Load balancing

Допустим, у вас есть 1000 серверов и много пользователей, которые суммарно посылают 1M запросов в секунду. Будем считать, что все сервера одинаковые и можно отправлять запрос на любой сервер. Как определить, куда посылать очередной запрос, чтобы максимально нагруженный сервер обрабатывал как можно меньше запросов?

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

Можно посылать запрос в случайный из 1000 серверов. Как посчитать максимальную нагрузку в таком случае? Можно выписать какие-то формулы на бумажке, но здесь олимпиада по программированию, а можно написать три строки на Python, которые проэмулируют этот процесс 100 раз, и мы узнаем, что с 99% вероятностью максимальное количество запросов будет не больше 1156. По сути это обозначает, что нам нужно будет использовать на 16% больше серверов, чем если бы мы умели распределять нагрузку идеально.

Допустим, мы хотим научиться добавлять и удалять сервера "на лету". Тогда для определения сервера можно использовать consistent hashing. Он работает так. Сопоставим каждому серверу случайное число от 0 до 1. Когда хотим отправить запрос, тоже сгенерируем случайное число, а потом найдем сервер с самым близким числом к данному, и отправим в него. Идея в том, что, если удалить какой-то один сервер, то большинство запросов все еще нужно будет посылать в тот же сервер, что и раньше.

Если проэмулировать ровно этот алгоритм (даже 1 раз, а не 100 как раньше), то окажется, что самый нагруженный сервер получит >8000 запросов. Это в 8 раз больше чем средний! Что совсем не позволительно.

Чтобы починить эту проблему применяется следующий трюк. Давайте для каждого сервера сгенерируем не одно число, а сто. Тогда симуляция показывает, что максимально нагруженный сервер получит 1363 запроса. Что гораздо лучше чем 8К, но все еще обозначает, что нам нужно будет на 36% больше серверов.

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

XOR Linked Tree

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

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

Понятно, что нужно просто запустить bfs/dfs из корня и сохранить расстояние до каждой вершины. Во время bfs нужно уметь обходить всех соседей текущей вершины. Для этого придется исходный список ребер превратить в N списков (для каждой вершины список ее соседей). Обычно N списков хранятся как Vec<Vec<usize>>, а это значит N отдельных аллокаций в heap, каждая из которых в среднем маленького размера, а такие обращения к памяти работают долго. На моем компьютере на каком-то дереве из миллиона вершин такой код работает 154мс.

Простой способ это ускорить — не делать N отдельных аллокаций, а сложить все ребра в один массив, а для каждой вершины запомнить какой отрезок массива соотвествует ребрам из этой вершины. Это работает значительно быстрее, условные 49мс на моем компьютере.

А теперь расскажу алгоритм, который работает 34мс. Для каждой вершины сохраним два числа — количество ее соседей, а также XOR всех ее соседей. Вместо того, чтобы запускать bfs, вначале найдем топологическую сортировку дерева. Будем постепенно удалять листья из дерева, пока не останется только корень. Чтобы узнать, что вершина лист — нужно проверить, что у нее ровно один сосед (и мы знаем какой, он записан в XOR). Когда удаляем лист, нужно обновить XOR и количество соседей у его единственного соседа. После того как все вершины удалены, можно пройтись по ним в обратном порядке и посчитать расстояния до корня.

Код получается примерно такой:

fn get_heights_xor_tree(edges: &[(usize, usize)]) -> Vec<usize> {
    let n = edges.len() + 1;
    let mut cnt_neighbours = vec![0; n];
    let mut xor_neighbours = vec![0; n];
    for &(u, v) in edges {
        cnt_neighbours[u] += 1;
        cnt_neighbours[v] += 1;
        xor_neighbours[u] ^= v;
        xor_neighbours[v] ^= u;
    }
    let mut queue = Vec::with_capacity(n);
    let mut parent = vec![n; n];
    parent[0] = 0;
    for mut v in 0..n {
        while cnt_neighbours[v] == 1 && parent[v] == n {
            queue.push(v);
            let p = xor_neighbours[v];
            parent[v] = p;
            cnt_neighbours[p] -= 1;
            xor_neighbours[p] ^= v;
            v = p;
        }
    }
    assert_eq!(queue.len(), n - 1);
    let mut h = vec![0; n];
    for &v in queue.iter().rev() {
        h[v] = h[parent[v]] + 1;
    }
    h
}

О каком AGI вы все говорите, если современные модели все еще не могут 3+2 правильно посчитать?

const int mod = 998244353;

В олимпиадном программировании в задачах на комбинаторику, где ответ может быть очень большим, часто просят посчитать остаток от деления этого ответа на какое-нибудь простое число (например, 998244353). Например, если ответ на задачу 10^100, то нужно вывести (10^100) % 998244353 = 876867878 вместо очень длинного числа. Идея в том, что если отстаток от деления совпал с правильным, то и исходный ответ, наверное, правильный. Но зато все вычисления можно проводить в 64-битных типах и не нужна длинная арифметика.

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

Например, чтобы посчитать x / 998244353, вначале предподсчитаем magic_number = 2^87 / 998244353 + 1 = 155014655926305585. Тогда x / 998244353 = (x * magic_number) / (2^87) = (x * magic_number) >> 87. Заметим, что x * magic_number вообще говоря не вмещатся в 64-битный тип, поэтому, если попытаться написать такой код вручную, то нужно было бы использовать 128 битную арифметику. Но на самом деле, ассемблерная инструкция imul и так при перемножении 64-битных чисел получает 128 битный результат, но кладет его в два разных 64-битных регистра. Так что для получения реального ответа нужно взять старший из регистров результата и сдвинуть его на 87 - 64 = 23 бита.

Хорошо что нынче не нужно понимать все это самому, и компилятор может это соптимизировать за нас!

Но буквально вчера обнаружил, что если объявить модуль как int mod = 998244353;, а не const int mod = 998244353;, то компилятор перестает делать эту оптимизацию, использует инструкцию idiv, и код становится в полтора* раза медленнее.

Идея в том, что если не добавить модификатор const, то, даже если мы никогда не изменяем переменную, компилятор не имеет права думать, что она всегда будет одинаковой. Например, мы можем в другом файле написать extern int mod;, а потом ее поменять. При этом код в исходном файле должен продолжить работать и использовать новое значение.

Так что когда объявляете модуль, всегда используйте const: const int mod = 998244353!

Weighted sampling without replacement

Вернёмся к скучным постам про алгоритмы. Допустим у нас есть N объектов, где объекту i сопоставлен какой-то вес w[i]. Мы хотим сгенерировать перестановку из этих элементов в соответствии с весами. Изначально возьмем пустой массив и будем добавлять в него элементы. Каждый раз добавляем случайный элемент, который еще не добавлен в массив. При этом вероятность взять элемент i должна быть пропорциональна w[i]. Как это сделать быстрее чем за O(N^2)?

Как спортивный программист я умею это делать с помощью дерева отрезков на сумму. Изначально запишем в ячейку i число w[i]. Чтобы выбрать очередной объект, посчитаем текущую сумму в дереве отрезков S, сгенерируем случайное число R от 1 до S. А потом c помощью спуска по дереву найдём наименьший префикс p такой, что сумма в ячейках 1..p хотя бы R. Добавим число p в ответ, а в дереве отрезков запишем туда 0 вместо w[p]. Повторим так N раз. Суммарно это работает за O(N log N).

Этот способ работает, но он довольно сложный. Оказывается можно сделать все тоже самое гораздо быстрее и за несколько строк кода.

Рассмотрим следующий алгоритм. Для каждого объекта i сгенируем случайное вещественные число r[i] от 0 до w[i]. А потом отсортируем все объекты в порядке убывания r[i]. Утверждается, что это и есть перестановка, которую мы хотели найти.

Например, если объекты i и j имели одинаковые веса, то i окажется раньше j в финальной перестановке с вероятностью 50%, как и нужно.

Если объект i имел вес больше чем j, то в среднем r[i] окажется больше чем r[j], и i в среднем окажется раньше в перестановке чем j, как и нужно.

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

Но оказывается, что можно немного изменить способ генерирования r[i], и метод начинает правильно работать! Расскажите в комментариях как исправить решение.

ICPC World Finals 2024

Привет всем новым подписчикам! Посты про ML это, конечно, хорошо (кстати, мы выложили решения, которые модель писала для задач с IOI), но до недавнего времени ML в моей жизни было довольно мало. На работе в основном я делал инфраструктуру для всяких распределенных высоконагруженных вычислений (как, впрочем, и сейчас), поэтому в канале были посты про всякие перформанс штуки. А еще я очень много увлекался всякими олимпиадами по программированию, иногда даже проводил свои.

Одна из самых больших и важных олимпиад по программированию — чемпионат мира по программированию среди студентов ICPC (в далеком 2015, будучи членом команды университета ИТМО, я даже его выиграл 🏆). Соревнование проходит каждый год, и финал в этом году будет в Астане уже завтра! Начинается в 11 утра по местному времени. На этом youtube канале будет трансляция с ведущими, аналитикой и всем таким. По идее должно быть понятно даже если вы никогда не участвовали сами в подобных олимпиадах. Так что рекомендую посмотреть, вдруг будет интересно!

P. S. И раз уж вы подписались на мой канал, рекомендую почитать историю про то, как я писал программу, которая автоматически собирает абсолютно белый пазл по фотке с телефона: раз и два.

10'000 обезьян и 🥇IOI

Я уже пару месяцев как работаю в OpenAI, так что времени на посты сюда почти не осталось. Нужно исправляться. Вчера мы выпустили новую модель, которая думает перед тем как отвечать. Я даже успел попасть в список контрибьюторов. Но пост не об этом — хочу рассказать про результат, который упоминается в посте про новую модель, кажется мне очень неочевидным, но мало обсуждаемый.

Как известно, если 10000 обезьян посадить за пишущие машинки, и дать им бесконечно времени, то рано или поздно они возьмут золото на IOI. Наша новая модель гораздо лучше справляется с задачами, где нужно думать, чем все предыдущие модели, но все еще в абсолютных значениях делает это довольно плохо. Ее рейтинг CodeForces оценивается примерно в 1800, и это очень далеко от того, чтобы взять даже бронзовую медаль на IOI.

Нам стало интересно, можно ли просто увеличив количество вычислений, добиться лучших результатов. Сетап был такой. Давайте модель попросим 10000 раз решить каждую задачу, а потом выберем лучшие решения. Интуитивно кажется, что для решения сложных олимпиадных задач обычно нужно придумать какую-то красивую идею, и, если модель имеет CF рейтинг 1800, то от увеличения количества попыток, особо ничего не поменяется. Она просто не сможет ее придумать.

На практике же оказалось все наоборот. Среди 10000 попыток оказываются такие, когда модель случайно подумала в нужную сторону, и придумала правильную идею. В итоге, если отфильтровать самые лучшие попытки, то их достаточно, чтобы получить золото на IOI (и мне кажется это очень крутой результат!). Правда, как именно находить лучшие решения, если у вас нет возможности протестировать их все, не очень понятно.

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

А у меня очень крутая жена, и она недавно получила заслуженное повышение до Staff Engineer в Meta, очень ей горжусь! 🎉

Physics of Language Models

Я в своей жизни ML занимался довольно мало, но в последнее время решил все-таки по-лучше разобраться. Так что иногда (частота зависит от количества лайков 👍) буду постить краткие пересказы статей/докладов, которые мне показались интересными.

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

В докладе Physics of language models авторы тренируют относительно маленькие модели (100М параметров) на синтетических данных, и смотрят, какие задачи LLM могут решать, а какие нет.

Например, оказывается что LLM даже теоретически не могут научиться отвечать на вопрос вида "Правда ли, что Байден родился в четном году?" при том, что они прекрасно знают в каком году он родился, и знают, какие числа четные. Оказывается, что дело в порядке токенов. Если бы ответ был в формате "Байден родился в году 1942, это четное число, ответ да", то все бы работало. Но если хочется получить ответ в формате "Да, потому что он родился в ...", то в момент написания первого токена у LLM еще не будет числа 1942 "в контексте" и она не сможет выбрать правильный ответ. И такая проблема есть у любых моделей вне зависимости от размера.

По аналогичным соображениям, если в датасете было написано только "X родился в городе Y", то модель никогда не сможет научиться правильно отвечать на обратный вопрос "кто родился в городе Y?" (потому что в "памяти" модели будет мапинг X->Y, но не в обратную сторону).

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

Шахматы

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

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

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

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

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

Интересно, топовые игроки уже давно имеют такие программы или это почему-то не работает?

P. S. на картинке у Яна осталось больше 10 минут времени, а у Алирезы меньше минуты (оба начинали с 10 минутами, и +2 секунды дают за каждый ход).

Lambdaman. Решение.

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

Как сгенерировать случайную строку? Можно использовать линейный конгруэнтный генератор. Звучит страшно, но по сути мы просто фиксируем две константы (например, mult=16807, mod=2147483647) и какой-то изначальный seed. Каждый раз, когда нужно сгенерировать случайное число от 0 до N, делаем seed = (seed * mul) % mod, а потом возвращаем seed % N.

Дальше мы можем пытаться подобрать изначальный seed такой, который посетит все клетки. Как оценить вероятность того, что мы сможем подобрать такой сид? Математику я знаю плохо, но зато могу написать код и проверить :) Я перебрал миллион различных сидов, и самый лучший посетил 4694 из 4999 клеток лабиринта.

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

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

Я нашел решение в таком формате где-то за 10 минут. Важно было перебирать не только разные стартовые seed, но и пробовать различные mult. В лучшем решении на контесте участники пошли еще дальше и вместо подcтрок "LL", "RR", "UU", "DD", нашли решение в виде конкатенации строк "LLUU", "LLDD", "RRUU", "RRDD", "UULL", "UURR", "DDLL", "DDRR" в случайном порядке. На практике такое решение можно найти быстрее чем за минуту. Видимо, идея в том, чтобы реже возвращаться обратно.

Lambdaman

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

Нужно написать программу на выдуманном функциональном языке программирования, которая выведит строку из миллиона букв LRUD (left, right, up, down). После этого робот пытается по порядку выполнить каждое действие. Если в клетке, в которую хочет пойти робот, находится стена, то он просто стоит на месте. Тест считается пройденным, если в итоге робот посетил каждую клетку.

Сложность в том, что ваше решение оценивается по тому, насколько короткую программу вы написали (а не по тому, насколько долго робот ходил). Например, можно заранее предподсчитать правильный путь, и написать программу println "LRLLRLU...", но она получит мало баллов.

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

Интересно, что лучшее решение участников для этого теста умещалось где-то в 150 символов. Отгадайте как?

P. S. спасибо жене за подбор гармоничных цветов для картинки 🤍.

ICFPC 2024

В эту пятницу начинается 72 часовое командное соревнование ICFPC: https://icfpcontest2024.github.io/, всем рекомендую поучаствовать!

Каждый год у него новые организаторы, поэтому качество и интересность контестов может быть существенно разным, но бывают очень хорошие года!

Чтобы проникнуться духом соревнования можно почитать мой write-up 2022 года: https://t.me/bminaiev_blog/16 или посмотреть на сайт 2020 года (этот год был очень крутым!): https://icfpcontest2020.github.io/#/ и почитать write-up одной из команд https://users.livejournal.com/-adept-/133986.html

Code Weekend #1. Результаты!

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

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

На время контеста я арендовал мощный сервер (и заплатил где-то 200$ за него), но в итоге он никогда не был нагружен больше чем на несколько процентов (несмотря на то, что у нас было 200 команд, которые отправили 175000 посылок).

А еще у нас в контесте участвовали очень топовые ребята. Например, Psyho, wata и nika!

В общем надеюсь всем понравилось. Stay tuned for Code Weekend #2!

Code Weekend #1. Призы!

Code Weekend #1 начнется уже через 10 часов! Благодаря TON Foundation у контеста появился призовой фонд размером 1700TON, что по текущему курсу больше 12 500$!

Мы решили раздать призы не только лучшим участникам в финальном скорборде, но и лучшим в других номинациях. Например, каждую минуту соревнования мы будем давать 0.1 TON команде, которая в конкретную минуту находится на первом месте. Так что если вы готовы быстро разобраться в задаче и написать простое решение, то тоже можете побороться за призы!

Еще у нас будут призы за лучшее решение по каждому отдельному тесту и за топ-1 после первых 24 часов контеста.

Больше информации про призы тут: https://codeweekend.dev/

Code Weekend #1

Вместе с Ромой и Геной мы решили провести командный оптимизационный контест. Для участия регистрируйтесь на сайте https://codeweekend.dev/ и вступайте в дискорд https://discord.gg/QkzjumPdbq.

Будет одна задача по стилю похожая на Google HashCode и сколько-то открытых тестов. Вы можете решать тесты любым способом, а потом отправлять свои ответы в систему. Контест будет длиться двое суток и начнется вечером 7 июня. Через сутки после начала мы усложним задачу и добавим новых тестов. Так что если в первый день вам покажется слишком просто, приходите на следующий день :)

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

Invalid status code: 429 Too Many Requests

Последнее время стал довольно много пользоваться ChatGPT, чтобы дебажить какие-то штуки, в которых плохо разбираюсь. Например, однажды пытался сформировать руками (не спрашивайте зачем) gRPC сообщение, которое почему-то не парсилось сервером. Скормил сырые байты запроса ChatGPT и он смог найти в них баг!

Сегодня хотел узнать, что обозначает "grpc-status": "12" и получил лакончиный ответ ERROR: Invalid status code: 429 Too Many Requests. После этого минут двадцать пытался понять, где мой сервер может вернуть такой ответ. Ничего не нашел, и решил в гугле перепроверить, нашел вот этот сайт, где написано, что 12 это "UNIMPLEMENTED". Это имело гораздо больше смысла, и я сразу нашел баг в своем запросе.

Я долго не мог понять, почему ChatGPT решил мне соврать на таком простом вопросе. Разгадка нашлась, когда я задал какой-то совсем не связанный вопрос и опять получил ответ ERROR: Invalid status code: 429 Too Many Requests. Тут я и понял, что это были не ответы на мои вопросы, а ошибки от API.

Чтобы это была не просто смешная история, то пусть тут будет какая-то мораль. Используйте тип Result<Ok, Failure>, а не просто String и для успеха и для ошибки.

CF 942D. Решение.

Условие задачи.

1. Первая идея довольно стандартная, но все равно красивая. Пусть для любой пары чисел (x, y) мы умеем за быстро определять, можно ли x превратить в y. Найдем в тупую минимальное число, в которое можно превратить a[0] и превратим. Потом сделаем тоже самое для a[1], но начиная проверять только с a[0]. Хоть для каждого конкретного числа мы можем проверить O(n) вариантов, суммарно мы проверим не O(n^2) вариантов, а только O(n).

2. Как проверять, можно ли получить y из x? Сделаем граф, в котором проведем ребро из i в next[i]. Такой граф состоит из циклов и деревьев, которые к ним подвешены. Давайте для каждого цикла веберем какую-то вершину root, удалим ребро root -> next[root], получим дерево с корнем в root. В таком графе проверка "можно ли x превратить в y" это тоже самое, что вершина x лежит в поддереве y. А это стандартная задача, нужно обойти дерево с помощью dfs, для каждой вершины i запомнить время входа tin[i] и выхода tout[i] из нее. Тогда условие x в поддреве y эквивалентно tin[y] <= tin[x] <= tout[y].

3. Если вспомнить, что ребро root -> next[root] все-таки существует, то чтобы определить достижимость y из x нужно рассмотреть два варианта. Либо x лежит в поддереве y, либо next[root] лежит в поддереве y.

4. Как просто выбрать root для каждого цикла? Можно сделать это в три строки кода с помощью DSU (функция union(x, y) добавляет ребро x-y и возвращает true, если x и y находились в разных компонентах связности).

for i in 0..n {
  if !dsu.union(i, next[i]) {
    // mark `i` as root 
  }
}

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

CF 942D

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

Если выкинуть неинтересные детали, то условие такое. Дан массив a длиной 10^6 из чисел от 0 до N-1 и массив next (длиной N с числами от 0 до N-1). Можно любое количество раз заменить a[i] на next[a[i]] для любого i (причем можно применять операцию для одной и той же позиции несколько раз). N=10^6. Спрашивается, можно ли сделать массив a неубывающим?

Тем временем прошло полтора часа контеста, и в топ-4 две команды из Украины 🥳

ICPC World Finals Luxor

Приехал в Египет потусить на финале ICPC (самая масштабная олимпиада по программированию среди студентов). Для меня это возможность не только вспомнить молодость (жесть, уже 10 лет прошло с моего первого финала), но и в одном месте увидеть кучу людей из олимпиадной тусовки, которых давно не видел. Очень круто!

Из-за ковида расписание финалов ICPC сдвинулось, поэтому сейчас проходит одновременно два — за 2022 и 2023 год. Само соревнование длится 5 часов и начнется завтра в 12 дня по местному времени.

На YouTube будет трансляция с ведущими и гостями, должно быть интересно.

Еще будет трансляция, где Гена, Петя и Кевин (все очень крутые олимпиадные программисты) будут решать те же задачи, что и участники, но не официально. Тоже рекомендую посмотреть!

Полезные ссылки:
- Таблицы результатов.
- Список участников с рейтингами на КФ: 2022 и 2023.

Beam Search

В эвристических контестах есть два алгоритма, которые чаще всего используются. Simulated Annealing (отжиг), о котором я уже писал раньше. И beam search. Расскажу о нем на примере задачи из предыдущего поста.

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

В этом массиве будет уже 400 различных полей, которые можно получить за два хода. Можно было бы так продолжать дальше, но размер этого массива будет расти экспоненциально. Поэтому давайте на каждом шаге оставлять только X лучших полей из массива. Как определять хорошесть полей? Когда мы поставили штампы в клетки (1, 1) и (1, 2), то мы знаем, что значения в этих клетках никогда не поменяются, поэтому можно максимизировать сумму значений в них.

Допустим мы хотим улучшить решение и ставить в каждую клетку от 0 до 2 штампов (но при этом по условию нельзя использовать суммарно больше 81). Как оставлять X лучших решений, если они используют разное количество штампов? Вместо одного вектора на Х элементов, можно сохранить X/81 лучших для каждого количества использованных штампов.

На практике чем больше Х, тем лучше скор вы получите. Поэтому очень важно сделать решение как можно более эффективным.

Например, как выбрать Х лучших полей для следующей итерации? Можно сложить все варианты в вектор, отсортировать, а потом оставить Х лучших. Но гораздо более эффективно добавлять новые элементы в PriorityQueue, которая хранит не больше Х элементов. Тогда для большинства вариантов можно сразу увидеть, что они хуже чем текущий Х-й вариант в PriorityQueue и не добавлять его в новый слой.

Другая важная перформанс оптимизация — хранить в PriorityQueue объекты размера О(1) байт, а не весь стейт целиком. Например, если к полю 9х9 мы применяем штамп размера 3х3, но в итоге пытаемся найти лучшие стейты только исходя из значений в конкретной клетке, то нет смысла копировать весь стейт из 81 интов и применять 9 сложений. Достаточно посчитать значение в конретной клетке и запомнить как восставновить весь стейт целиком.

С аккуратной реализацией этого алгоритма можно было легко попасть в топ-10 AHC 032. Если добавить оптимизацию для правого нижнего прямоугольника 4х3 из предыдущего поста, можно было получить топ-1 скор.

AtCoder Heuristic Contest 032 (решение)

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

Можно идти сверху вниз слева направо и в клетку (r, c) жадно ставить штамп, который делает значение в клетке (r, c) максимальным (не обращая внимание на клетки снизу и справа). Если у нас каждый раз есть выбор из 20 различных штампов, то значения в клетках будут примерно 19M/20, что достаточно хорошо. Но в последних двух строках и столбцах будут случайные числа, это плохо.

Чтобы лучше понимать текст, удобно смотреть на gif-ку из предыдущего поста.

1. Жадно (на самом деле с помощью beam-search) расставим штампы в левом верхнем квадрате 5х5.
2. Подберем 4 штампа, которые поставим в клетки (1, 6) и (1, 7), которые максимизируют значения в клетках (1, 6..9). Аналогично подберем 4 штампа для клеток (2, 6..9). И.т.д до клеток (5, 6..9).
3. Симметрично решим четверку (6..9, 1) ставя штампы в клетки (6, 1) и (7, 1). Дальше четверку (6..9, 2). И.т.д. до (6..9, 6).
4. Осталось решить прямоугольник 4х3: (6..9, 7..9). Но у нас есть только две позиции, в которые можно ставить штампы (6, 7) и (7, 7). Поэтому поставим по 5 штампов в каждую из клеток. Идея в том, что мы получим примерно 20^10 случайных прямоугольников 4х3 и какой-нибудь из них окажется с большой суммой.

Как выбрать лучший из 20^10 вариантов? Сгенерируем все возможные способы поставить 5 штампов в клетку (6, 7) и оставим только 1000 лучших по сумме в клетках (6, 7..9). Аналогично сгенерируем все варианты для клетки (7, 7) и оставим 1000 лучших по сумме в клетках (9, 7..9). Дальше переберем все пары.

P. S. как вообще писать посты про решения задач, чтобы их было интересно читать людям, которые сами не решали эту задачу?

AtCoder Heuristic Contest 032

Написал тут 4 часовой эвристический (в задаче нужно найти не абсолютно правильный ответ, а просто как можно лучший) контест на AtCoder, очень понравился опыт. Расскажу критерии, которые делают участие более приятным.

1. Простое и понятное условие задачи. Формула для подсчета скора очень простая.
2. Все тесты сгенерированы с помощью простого генератора, который доступен участникам (поэтому можно тестировать решение локально). Не известны только randseed-ы финальных тестов.
3. Есть визуализатор, которым удобно пользоваться. Даже в простой задаче, где все состояние это массив 9х9, он пригодился.

Условие задачи было такое. Поле 9х9 заполнили случайными числами от 0 до M=998244353. Сгенерировали 20 случайных "штампов" размера 3х3 со случайными числами от 0 до M. Вы можете не более 81 раза приложить любой штамп в любое место поля (но он не должен выходить за границы). Когда прикладывается штамп, к числам на поле добавляются числа со штампа.

В конце все числа на поле берутся по модулю M. Ваш скор — сумма этих остатков. Его нужно максимизировать.

В комментарии будет gif-ка с визуализацией моего решения (правда Telegram ее немного криво отображает).