Боря дорешивает

Grand Prix of EPS. H.

https://contest.ucup.ac/contest/4207/problem/21380

Если убрать все детали, то задача следующая. Есть n вершин, каждая характеризуется числами (x_i, A_i, B_i). Ребро между вершинами i и j стоит A_i * x_j + B_i. Формула получилась немного не симметричная, но на самом деле (A_i, B_i) такие, что расстояние в одну и другую сторону получаются одинаковые. Нужно на таком графе построить максимальное остовное дерево.

Если вы внимательно читали предыдущие посты, то знаете, что когда нам дают какой-то неявный полный граф, в котором нужно находить MST, то нам нужен алгоритм Борувки. Тогда за логарифм итераций "для каждой вершины найти самую далекую не из текущей компоненты" мы сможем решить задачу.

Задача несколько усложняется тем, что TL=1s, а сумма n может быть 5*10^5. Поэтому было бы неплохо делать каждую итерацию за линию, тогда суммарная сложность будет O(n log n). Оказывается так можно сделать!

Как решать задачу, если нет условия на "не из текущей компоненты"? Тогда нужно построить верхнюю огибающую всех прямых Ax+B. Отсортируем их по A, будем хранить стек, и добавлять их по одной. Потом посортируем все запросы по x и указателем будем искать нужную прямую. Все сортировки можно сделать заранее.

Но в данной задаче нам нужно находить прямые не текущего цвета. Как обычно, будем хранить два максимума. Что это значит для выпуклой оболочки? Посмотроим оболочку не обращая внимание на цвет. Теперь для каждого наибольшего подотрезка оболочки одинакого цвета выкинем его и построим "вторую максимальную оболочку" из линий не этого цвета, которые лежат на том же интервале. Можно показать, что суммарный размер "вторых оболочек" будет O(n).

В итоге решение получается такое и проходит за ~300мс. А были времена, когда такое можно было сдавать не в дорешку...

47/100.

Чтобы в предыдущей задаче посчитать ответ быстрее чем за квадрат надо сделать два многочлена. Для каждой позиции i, если она равна нулю, то записать first[i] = 1, а иначе second[n - i] = 1. Если их перемножить, то в res[n - len] + res[n + len] будет записано сколько пар (0, 1) на расстноянии ровно len.

Правда работает это примерно столько же по времени сколько и битсет :)

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

Оказывается n-е число Каталана можно считать не только как C(2 * n, n) / (n + 1), но и как C(2 * n, n) - C(2 * n, n + 1). Тогда не нужно делить, получается чуть быстрее!

Расскажите в комментариях какое-нибудь понятное объяснение почему "количество скобочных последовательностей длины 2n" считается именно таким образом? Есть какое-то понятное отображение между последовательностями и выборобом каких-то позиций?

46.5/100

https://codeforces.com/contest/2268/problem/E

После скучной части про комбинаторику задача сводится к тому, что нужно 20 раз решить такую подзадачу. Есть последовательность a из нулей и единиц длиной 2*10^5. Нужно для каждого shift посчитать сколько существует таких i, что a[i] != a[i + shift].

Наверняка это сводится к перемножению каких-то многочленов. Но это же скучно?

На самом деле для каждого shift нас просят просто взять битсет, сдвинуть его, проксорить, и посчитать количество единиц. Нам,конечно, нужно сделать суммарно 20 * (2*10^5)^2 / 2 = 4*10^11 операций. Но если поделить это число на 64, то получается всего 6 миллиардов, звучит уже не так и страшно. https://codeforces.com/contest/2268/submission/392765224

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

Grand Prix of EPS. A.

https://contest.ucup.ac/contest/4207/problem/20715

Не будем вдаваться в детали задачи, но решение (авторское?), которое я решил написать, работает за 8*n*k*4+q*k, при том что n=10^5, q=3*10^5, k=800, т.е. делает примерно 3 миллиарда операций (и выделяет примерно столько же памяти). TL=4s и если это реально авторское, то мое уважение.

Так вот, написал я код, отправил, получил TimeLimit. https://pastebin.com/2VqTiGtU. Я специально старался не особо оптимизировать на этом этапе (например, выделял много памяти), зато хотелось написать без багов.

Локально код работал где-то 7с, что в целом давало надежду. Я в решении выделял трехмерный массив и часто делал операции в цикле типа:

for j in 0..k {
  dp[i + 1][1][j + 1] = dp[i + 1][1][j + 1].max(dp[i][0][j] + cur_val);
}

В идеальном мире компилятор такое должен очень хорошо оптимизировать со всякими avx, но ему тут явно не до этого. Например, он скорее всего вообще не понимает, что dp[i + 1] и dp[i] это разные участки памяти, поэтому можно все векторизовать. Еще, скорее всего он каждый раз делает "переход по ссылке", чтобы понять где находится dp[i + 1]. Поэтому я решил вынести dp[i + 1] в отдельный новый двухмерный массив, заполнить его, а потом скопировать в старых трехмерный. Локально это ускорило на пару секунд, но я все еще получил TimeLimit. https://pastebin.com/Rm4anpsa

В этой задаче мы в каком-то смысле делаем первый уровень вложенности алгоритма "разделяй и властвуй". Выбираем опорный элемент, считаем какую-то динамику слева, какую-то справа, а потом для каждого запроса, который пересекает центр, объединяем значения двух динамик. Причем центр выбирается так, что левая часть это 15% позиций, а правая 85%. Можно не выделять трехмерный массив для правой части, а хранить только два последних слоя, и сразу же отвечать на все запросы, которые заканчиваются в текущем слое. https://pastebin.com/tVF8cdDn. И тут я наконец-то получил WA вместо TL. Правда, работала программа на этом тесте 3897ms, так что даже если исправить WA, то не факт, что решение работает достаточно быстро.

Тут я понял, что я не до конца последовал своему изначальному плану "писать без оптимизаций, но без багов", потому что как раз таки добавил какую-то багу из-за неправильной оптимизации. После ее исправления, я получил AC за 3571ms! 🎉 https://pastebin.com/t31jUaTU

Мне стало интересно, насколько сильнее можно соптимизировать код. Я запустил свой код, рядом запустил perf top -p <pid>, было видно, что много времени тратится в циклах типа:

for left_cnt in 0..=k {
  best = best.max(dp_left[left_len][0][left_cnt] + dp[0][k - left_cnt]);
}

Тут опять же хочется, чтобы компилятор мог их лучше оптимизировать, поэтому сделал отдельную функцию (это часто помогает компилятору понять, что данные независимы и не делать много лишних проверок на каждом шагу):

fn fast_conv(a: &[i32], b: &[i32]) -> i32 {
  let mut res = i32::MIN;
  let n = a.len();
  assert_eq!(n, b.len());
  for i in 0..n {
    res = res.max(a[i] + b[n - 1 - i]);
  }
  res
}

Также соптизировал какие-то простые циклы, которые просто копируют данные через .copy_from_slice(...). https://pastebin.com/8RPHsZ3S. 1685ms.

Если вы дочитали до этого места, то научите меня как эффективнее всего оптимизировать дальше. Как понять, какой код на самом деле тормозит? Стандартные perf record / perf report показывают что-то вроде "100% cpu тратится в функции solve, 14% вот в этих местах, а еще 86% непонятно где". Как понять где конкретно тратится время и на что?

В общем, мне стало лень оптимизировать дальше самому, и я попросил codex научить меня это делать и подсказать, что и где еще не эффективно. По дороге я еще ради прикола завайбкодил что-то вроде локального godbolt, но так и не понял, почему он чем-то лучше чем perf report.

В итоге сделал какие-то такие оптимизации:
- Заалоцировать память один раз вместо выделения в цикле (не особо помогло?)
- Использовать 2x меньше памяти (помогло). Видимо стало лучше в какие-то кеши помогать.
- Обернуть какие-то функции в #[target_feature(enable = "avx2")]. Тоже помогло на 100-200мс.
- Убрать ненужные copy_from_slice, где можно сразу посчитать новое правильное значение динамики.
- Написать отдельную функцию, которая делает ndp[j] = dp0[j].max(dp1[j] + cur_val) и вызвать ее с правильными slice. Помогло довольно сильно!
- Функция update_pref_max, которая по сути делала a[i] = a[i].max(a[i - 1]), всегда вызывалась на массиве, который вначале возрастал, а потом убывал. Поэтому можно было найти позицию максимума и сделать a[max_pos..].fill(max_value).
- Когда сохранял запросы, которые заканчиваются в конкретной позиции, вместо того, чтобы сохранить только индекс, сохранил весь запрос, чтобы не нужно было каждый раз доставать информацию из вектора. (еще 100мс!).
- Убрать update_pref_max вообще и перейти от динамики "взял k отрезков" к "взял не более k отрезков".
- Сохранять запросы не в Vec<Vec<...>>, а просто в отсортированный Vec<...> (на сервере столько же работает, локально быстрее).

Некоторые оптимизации помогали локально, но не особо помогали на сервере.

В итоге последняя версия кода выглядит вот так https://pastebin.com/GE2YyqrA, и получает AC за 367ms. Так что можно считать, что авторы выставили TimeLimit с запасом :)

46/100.

https://contest.ucup.ac/contest/4126/problem/20248

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

А еще представляете, в те годы на AtCoder в большинстве задач НЕ просили считать что-то по модулю, а были обычные нормальные задачи! И рейтинг у меня там был примерно на 1000 больше чем сейчас.. Были же времена!

Так вот, я тогда решил, что надо практиковаться в задачах, где что-то просят посчитать по модулю. Подумал, что если решить 100 задач, то явно научусь это делать гораздо лучше. Как можно понять из заголовка поста, до ста пока далеко...

В сегодняшней задаче просят посчитать какую-то странную величину. Берут лист в дереве, смотрят на путь до корня, и считают 1/(произведение степеней вершин на этом пути). Спрашивается чему равна сумма таких величин по всем листьям. На контесте мы подумали, что раз спрашивают что-то такое странное, то наверняка эта формула во что-то красиво сворачивается, но так и не придумали во что. Но если нарисовать пару примеров, то становится понятно, что сворачивается оно в число один.

Подписывайтесь на канал Um_nik https://t.me/umnik_video! Он там тоже задачи разбирает (и явно тратит больше времени на создание видео чем я на свои посты).

Узнал вот, что в задаче G с предыдущего кубка надо было просто пошафлить инпут пока не получишь правильный ответ.

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

GP of Nizhny Novgorod. C.

https://contest.ucup.ac/contest/4126/problem/20250

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

Впервые в жизни пригодился алгоритм Борувки! Он работает следующем образом. Вначале все вершины поместим в отдельные компоненты. Пока компонент больше одной, для каждой найдем минимальное ребро в другую, а потом добавим все такие ребра. Идея в том, что всего таких итераций будет логарифм. Поэтому, если для каждой вершины уметь быстро находить ближайшую не из текущей компоненты, то итоговая сложность алгоритма получится O(n * logn * быстро).

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

DragonByte Final 2026. I.

https://www.wincentdragonbyte.com/archive/finals2026/I/statement

Прикольная оптимизационная задача. Вам даны две колоды карт с различными числами от 1 до 1000. Вы играете в пьяницу. Каждый раз, когда кладете очередные две карты вниз колоды, можно выбрать в каком порядке их положить. Нужно выбирать так, чтобы игра закончилась как можно быстрее. Дано 1000 тестов, и скор зависит от максимальной длины ответа. Если все ответы меньше 7500 действий — полный балл. Если есть хотя бы один ответ длиннее 175000, то 0 баллов.

Во время контеста большинство участников, которые отправили эту задачу, получили скор в районе 40-50 баллов. Максимальный скор был 60.83. Расскажу как можно получить 70 баллов стандартными средствами вообще не думая про суть задачи.

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

Давайте в 99% случаев класть большую карту, а в 1% меньшую. Такое решение проходит какие-то тесты, но не проходит другие. Давайте для каждого теста будем перебирать randseed пока не найдем такой, который решает тест за 30000 операций. Такое решение я написал на контесте и получил ~55 баллов.

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

Воспользуемся стандартным трюком из оптимизационных контестов. Запишем последовательность наших действий как строку из 0 и 1. Поменяем случайную позицию. Если это привело к лучшему решению, то сохраним, иначе отменим. Будем так делать пока не придем в ситуацию, где никакое изменение не помогает. Если действий стало меньше 19000 — отлично, иначе попробуем с другого randseed. Немного подождем и у нас 70 баллов!

DragonByte Final 2026. P3.

https://www.wincentdragonbyte.com/archive/finals2026/P/statement

Участвовал в контесте Wincent Dragonbyte. Особенность формата заключается в том, что вам дают инпуты для задач, вы запускаете свое решение локально, и отправляете готовые ответы на проверку. В задачах есть подзадачи, где можно написать более медленное решение и получить частичные баллы.

Так, например, чтобы решить подзадачу P2 во время контеста я написал решение с асимптотикой O(n * b^2). В подзадаче P3 ограничения были:
- 100 отдельных тестов
- n <= 10^5
- b <= 1000
- сумма n по всем тестам не больше 10^6

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

Еще в Rust можно довольно легко распараллелить по доступным ядрам запуск на всех тестах. Для этого нужно добавить rayon = "1.12" в [dependencies] в Cargo.toml. А в самой задаче считать инпут в вектор, сделать на нем into_par_iter().map(|input| solve(input)).collect() и все!

В итоге такое решение работает на всех тестам суммарно где-то 15 минут на ноутбуке.

GP of Nizhny Novgorod. H.

https://contest.ucup.ac/contest/4126/problem/20255

Не будем углубляться в детали задачи, но там, как и в любой задаче на вычгеом, нужно быть очень аккуратным с точностью вычислений. Существует несколько "школ" того, как правильно писать задачи на вычгеом. Некоторые люди спокойно создают структуру Point с double x, y, добавляют в случайные места программы EPS при различных вычислениях и вообще ничего не бояться по жизни. Я же очень сильно боюсь так делать и стараюсь писать все вычисления в целых числах. Иначе, при получении WA, очень сложно понять это бага в коде или нужно просто поменять EPS.

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

Существует много разных способов пересечь две прямых. Расскажу про тот, которым было удобно воспользоваться в данной задаче. Пусть одна прямая задана координатами двух точек A и B лежащих на ней, а другая точками C и D. Нужно найти некоторую точку Q, которая лежит на их пересечении. Запишем позицию Q в виде A + u * (B - A). Удобно, что получив значение u, можно заодно понять где конкретно она лежит по отношению к A и B. Например, если 0 <= u <= 1, то она лежит на отрезке AB. Если u > 1, то на продолжении луча AB.

Как найти u? Мне кажется удобно думать об этом с геометрической точки зрения. Посмтрим на треугольники ADC и BCD. Их площади относятся как u к 1 - u. Площадь треугольника ADC это просто векторное произведение AD * AC (с точностью до 1/2). Отсюда получаем, что u = ADC / (BCD + ADC).

Прикольный факт, что о площадях надо думать как о чем-то, у чего есть знак (и считается по формуле векторного произведения). Тогда эта формула для u продолжает работать даже для u < 0 и u > 1, когда какие-то из площадей отрицательные. А если BCD + ADC = 0, то это обозначает, что AB и CD параллельны.

В таком формате еще очень удобно думать про то, какой тип данных нужен для хранения всего этого. Если координаты были порядка C = 10^9, то векторное произведение порядка C^2, а u это дробь, где числитель и знаменатель порядка C^2. Если мы захотим такие дроби сравнивать, то нужен будет тип, который вмещает C^4 (int128).

Боря дорешивает pinned «Всем привет! С развитием AI приходится все реже писать код руками, а хочется все еще поддерживать этот скилл. Поэтому решил, что надо решать побольше олимпиадных задач. А чтобы было побольше мотивации это делать, решил, что буду писать сюда про какие-то инетерсные…»

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

По сравнению с моим основным каналом https://t.me/bminaiev_blog постараюсь писать сюда чаще, но качество постов будет ниже.

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

Channel photo updated

Channel created