Osijek Competitive Programming Camp, Winter 2024
С 17 по 25 февраля пройдет Osijek Competitive Programming Camp, Winter 2024. В один из дней будет контест, который подготовил я. Потратил кучу времени, но надеюсь, что задачи получились необычными и интересными (и сложными). Так что студентам рекомендую поучаствовать в этих сборах!
Если вы не собираетесь участвовать в сборах, знакомы со мной лично и хотите помочь, то можете принять участие в прорешивании контеста. Напишите в личку, если вам это интересно.
Через неопределенное время после конца сборов (скорее всего во второй половине 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, но скор почему-то в два раза лучше 😐.
Вчера закончилось соревнование на Kaggle, в котором нужно было за наименьшее количество шагов собрать различные вариации кубика Рубика. Скор считался как сумма длин решений по всем тестам, поэтому важно было научиться хорошо решать самые большие кубики (33х33х33), а маленькие играли второстепенную роль.
Проблема сборки кубика Рубика довольно хорошо изучена и есть много готовых алгоритмов. Но большинство из них работают только для 3х3х3. Я нашел только два готовых солвера, которые умеют решать NxNxN. Один из них был совсем не оптимальным. А второй оптимизировал количество шагов в другой метрике. Он был сделан для роботов, которые автоматически собирают кубик, поэтому считает, что можно повернуть несколько внешних слоев за один шаг.
На протяжении всего контеста я думал, что путь к успеху это переписать второй солвер на правильную метрику. Но каждый раз, когда я собирался это сделать, я смотрел на десятки тысяч строк кода этого солвера, и понимал, что шансы на успех довольно малы. Я потратил где-то неделю на то, чтобы написать солвер для 3х3х3 и начал писать 4х4х4, но это выглядело слишком сложно.
В итоге я решил реализовать хоть какое-то решение, которое основано на той же идее, что и первый неоптимальный солвер. Все клетки можно разбить на множества по 24 штуки таким образом, что при любом движении клетка остается только в своем множестве. Существуют последовательности из 8 действий, которые переставляют по циклу 3 клетки из одного множества и никак не трогают остальные. Поэтому можно решать каждое множество независимо.
Потом я еще улучшил эту идею за счет того, что можно объединить две (и даже больше) такие последовательности и переиспользовать часть ходов. Но меня все еще не покидало ощущение, что делать 8 действий, чтобы передвинуть 3 клетки, это очень дорого.
В итоге соревнование закончилось, читаю решение участников с первого места, а у них все те же самые идеи про циклы длины 3, но скор почему-то в два раза лучше 😐.
Stress testing
Допустим вы написали решение к какой-то олимпиадной задаче, отправили его на проверку, получили "wrong answer", прочитали код и не нашли баг. Что делать дальше?
Хороший следующий шаг — написать стресс-тест. Нужно написать максимально простое решение задачи, но которое работает только на маленьких тестах, и генератор маленьких тестов. А потом в цикле генерировать тест, запускать два решения, сранивать ответы и остановиться, когда они не совпадут. Как лучше (по скромному мнению авторого этого поста, которое может не совпадать с вашим) всего все это запускать?
Тут довольно хорошо описан типичный "плохой" и "хороший" способы. Постараюсь объяснить почему на самом деле все наоборот. В посте предлагается делать три отдельных программы — генератор, решение и медленное решение. И еще дополнительно написать скрипт, который все запускает.
Самая главная проблема такого подхода — оверхед от запуска процессов. Скорее всего вы сможете запустить тысячу различных тестов за секунду, но вряд ли сможете сотни тысяч. Часто довольно просто найти большой тест, на котором решение не работает, но чтобы было удобнее дебажить, хорошо бы найти минимальный. А для этого как раз хочется уметь много раз запускать решение.
Типичный способ решить эту проблему — генерировать сразу несколько тестов в одном файле, но тогда нужно тратить время, чтобы понять, какой именно из тестов не работает.
Я обычно пишу все четыре части в одном месте, код получается примерно такой:
В данном случае
После того как плохой тест найден, можно попробовать уменьшить
Допустим решение упало на 100500-м тесте и мы хотим его подебажить. Можно просто заменить строку
Сразу отвечу на потенциальные вопросы:
1. Обычно решение написано таким образом, что оно читает тест из stdin, а тут тест передается как уже готовая структура данных. Придется переписать эту часть
Полезно сразу писать решение в формате, когда чтение инпута и решение это отдельные части, тогда такой проблемы нет.
2. Решение может использовать какие-то глобальные переменные, тогда так писать стресс нельзя.
Не используйте глобальные переменные.
Допустим вы написали решение к какой-то олимпиадной задаче, отправили его на проверку, получили "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 секунд. Как можно так работать я не понял, и попытался это пофиксить.
Автодополнение работало долго, потому что оно вызывало
Самый эффективный способ ускорить
Ещё в три раза получилось ускорить более простым способом — вместо ноутбука я купил себе стационарный компьютер с сильно бóльшим количеством ядер (лучшее моё вложение нескольких тысяч долларов в жизни!).
К хорошему быстро привыкаешь, поэтому каждый раз, когда я куда-то ездил и приходилось писать код на ноутбуке, было очень не комфортно.
Недавно осознал, что VSCode можно запускать в режиме, когда код находится на удалённом сервере, VSCode подключается к нему через ssh, а для пользователя это выглядит так, как будто все локально. Всё плагины типа rust-analyzer или copilot запускаются удалённо, поэтому если условно бесплатно арендовать мощную виртуалку, то можно наслаждаться быстрым автодополнением на ноутбуке. Вот тут написано как это все настроить.
Когда я только присоединился к 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. Вот тут подробности: 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.
Если кто-то тоже решал контест, расскажите как у вас прошло и какие решения писали.
Вчера прошел Reply Challenge, о котором я писал в предыдущем посте. Мы его выиграли 🎉.
Но сам контест прошел довольно странно. Похожий по стилю 4-часовой Google HashCode обычно проходил так:
- В первый час читаешь условие, смотришь на особенности тестов.
- Во второй час пишешь какое-нибудь самое простое решение и код, который по решению считает его результат.
- В третий час пишешь более-менее умное решение.
- В четвертый час подбираешь константы/доделываешь решение.
В этот раз самое простое решение я написал к концу третьего часа, а времени на чекер и что-то умное вообще не осталось. Если что-то плохо работало, то вместо поиска бага проще было просто подобрать другой randseed, с которым решение работает.
Как обычно в таких соревнованиях общий скор считался как сумма скоров по отдельным тестам, поэтому какие-то тесты были более важными, а на какие-то можно было забить. В итоге мы набрали 0.5k+31k+401k+804k+3163k+7773k=12175k.
Если кто-то тоже решал контест, расскажите как у вас прошло и какие решения писали.
Соседние клетки
Я редко пишу что-то в этот канал, потому что на интересные посты обычно нужно потратить много времени. Но само его наличие мне очень нравится! Например, часто в комментарии приходят умные люди и рассказывают, как на самом деле что-то надо было сделать :)
Так вот, представим, что у нас есть клеточное поле размером
В совсем крайнем случае можно написать 4 похожих куска кода:
Но дублировать код не хочется. Если забыть на секундочку о типах, то можно написать примерно так:
Это бы нормально работало, если бы все переменные были типа
И это выглядит некрасиво. Плюс придется из-за этого сделать
Так вот, как проще всего писать такой код на Rust?
P. S. Я еще видел такой вариант (overflowing_add и .0 это обычное сложение, которое разрешает переполнение):
Я редко пишу что-то в этот канал, потому что на интересные посты обычно нужно потратить много времени. Но само его наличие мне очень нравится! Например, часто в комментарии приходят умные люди и рассказывают, как на самом деле что-то надо было сделать :)
Так вот, представим, что у нас есть клеточное поле размером
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 приходится значительная часть трат (десятки процентов). Неожиданно, правда?
Читал недавно статью про то, что 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 ее немного криво отображает).
Написал тут 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. как вообще писать посты про решения задач, чтобы их было интересно читать людям, которые сами не решали эту задачу?
В этом посте будет описание решения, которое я написал на контесте. А в следующем расскажу каких идей мне не хватило, чтобы занять первое место (как еще заставить себя дорешать задачу, если не публично пообещать?).
Можно идти сверху вниз слева направо и в клетку (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 скор.
В эвристических контестах есть два алгоритма, которые чаще всего используются. 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 скор.
ICPC World Finals Luxor
Приехал в Египет потусить на финале ICPC (самая масштабная олимпиада по программированию среди студентов). Для меня это возможность не только вспомнить молодость (жесть, уже 10 лет прошло с моего первого финала), но и в одном месте увидеть кучу людей из олимпиадной тусовки, которых давно не видел. Очень круто!
Из-за ковида расписание финалов ICPC сдвинулось, поэтому сейчас проходит одновременно два — за 2022 и 2023 год. Само соревнование длится 5 часов и начнется завтра в 12 дня по местному времени.
На YouTube будет трансляция с ведущими и гостями, должно быть интересно.
Еще будет трансляция, где Гена, Петя и Кевин (все очень крутые олимпиадные программисты) будут решать те же задачи, что и участники, но не официально. Тоже рекомендую посмотреть!
Полезные ссылки:
- Таблицы результатов.
- Список участников с рейтингами на КФ: 2022 и 2023.
Приехал в Египет потусить на финале ICPC (самая масштабная олимпиада по программированию среди студентов). Для меня это возможность не только вспомнить молодость (жесть, уже 10 лет прошло с моего первого финала), но и в одном месте увидеть кучу людей из олимпиадной тусовки, которых давно не видел. Очень круто!
Из-за ковида расписание финалов ICPC сдвинулось, поэтому сейчас проходит одновременно два — за 2022 и 2023 год. Само соревнование длится 5 часов и начнется завтра в 12 дня по местному времени.
На YouTube будет трансляция с ведущими и гостями, должно быть интересно.
Еще будет трансляция, где Гена, Петя и Кевин (все очень крутые олимпиадные программисты) будут решать те же задачи, что и участники, но не официально. Тоже рекомендую посмотреть!
Полезные ссылки:
- Таблицы результатов.
- Список участников с рейтингами на КФ: 2022 и 2023.
Please open Telegram to view this post
VIEW IN TELEGRAM
CF 942D
Решал тут CodeForces раунд и очень понравилось решение одной из задач. На контесте я перемудрил, попытался придумать слишком сложное решение и в итоге задачу не сдал. Но на самом деле все гораздо проще, и в следующем посте расскажу как надо было решать. А вы пока можете в комментариях предложить свои решения.
Если выкинуть неинтересные детали, то условие такое. Дан массив
Решал тут 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. Первая идея довольно стандартная, но все равно красивая. Пусть для любой пары чисел
2. Как проверять, можно ли получить
3. Если вспомнить, что ребро
4. Как просто выбрать
Доказательство того, что этот код делает ровно то, что нужно, оставлю в качестве упражнения для любознательных читателей.
Условие задачи.
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 и он смог найти в них баг!
Сегодня хотел узнать, что обозначает
Я долго не мог понять, почему ChatGPT решил мне соврать на таком простом вопросе. Разгадка нашлась, когда я задал какой-то совсем не связанный вопрос и опять получил ответ
Чтобы это была не просто смешная история, то пусть тут будет какая-то мораль. Используйте тип
Последнее время стал довольно много пользоваться 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 июня. Через сутки после начала мы усложним задачу и добавим новых тестов. Так что если в первый день вам покажется слишком просто, приходите на следующий день :)
Мы потратили много сил, чтобы сделать хороший контест, так что обязательно участвуйте (и заходите в дискорд уже сейчас)!
Вместе с Ромой и Геной мы решили провести командный оптимизационный контест. Для участия регистрируйтесь на сайте 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 начнется уже через 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!
На прошлых выходных провели контест, фух, можно теперь наконец-то выдохнуть и расслабиться! Посмотрел историю коммитов в репозитории — мы его готовили (в очень ленивом режиме) где-то полгода.
На удивление все прошло гораздо лучше чем я ожидал. Задача людям понравилась, система работала стабильно, ничего ни разу не упало. Видимо долгие годы написания высоконагруженных баз данных не прошли зря :)
На время контеста я арендовал мощный сервер (и заплатил где-то 200$ за него), но в итоге он никогда не был нагружен больше чем на несколько процентов (несмотря на то, что у нас было 200 команд, которые отправили 175000 посылок).
А еще у нас в контесте участвовали очень топовые ребята. Например, Psyho, wata и nika!
В общем надеюсь всем понравилось. Stay tuned for Code Weekend #2!
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
В эту пятницу начинается 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
Lambdaman
Расскажу про одну из задач с прошедшего ICFPC. Вам дан какой-то фиксированный лабиринт (в данном тесте размера 101х101) и начальное положение робота.
Нужно написать программу на выдуманном функциональном языке программирования, которая выведит строку из миллиона букв LRUD (left, right, up, down). После этого робот пытается по порядку выполнить каждое действие. Если в клетке, в которую хочет пойти робот, находится стена, то он просто стоит на месте. Тест считается пройденным, если в итоге робот посетил каждую клетку.
Сложность в том, что ваше решение оценивается по тому, насколько короткую программу вы написали (а не по тому, насколько долго робот ходил). Например, можно заранее предподсчитать правильный путь, и написать программу
В самом языке программирования ничего особенного нет, там можно делать какие-то простые операции с числами и строками, писать циклы (через рекурсию).
Интересно, что лучшее решение участников для этого теста умещалось где-то в 150 символов. Отгадайте как?
P. S. спасибо жене за подбор гармоничных цветов для картинки 🤍.
Расскажу про одну из задач с прошедшего ICFPC. Вам дан какой-то фиксированный лабиринт (в данном тесте размера 101х101) и начальное положение робота.
Нужно написать программу на выдуманном функциональном языке программирования, которая выведит строку из миллиона букв LRUD (left, right, up, down). После этого робот пытается по порядку выполнить каждое действие. Если в клетке, в которую хочет пойти робот, находится стена, то он просто стоит на месте. Тест считается пройденным, если в итоге робот посетил каждую клетку.
Сложность в том, что ваше решение оценивается по тому, насколько короткую программу вы написали (а не по тому, насколько долго робот ходил). Например, можно заранее предподсчитать правильный путь, и написать программу
println "LRLLRLU...", но она получит мало баллов.В самом языке программирования ничего особенного нет, там можно делать какие-то простые операции с числами и строками, писать циклы (через рекурсию).
Интересно, что лучшее решение участников для этого теста умещалось где-то в 150 символов. Отгадайте как?
P. S. спасибо жене за подбор гармоничных цветов для картинки 🤍.