Гамильтонов цикл.

Вчера читал статью на викиконспектах итмо про нахождение гамильтонова цикла наименьшей стоимости. В статье приведен псевдокод, а вот мой вольный перевод на С++:

double findCheapest(int i, int mask) {
  if (d[i][mask] != inf) return d[i][mask];

  for (int j = 0; j < N; j++)
    if ((mask & (1 << j)) != 0)
      d[i][mask] =
          std::min(d[i][mask], findCheapest(j, mask - (1 << j)) + w[i][j]);

  return d[i][mask];
}

double start() {
  for (int i = 0; i < N; i++)
    for (int mask = 0; mask < (1 << N); mask++) d[i][mask] = inf;
  d[0][0] = 0;
  return findCheapest(0, (1 << N) - 1);
}

Отгадайте за сколько он работает?

Правильно, за θ(n!). Например, если в графе вообще нет гамильтонова цикла, то все d[i][mask] будет равны inf и каждый раз будут вычисляться заново. А теперь давайте представим, что между всеми вершинами в графе есть ребра. За сколько будет работать теперь?

Неправильно, все еще за θ(n!). Отгадайте почему.

Если вы смотрите на этот код уже 5 минут, и не верите мне, то попробуйте запустить его локально: https://pastebin.com/ZhzYqRmx

Contest platform

Будем считать, что после вчерашнего поста все уже умеют решать задачу коммивояжера быстрее чем за n!, а значит вы можете помочь мне протестировать тестирующую систему!

Мне очень нравился формат задач на Google HashCode (никак не связано с тем фактом, что мы его два раза выиграли :). Там давали какую-то задачу, у которой нет точного решения, и тесты, которые нужно решить. Тесты давались в открытом виде, т.е. их можно скачать, посмотреть на них, как-то повизуализировать, найти какие-то закономерности и как-то сгенерировать для них ответы. Причем нет почти никаких ограничений на то, как именно ответы должны быть получены. Можно хоть в Excel решать!

К сожалению, Google HashCode больше не проводится :(

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

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

Поэтому я решил написать свою платформу, на которой можно было бы проводить такие соревнования. Уже даже есть сайт, на котором можно попробовать решить тестовую задачу: https://bminaiev.github.io/contest-platform/

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

P. S. задача, конечно, тестовая, но написать для нее нормальное решение тоже может быть интересно!

slice.reverse

Вчера решал задачу на КФ, где нужно было уметь делать следующее. Дана строка длиной 2*10^5 символов, к ней нужно применить 2*10^5 операций. Каждая операция — развернуть какой-то подотрезок этой строки. TL=1с.

Это довольно известная задача, которую можно решать, например, с помощью декартового дерева за O(log n) на запрос.

После контеста в комментариях рассказали прикольный трюк, как можно получить АС с решением, которое делает O(n) операций на запрос. Вместо того чтобы просто хранить строку s, будем еще дополнительно хранить ее развернутую копию s_rev. Тогда, чтобы развернуть подстроку s[fr..to], можно просто скопировать готовую подстроку из s_rev:

fn reverse(&mut self, fr: usize, to: usize) {
let n = s.len();
let s = &mut self.s[fr..to];
let s_rev = &mut self.s_rev[n - to..n - fr];
s.swap_with_slice(s_rev);
}

Например, s='abcde'. Сохраним s_rev='edcba'. Как развернуть подстроку s[1..3]='bc'? Поменяем ее с s_rev[(5-3)..(5-1)]='cb'. Теперь s='acbde', а s_rev='edbca'.

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

Это решение получало АС за 889мс. Потом оказалось, что в задаче плохие тесты и на самом деле оно работает в 2 раза дольше, но все равно довольно быстро!

Самое смешное, что решение, которое просто вызывает .reverse на нужной подстроке (правда с указанием, что нужно использовать avx2) работает еще в два раза быстрее:

#[target_feature(enable = "avx2")]
unsafe fn reverse(s: &mut [u8]) {
s.reverse();
}

Running Transformers using SMPC

Почти год назад я написал пост про SMPC (Secure multi-party computation) — технологию, которая позволяет запускать вычисления на данных нескольких участников таким образом, что все узнают итоговый результат вычислений, но при этом ничего не могут понять про исходные данные других участников.

План был в том, чтобы написать три поста:
1. Смотрите, какая прикольная вещь, можно не раскрыть ни одного бита информации про свои данные, но все равно посчитать что-то интересное.
2. На самом деле делать такие вычисления довольно сложно, потому что это накладывает кучу ограничений.
3. Несмотря на то, что это сложно, можно все равно делать довольно сложные вещи с помощью SMPC — например, тренировать ML модели не раскрывая исходных данных.

Но второй пост я так и не написал, потому что сложно простыми словами доказывать, что что-то делать сложно :)

Зато теперь есть третий пост, где мы рассказываем как надо запускать трансформеры на SMPC, когда у вас нет if-ов, циклов, чисел с плавающей точкой и всего такого: https://www.pyte.ai/blog/making-transformers-based-ai-algorithms-secure-using-secure-multi-party-computation-smpc

Lazy Fenwick Tree

Чтобы канал не пустовал расскажу о простом трюке, который возможно не все знают. Допустим нам нужна структура данных, которая умеет поддерживать массив чисел a и обрабатывать две операции:
+ l r x. Ко всем элементам на отрезке l..r добавить число x.
? pos. Узнать значение элемента a[pos].

Это стандартная задача, которая решается деревом отрезков или деревом Фенвика. Обе структуры данных используют O(n) памяти, где n — размер массива a.

Что делать, если мы хотим обрабатывать такие же запросы, но для массива размером 10^9 элементов? Если все запросы известны заранее, то можно сжать координаты и свести задачу к предыдущей. А если нет, то можно написать Dynamic Segment Tree, в котором вершины дерева отрезков инициализируются в первый момент, когда к ним происходит обращение. Но в этом случае придется написать кода в несколько раз больше чем в обычном дереве Фенвика.

На самом деле можно все еще использовать дерево Фенвика, но хранить значения не в векторе, а в хеш таблице. Такая структура данных будет занимать O(Q * log(MAX_C)) памяти, где Q — количество запросов, а MAX_C — размер массива a. При этом код почти не отличается от обычного дерева Фенвика:

struct LazyFenwick {
    data: FxHashMap<i32, i32>,
    n: i32,
}

impl LazyFenwick {
    pub fn get_sum(&self, mut pos: i32) -> i32 {
        let mut res = 0;
        loop {
            res += self.data.get(&pos).copied().unwrap_or_default();
            pos = pos & (pos + 1);
            if pos == 0 {
                return res;
            }
            pos -= 1;
        }
    }

    pub fn add(&mut self, mut pos: i32, change: i32) {
        while pos < self.n {
            *self.data.entry(pos).or_default() += change;
            pos |= pos + 1;
        }
    }
}

Другой подход, который я подсмотрел в https://contest.ucup.ac/submission/229077, написать bottom-up дерево отрезков, которое тоже хранит значения в хеш-таблице:

ll N, Q;
unordered_map<ll, ll> seg;
void add(ll L, ll R, ll x) {
    L += N; R += N;
    for(; L < R; L >>= 1, R >>= 1) {
        if(L & 1) seg[L++] += x;
        if(R & 1) seg[--R] += x;
    }
}
ll get(ll i) {
    i += N;
    ll ans = 0;
    do ans += seg[i]; while(i >>= 1);
    return ans;
}

Telegram ML Competition. Решение.

Первая часть.

Я начал с того, что попытался собрать какой-то датасет из реальных кусков сообщений, которые люди оборачивают в кавычки. Скачивать реальные чаты через API мне показалось плохой идеей (явно же забанят довольно быстро), поэтому вместо чатов я скачивал каналы, которые можно смотреть по ссылке типа https://www.tgoop.com/s/bminaiev_blog, которая не требует авторизации.

Я не нашел какого-то нормального списка из всех существующих каналов, поэтому я руками набрал какой-то небольшой список исходных каналов, а потом в них смотрел на репосты или ссылки на другие каналы и добавлял их в очередь для скачивания и так по кругу. В итоге у меня набралось порядка миллиона каналов, для каждого из которых я распарсил сколько-то последних сообщений, которые видны при открытии канала через www.tgoop.com/s/.

Из этого датасета было довольно очевидно, что большинство вещей, которые обернуты в кавычки, это какой-то трэш, а не код. И если оценивать будут действительно количество правильно определенных текстов, то сделать решение, которое работает лучше, чем return OTHER; довольно сложно. Спойлер: всего два участника из ~100 написали что-то лучшее чем такой бейзлайн.

В этот раз у меня было довольно мало времени на участие в контесте, поэтому от идеи "нужно натренировать какую-нибудь маленькую модель и научиться ее запускать через что-нибудь типа llama2.c" я очень быстро дошел до "нужно за выходные написать хоть что-то работающее хотя бы на каком-то наборе языков".

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

Чтобы быстро решить вторую проблему, я просто выкинул большинство языков программирования и оставил ~10 самых популярных. Понятно, что можно сделать что-то лучше (например, ввести какие-нибудь веса для языков программирования), но когда времени мало, и так сойдет.

Чтобы побороться с первой проблемой я вначале думал просто добавить условие "если никакой язык программирования не набрал скор лучше какого-то барьера, то верни OTHER". Но из-за того, что трэша в датасете было много, работало это так себе. В итоге я нашел список ключевых слов для каждого языка программирования и сказал, что если в тексте нет ни одного ключевого слова, то он OTHER. Пришлось еще немного обработать эти списки и убрать из него слова типа "in", "or", "not". После этого результат получился уже относительно неплохой.

Рассказ получился длинный, но надеюсь кому-нибудь было интересно :)

Интересные Telegram каналы

Расскажу историю, которая стремительно теряет свою актуальность в течении последних суток. Где-то полгода назад, вдохновившись своими (уже бывшими 😢) коллегами, я перестал пользоваться твиттером, инстаграмом, фейсбуком и большинством других социальных сетей. Но совсем не отвлекаться сложно, поэтому я решил вместо этого читать технические Telegram каналы. Во-первых, на это тратится сильно меньше времени. Во-вторых, вместо мемов хоть прочитаю что-то полезное.

Проблема с этой идеей была в том, что в Telegram довольно сложно находить интересные каналы. Я давно и с интересом читаю каждый пост в Experimental Chill. Но как найти каналы с похожем по качеству контентом — неясно.

Я быстро нашел много каналов про Machine Learning (они часто ссылаются друг на друга). Начиная от более попсовых типа Сиолошная или Время Валеры до более маленьких типа Wazowski Recommends или Information Retriever. Но в ML я разбираюсь довольно плохо, так что хотелось еще найти каналов про performance оптимизации, Rust или даже C++.

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

В предыдущем посте я научился получать длинный список около-программистских Telegram каналов и парсить посты из них. Я скачал где-то 100к постов и посчитал для них эмбеддинги через OpenAI API. Изначально я думал научиться считать эмбеддинги локально через какую-нибудь open source модель, он оказалось, что эмбеддинги у OpenAI API стоят супер дешево (суммарно потратил меньше 5$).

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

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

Пока тестировал бота, подписался на кучу новых каналов, посмотрим насколько будет интересно их читать. Выделить какие-то конкретные сложно, но пусть будет Записки cpu designer'а, Графики каждый день, C++95, MLE шатает Produnction и PLComp.

А на какие интересные каналы подписаны вы?

Вместо очередного технического поста, в качестве итогов 2023 года, тут будет фоточка со свадьбы! ❤️

Osijek Competitive Programming Camp, Winter 2024

С 17 по 25 февраля пройдет Osijek Competitive Programming Camp, Winter 2024. В один из дней будет контест, который подготовил я. Потратил кучу времени, но надеюсь, что задачи получились необычными и интересными (и сложными). Так что студентам рекомендую поучаствовать в этих сборах!

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

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

Kaggle. Собираем кубик Рубика NxNxN.

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

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

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

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

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

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

Stress testing

Допустим вы написали решение к какой-то олимпиадной задаче, отправили его на проверку, получили "wrong answer", прочитали код и не нашли баг. Что делать дальше?

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

Тут довольно хорошо описан типичный "плохой" и "хороший" способы. Постараюсь объяснить почему на самом деле все наоборот. В посте предлагается делать три отдельных программы — генератор, решение и медленное решение. И еще дополнительно написать скрипт, который все запускает.

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

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

Я обычно пишу все четыре части в одном месте, код получается примерно такой:

fn gen(rng: &mut Random, max_n: usize) -> Input { ... }
fn solve(input: &Input) -> Output { ... }
fn solve_slow(input: &Input) -> Output { ... }

fn main() {
    const MAX_N: usize = 10;
    for seed in 1.. {
        dbg!(seed);
        let mut rng = Random::seed_from_u64(seed);
        let input = gen(&mut rng, MAX_N);
        let output = solve(&input);
        let slow_output = solve_slow(&input);
        assert_eq!(output, slow_output);
    }
}

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

После того как плохой тест найден, можно попробовать уменьшить MAX_N и найти минимальный тест.

Допустим решение упало на 100500-м тесте и мы хотим его подебажить. Можно просто заменить строку for seed in 1.. на for seed in 100500.. и тогда этот тест сгенерируется первым.

Сразу отвечу на потенциальные вопросы:

1. Обычно решение написано таким образом, что оно читает тест из stdin, а тут тест передается как уже готовая структура данных. Придется переписать эту часть solve?
Полезно сразу писать решение в формате, когда чтение инпута и решение это отдельные части, тогда такой проблемы нет.

2. Решение может использовать какие-то глобальные переменные, тогда так писать стресс нельзя.
Не используйте глобальные переменные.

Remote Work

Когда я только присоединился к Pyte, открыл в VSCode репозиторий с кодом и попытался что-то написать, все очень сильно тормозило. Я привык пользоваться автодополнением, но тут подсказку от rust-analyzer нужно было ждать где-то по 8 секунд. Как можно так работать я не понял, и попытался это пофиксить.

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

Самый эффективный способ ускорить cargo check в таком случае — разбить код на несколько независящих крейтов. Тогда, после изменения файла, проверка будет происходить для текущего крейта и для всех других, которые его используют. Но соседние крейты перепроверять не нужно. Это помогло ускорить автодополнение где-то в 3 раза. Гораздо лучше, но все равно медленно.

Ещё в три раза получилось ускорить более простым способом — вместо ноутбука я купил себе стационарный компьютер с сильно бóльшим количеством ядер (лучшее моё вложение нескольких тысяч долларов в жизни!).

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

Недавно осознал, что VSCode можно запускать в режиме, когда код находится на удалённом сервере, VSCode подключается к нему через ssh, а для пользователя это выглядит так, как будто все локально. Всё плагины типа rust-analyzer или copilot запускаются удалённо, поэтому если условно бесплатно арендовать мощную виртуалку, то можно наслаждаться быстрым автодополнением на ноутбуке. Вот тут написано как это все настроить.

Reply Challenge 2024

Меня в комментариях просили заранее писать о соревнованиях, в которых я участвую, а не после того как они уже прошли. Исправляюсь. В этот четверг пройдет Reply Challenge. Вот тут подробности: https://challenges.reply.com/challenges/coding/how-it-works/

Соревнование по формату похоже на Google HashCode. Дается задача с неточным решением и открытыми тестами. Нужно за 4 часа их как можно лучше решить, используя любые средства. Соревнование командное, до 4 участников в каждой команде. За первое место дают 10k$ на команду.

Reply Challenge 2024 (результаты)

Вчера прошел Reply Challenge, о котором я писал в предыдущем посте. Мы его выиграли 🎉.

Но сам контест прошел довольно странно. Похожий по стилю 4-часовой Google HashCode обычно проходил так:
- В первый час читаешь условие, смотришь на особенности тестов.
- Во второй час пишешь какое-нибудь самое простое решение и код, который по решению считает его результат.
- В третий час пишешь более-менее умное решение.
- В четвертый час подбираешь константы/доделываешь решение.

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

Как обычно в таких соревнованиях общий скор считался как сумма скоров по отдельным тестам, поэтому какие-то тесты были более важными, а на какие-то можно было забить. В итоге мы набрали 0.5k+31k+401k+804k+3163k+7773k=12175k.

Если кто-то тоже решал контест, расскажите как у вас прошло и какие решения писали.

Соседние клетки

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

Так вот, представим, что у нас есть клеточное поле размером width*height и вы пишете bfs на нем. Есть текущая клетка (row, col). Как обойти всех непосещенных соседей (по стороне) этой клетки?

В совсем крайнем случае можно написать 4 похожих куска кода:

if row + 1 < height && !used[row + 1][col] {
  used[row + 1][col] = true;
  queue.push((row + 1, col));
}
if col + 1 < width && !used[row][col + 1] {
  ...
}

Но дублировать код не хочется. Если забыть на секундочку о типах, то можно написать примерно так:

for (dr, dc) in [(0, 1), (1, 0), (0, -1), (-1, 0)] {
  let nrow = row + dr;
  let ncol = col + dc;
  if 0 <= nrow && nrow < height && 0 <= ncol && ncol < width && !used[nrow][ncol] {
    used[nrow][ncol] = true;
    queue.push((nrow, ncol));
  }
}

Это бы нормально работало, если бы все переменные были типа i32. Но в Rust массивы индексируются только типом usize, который беззнаковый. Поэтому в каком-то месте придется приводить типы. Условно:

used[nrow as usize][ncol as usize]

И это выглядит некрасиво. Плюс придется из-за этого сделать width и height типа i32, а интуитивно кажется, что они должны быть usize, иначе придется много где добавлять лишние касты.

Так вот, как проще всего писать такой код на Rust?

P. S. Я еще видел такой вариант (overflowing_add и .0 это обычное сложение, которое разрешает переполнение):

for (dr, dc) in [(0, 1), (1, 0), (0, !0), (!0, 0)] {
  let nrow = row.overflowing_add(dr).0;
  let ncol = col.overflowing_add(dc).0;
  if nrow < height && ncol < width && !used[nrow][ncol] {
    used[nrow][ncol] = true;
    queue.push((nrow, ncol));
  }
}

Стоимость SMS

Читал недавно статью про то, что Telegram внедрил peer-to-peer верификацию пользователей. Когда вы входите в Telegram с нового устройства, Telegram присылает SMS с кодом вам на телефон, чтобы подтвердить, что это вы. В новой схеме SMS будет приходить не напрямую от Telegram, а просто от какого-то другого случайного пользователя (который дал согласие на использование своего телефона в качестве "прокси").

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

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

Как оценить сколько SMS надо отправить? Не очень понятно сколько SMS в год получает средний пользователь, но в качестве оценки снизу можно понять, что каждому новому пользователю нужно послать хотя бы одну SMS, чтобы верифицировать номер. В прошлом году Павел Дуров писал, что каждый день регистрируется 2.5 миллиона новых пользователей. Допустим сейчас это число 3 миллиона в день, тогда суммарно нужно будет потратить 3 * 365 * 0.1 = 110M$ в год.

Суммарно Telegram тратит сотни миллионов в год, а это обозначает, что на отправку SMS приходится значительная часть трат (десятки процентов). Неожиданно, правда?

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 ее немного криво отображает).

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. как вообще писать посты про решения задач, чтобы их было интересно читать людям, которые сами не решали эту задачу?

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 скор.