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 можно довольно хорошо решать олимпиадные задачи.

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!