ICPC World Finals Luxor

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

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

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

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

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

CF 942D

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

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

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 
  }
}

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

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 и для успеха и для ошибки.

Code Weekend #1

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

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

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

Code Weekend #1. Призы!

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

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

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

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

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

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

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

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

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

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

ICFPC 2024

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

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

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

Lambdaman

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

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

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

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

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

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

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" в случайном порядке. На практике такое решение можно найти быстрее чем за минуту. Видимо, идея в том, чтобы реже возвращаться обратно.

Шахматы

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

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

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

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

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

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

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

Physics of Language Models

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

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

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

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

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

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

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

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

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

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

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

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

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

ICPC World Finals 2024

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

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

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

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], и метод начинает правильно работать! Расскажите в комментариях как исправить решение.

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!

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

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
}