Summary of the year for the channel "Запрети мне псевдолейблить" from @TGStat

Люкс войскам приготовиться

Фикс успешно влили в мастер. Теперь я контрибьютор еще и в дагстер
https://github.com/dagster-io/dagster/pull/33227/files

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

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

От этого @pseudolabeling немножко меньше утонул в глобальном ладдере

Посвещается @ArtemVeshkin @markdjadcnhenko @artyomjk которых шейкнуло с 10 места на 38 в CSIRO - Image2Biomass Prediction сегодня ночью и которые не все стали кагл мастерами

Если со мной часто пить кофе, то можно получить бесплатные идеи

https://huggingface.co/spaces/AlexWortega/hr-breaker

HR-breaker теперь в общем доступе

Заняли 47 место в упаковке елок в квадрат. Вернулся на 4 страницу рейтинга (382 место) в компетишнах, но как-то не ощутимо приблизился к гранд мастеру.

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

В жизни пару раз встречался с задачами упаковки объектов и всегда казалось, что каждый раз нужно изобретать костыли и писать очередной Branch & Bound. Ну так вот вывод: надо!

#santa2025
И так, наша первая идея для решения санты 2025, которая до сих пор работает, но почему-то не очень популярна в комьюнити. Ну или Вехденская правда придумал ее едиственный.

TLDR: сведем задачу упаковки к LP

Перва проблема сведения- это то, что ёлки то сами по себе не очень-то и выпуклые фигуры, а для решения LP надо фигуры иметь выпуклые. Тогда представим елку как минимальный набор выпуклых фигур (на рисунке), относительно которых можно собрать систему уравнений: порежем елку на фигуры и сделаем вид, что они друг к другу приклеены.
Для пары елок будем иметь 16 ограничивающих уравнений, но нам елки нужно сравнивать только попарно, так что количество уравнений не станет запредельным.
Тогда для каждой прямой описывающей каждый многоугольник будем иметь

a x + b y + c = 0

Т.е. линейное ограничение. Если вдруг мы елку хотим двигать на (d_i, d_j), то каждое индивидуальное уравнение приобретет вид

a·dx_i + b·dy_i − a·dx_j − b·dy_j ≤ k

Где k будет как раз нашим зазором между елками. Чем больше зазор- те больше 'воздуха' в нашем квадрате.

Тогда сведение к LP будет:
1. Как переменные иметь сдвиги всех фигур + сторона квадрата
2. Сторону квадрата мы минимизируем
3. Каждую фигуру можно двигать так, чтобы она все еще находилась в квадрате и не пересекалась с другими ёлками.

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

Опять же, не надо шагать в глобальный оптимум сразу. Лучше применить алгоритм несколько раз и делать сдвиги на какой-то коэффициент [0, 1], чтобы найти более глобальный оптимум. Тут аналогия как с другими оптимизаторами, где не надо торопиться.

Таким образом команда @pseudolabeling примерно каждое решение могла немного улучшить в ~четвертом знаке

Код можно вот тут потыкать и обойти текущий лучший паблик, чтобы поднять чсв

Еще Вехденская правда планирует стрим с объяснением обсуждением этого в 21:00 по мск.