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

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