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. спасибо жене за подбор гармоничных цветов для картинки 🤍.
Lambdaman. Решение.
Как многие предложили в комментариях, можно попробовать сгенерировать псевдослучайную строку длины миллион, а потом подбирать
Как сгенерировать случайную строку? Можно использовать линейный конгруэнтный генератор. Звучит страшно, но по сути мы просто фиксируем две константы (например,
Дальше мы можем пытаться подобрать изначальный
С одной стороны это говорит о том, что метод достаточно интересный. А с другой о том, что подобрать сид, который посетит совсем все, скорее всего будет сложно.
Посмотрим на то, как именно устроен конкретный тест. Можно заметить, что все клетки, которые имеют такую же четность как и стартовая клетка, проходимые. Поэтому давайте генерировать строку, где каждая буква на четной позиции просто повторяет предыдущее действие, а буквы на нечетных позициях все еще случайные. Заметим, что если этот алгоритм обойдет все клетки той же четности, что и старт, то и все "промежуточные" клетки он тоже обойдет. Поэтому мы свели задачу к тому, чтобы за
Я нашел решение в таком формате где-то за 10 минут. Важно было перебирать не только разные стартовые
Как многие предложили в комментариях, можно попробовать сгенерировать псевдослучайную строку длины миллион, а потом подбирать
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" в случайном порядке. На практике такое решение можно найти быстрее чем за минуту. Видимо, идея в том, чтобы реже возвращаться обратно.Шахматы
В свободное от работы время я люблю смотреть стримы по шахматам. Сам я играть почти не умею, но посмотреть на игру глазами сильных гроссмейстеров, которые комментируют партии, очень интересно.
При подготовке к партиям игроки часто используют компьютер, потому что он довольно давно играет гораздо лучше человека. Анализируя позицию, игроки запоминают лучший ход в ней, смотрят на лучший ход за соперника, потом за себя, и так далее. Поскольку у всех есть доступ к такому оракулу с лучшим ходом, часто случаются ситуации когда партия очень быстро заканчивается в ничью, потому что все помнят оптимальные ходы.
Единственный способ как-то разнообразить игру на высоком уровне, это специально сделать неоптимальный ход, поставить себя в более плохое положение, но получить преимущество за счет того, что, возможно, соперник не смотрел этот вариант. При этом хочется с одной стороны не сделать свою позицию совсем проигрышной, а с другой поставить какие-то проблемы перед соперником.
Иногда оценка позиции компьютером может быть в пользу черных (потому что при оптимальной игре обоих соперников они получают преимущество), но при этом по-челевечески позицию может быть легче играть за белых (потому что им нужно делать простые ходы, а черным всегда искать единственные точные ходы). Именно такие позиции (где компьютерную оценку сложно доказать человеку за доской) шахматисты пытаются найти, готовясь к матчам. Считается, что находить подобные идеи (как в видео по ссылке выше) довольно трудно.
Меня давно не покидает идея, что можно искать такие идеи автоматически. Можно научиться предсказывать "человеческую" оценку позиции. Например, можно посмотреть насколько часто в позиции нужно будет находить единственные ходы. Или проанализировать миллионы партий, которые сыграны онлайн, и натренировать какую-нибудь нейронку. А потом поискать позиции, где такая оценка сильно отличается от компьютерной.
Интересно, топовые игроки уже давно имеют такие программы или это почему-то не работает?
P. S. на картинке у Яна осталось больше 10 минут времени, а у Алирезы меньше минуты (оба начинали с 10 минутами, и +2 секунды дают за каждый ход).
В свободное от работы время я люблю смотреть стримы по шахматам. Сам я играть почти не умею, но посмотреть на игру глазами сильных гроссмейстеров, которые комментируют партии, очень интересно.
При подготовке к партиям игроки часто используют компьютер, потому что он довольно давно играет гораздо лучше человека. Анализируя позицию, игроки запоминают лучший ход в ней, смотрят на лучший ход за соперника, потом за себя, и так далее. Поскольку у всех есть доступ к такому оракулу с лучшим ходом, часто случаются ситуации когда партия очень быстро заканчивается в ничью, потому что все помнят оптимальные ходы.
Единственный способ как-то разнообразить игру на высоком уровне, это специально сделать неоптимальный ход, поставить себя в более плохое положение, но получить преимущество за счет того, что, возможно, соперник не смотрел этот вариант. При этом хочется с одной стороны не сделать свою позицию совсем проигрышной, а с другой поставить какие-то проблемы перед соперником.
Иногда оценка позиции компьютером может быть в пользу черных (потому что при оптимальной игре обоих соперников они получают преимущество), но при этом по-челевечески позицию может быть легче играть за белых (потому что им нужно делать простые ходы, а черным всегда искать единственные точные ходы). Именно такие позиции (где компьютерную оценку сложно доказать человеку за доской) шахматисты пытаются найти, готовясь к матчам. Считается, что находить подобные идеи (как в видео по ссылке выше) довольно трудно.
Меня давно не покидает идея, что можно искать такие идеи автоматически. Можно научиться предсказывать "человеческую" оценку позиции. Например, можно посмотреть насколько часто в позиции нужно будет находить единственные ходы. Или проанализировать миллионы партий, которые сыграны онлайн, и натренировать какую-нибудь нейронку. А потом поискать позиции, где такая оценка сильно отличается от компьютерной.
Интересно, топовые игроки уже давно имеют такие программы или это почему-то не работает?
P. S. на картинке у Яна осталось больше 10 минут времени, а у Алирезы меньше минуты (оба начинали с 10 минутами, и +2 секунды дают за каждый ход).
Physics of Language Models
Я в своей жизни ML занимался довольно мало, но в последнее время решил все-таки по-лучше разобраться. Так что иногда (частота зависит от количества лайков 👍) буду постить краткие пересказы статей/докладов, которые мне показались интересными.
Мне очень не нравится идея смотреть на LLM, как на какой-то черный ящик, который каким-то магическим образом учится, и, нужно всего лишь увеличить количество параметров в нем, обучить на большем количестве данных, и тогда он станет гораздо умнее и вдруг научится решать всякие задачи.
В докладе Physics of language models авторы тренируют относительно маленькие модели (100М параметров) на синтетических данных, и смотрят, какие задачи LLM могут решать, а какие нет.
Например, оказывается что LLM даже теоретически не могут научиться отвечать на вопрос вида "Правда ли, что Байден родился в четном году?" при том, что они прекрасно знают в каком году он родился, и знают, какие числа четные. Оказывается, что дело в порядке токенов. Если бы ответ был в формате "Байден родился в году 1942, это четное число, ответ да", то все бы работало. Но если хочется получить ответ в формате "Да, потому что он родился в ...", то в момент написания первого токена у LLM еще не будет числа 1942 "в контексте" и она не сможет выбрать правильный ответ. И такая проблема есть у любых моделей вне зависимости от размера.
По аналогичным соображениям, если в датасете было написано только "X родился в городе Y", то модель никогда не сможет научиться правильно отвечать на обратный вопрос "кто родился в городе Y?" (потому что в "памяти" модели будет мапинг X->Y, но не в обратную сторону).
Еще из прикольного в докладе показывают, что можно обучить текстовую модель делать топологическую сортировку графа. При этом можно проследить, что в "состоянии" модели во время инференса действительно будет храниться множество посещенных вершин и тех вершин, которые можно посетить на следующем шагу.
Я в своей жизни ML занимался довольно мало, но в последнее время решил все-таки по-лучше разобраться. Так что иногда (частота зависит от количества лайков 👍) буду постить краткие пересказы статей/докладов, которые мне показались интересными.
Мне очень не нравится идея смотреть на LLM, как на какой-то черный ящик, который каким-то магическим образом учится, и, нужно всего лишь увеличить количество параметров в нем, обучить на большем количестве данных, и тогда он станет гораздо умнее и вдруг научится решать всякие задачи.
В докладе Physics of language models авторы тренируют относительно маленькие модели (100М параметров) на синтетических данных, и смотрят, какие задачи LLM могут решать, а какие нет.
Например, оказывается что LLM даже теоретически не могут научиться отвечать на вопрос вида "Правда ли, что Байден родился в четном году?" при том, что они прекрасно знают в каком году он родился, и знают, какие числа четные. Оказывается, что дело в порядке токенов. Если бы ответ был в формате "Байден родился в году 1942, это четное число, ответ да", то все бы работало. Но если хочется получить ответ в формате "Да, потому что он родился в ...", то в момент написания первого токена у LLM еще не будет числа 1942 "в контексте" и она не сможет выбрать правильный ответ. И такая проблема есть у любых моделей вне зависимости от размера.
По аналогичным соображениям, если в датасете было написано только "X родился в городе Y", то модель никогда не сможет научиться правильно отвечать на обратный вопрос "кто родился в городе Y?" (потому что в "памяти" модели будет мапинг X->Y, но не в обратную сторону).
Еще из прикольного в докладе показывают, что можно обучить текстовую модель делать топологическую сортировку графа. При этом можно проследить, что в "состоянии" модели во время инференса действительно будет храниться множество посещенных вершин и тех вершин, которые можно посетить на следующем шагу.
YouTube
ICML 2024 Tutorial: Physics of Language Models
Project page (with further readings): https://physics.allen-zhu.com/
Abstract: We divide "intelligence" into multiple dimensions (like language structures, knowledge, reasoning, etc.). For each dimension, we create synthetic data for LLM pretraining to understand…
Abstract: We divide "intelligence" into multiple dimensions (like language structures, knowledge, reasoning, etc.). For each dimension, we create synthetic data for LLM pretraining to understand…