Деревья и Rust
Oct. 30th, 2022 12:40 pm![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
amaraoЯ тут решаю одну hard problem на leetcode (в leetcod'овском смысле 'hard', не NP-hard). Я думаю, что я её уже решил оптимально (спустя ~10 исписанных бумажек), но я не знаю как её запрограммировать на Rust. Списки и деревья - моя слабость в Rust, потому что "всё понимает, а сказать не может".
Итак, задача: https://leetcode.com/problems/maximum-segment-sum-after-removals/
Дан массив положительных чисел и массив со списком позиций для удаления чисел. Нужно заменять в первом массиве (чисел) позицию из второго списка нулём. После этого нужно смотреть на массив чисел и отвечать какая сумма сегмента там самая большая. Сегмент - непрерывная последовательность чисел без нулей. Эти суммы надо записать в результат (для каждого удаления - максимальный размер сегмента в после данного удаления).
Т.е. после каждого удаления старый сегмент может оказаться поделен на два, и возможно что какой-то другой сегмент теперь больший.
Всего для массива в N чисел будет N удалений.
Решение в лоб тривиальное - заменяем элемент в массиве, считаем какой сегмент максимальный. Сложность n², потому что у нас надо N раз посчитать максимальный сегмент среди N чисел.
Дальше спойлер
Я быстро прошёл этапы локальной оптимизации. Наверное, самый интересный был с running sum, когда нулевой элемент обнулял current running sum, но сохранял max running sum и при сканировании сравнивалось значение нуля и если оно было меньше, чем у последнего элемента, мы прыгали прямо к нему. (т.к. в прошлый прогон у нас уже в последнем элементе max был). Это всё ерунда под которую есть контр-примеры с n² сложностью, и я не уверен, что у меня бы даже и получилось что-то сэкономить (обновлять-то running max всё равно надо у всех ненулевых элементов и у некоторых нулевых..., короче, skip).
Следующая идея была хранить числа в дереве/в рекурсии стека и понимать случаи "слева были нули/не было/примыкающий ноль" и т.д. Я взорвался в дереве состояний и условий.
Наконец, решение, которое я думаю, что работает, простое:
Segments = Zero(Left: Segments, Right: Segments) ∪ Range[x..y]
Дерево нулей, в котором либо полный отрезок без нулей (точнее, значения его начала/конца), либо пара значений (лево/право от нуля), где каждое значение ссылка на ноду (дерева), то есть на структуру самого себя. Плюс кешированный max для каждой половинки, плюс None, если ноль находится с "краю".
При каждом удалении мы обходим дерево, находим сегмент, в котором находится ноль, заменяем этот сегмент на новый Zero и 0-1-2 сегмента, пересчитываем суммы для этих двух сегментов, вычисляем максимум, пересчитываем максимум у родителя (не заходя во второго потомка) и так до самого верха, верх - результат для записи в output.
Я 100% уверен, что оно работает, сложность ~o(n*log(n)) (будет вставлено n нулей, каждый ноль log (n) обходов дерева. У меня трещит голова посчитать сложность посчёта максимума для массивов, но понятно, что она резко снижается после каждого нуля. Несколько "плохих" случаев легко покрываются локальными оптимизациями (ноль с краю - мы не пересчитываем длину отрезка, а просто вычитаем из него, ноль где-то посредине - считаем до середины в меньшем интервале и принимаем решение на середине о том, чему равен остаток (мы знаем общую сумму), но понятно, что в среднем это меньше n, и оно либо стремительно сокращается с каждой итерацией (если ноль в середине), либо легко высчитывается за малое число операций, если ноль с краю. В любом случае, у нас на каждом шагу отрезается m чисел из рассмотрения... Вероятно, там есть мерзкий пример с постоянным пересчётом по большому интервалу, но мне трудно додумать туда.
В любом случае, дерево тут - путь куда надо.
Но! Деревья медленные. Надо BTree. И я совершенно не понимаю как мне использовать BTreeMap в Rust для этой задачи. Я не понимаю, что является value. Более того, я даже не понимаю, что является key, потому что в моём наивном описании дерева нода - это или ноль (его позиция и информация об нодах слева/справа), либо интервал (leaf).
Получается, мне нужно писать своё дерево? Я к этому совсем не готов, особенно для BTree.
BTreeSet выглядит интересно, мне нужно всего лишь реализовать Ord... Я могу задать Ord на Range ∪ Zero...
Грубо говоря, я гарантирую, что либо у меня ноль, либо интервал без нулей. Я делаю get на позицию нового нуля, получаю None... А мне нужно получить range, в который этот ноль прийдёт. Окей.
Ага... Мне нужно задать очень хитрое отношение с нулём.
Zero(n) === x..y if n ∈ x..y
Но при этом я про себя знаю, что они не равны, и если я получил range, мне нужно его pop, split, insert.
Да, может быть получится.
Итак, задача: https://leetcode.com/problems/maximum-segment-sum-after-removals/
Дан массив положительных чисел и массив со списком позиций для удаления чисел. Нужно заменять в первом массиве (чисел) позицию из второго списка нулём. После этого нужно смотреть на массив чисел и отвечать какая сумма сегмента там самая большая. Сегмент - непрерывная последовательность чисел без нулей. Эти суммы надо записать в результат (для каждого удаления - максимальный размер сегмента в после данного удаления).
Т.е. после каждого удаления старый сегмент может оказаться поделен на два, и возможно что какой-то другой сегмент теперь больший.
Всего для массива в N чисел будет N удалений.
Решение в лоб тривиальное - заменяем элемент в массиве, считаем какой сегмент максимальный. Сложность n², потому что у нас надо N раз посчитать максимальный сегмент среди N чисел.
Дальше спойлер
Я быстро прошёл этапы локальной оптимизации. Наверное, самый интересный был с running sum, когда нулевой элемент обнулял current running sum, но сохранял max running sum и при сканировании сравнивалось значение нуля и если оно было меньше, чем у последнего элемента, мы прыгали прямо к нему. (т.к. в прошлый прогон у нас уже в последнем элементе max был). Это всё ерунда под которую есть контр-примеры с n² сложностью, и я не уверен, что у меня бы даже и получилось что-то сэкономить (обновлять-то running max всё равно надо у всех ненулевых элементов и у некоторых нулевых..., короче, skip).
Следующая идея была хранить числа в дереве/в рекурсии стека и понимать случаи "слева были нули/не было/примыкающий ноль" и т.д. Я взорвался в дереве состояний и условий.
Наконец, решение, которое я думаю, что работает, простое:
Segments = Zero(Left: Segments, Right: Segments) ∪ Range[x..y]
Дерево нулей, в котором либо полный отрезок без нулей (точнее, значения его начала/конца), либо пара значений (лево/право от нуля), где каждое значение ссылка на ноду (дерева), то есть на структуру самого себя. Плюс кешированный max для каждой половинки, плюс None, если ноль находится с "краю".
При каждом удалении мы обходим дерево, находим сегмент, в котором находится ноль, заменяем этот сегмент на новый Zero и 0-1-2 сегмента, пересчитываем суммы для этих двух сегментов, вычисляем максимум, пересчитываем максимум у родителя (не заходя во второго потомка) и так до самого верха, верх - результат для записи в output.
Я 100% уверен, что оно работает, сложность ~o(n*log(n)) (будет вставлено n нулей, каждый ноль log (n) обходов дерева. У меня трещит голова посчитать сложность посчёта максимума для массивов, но понятно, что она резко снижается после каждого нуля. Несколько "плохих" случаев легко покрываются локальными оптимизациями (ноль с краю - мы не пересчитываем длину отрезка, а просто вычитаем из него, ноль где-то посредине - считаем до середины в меньшем интервале и принимаем решение на середине о том, чему равен остаток (мы знаем общую сумму), но понятно, что в среднем это меньше n, и оно либо стремительно сокращается с каждой итерацией (если ноль в середине), либо легко высчитывается за малое число операций, если ноль с краю. В любом случае, у нас на каждом шагу отрезается m чисел из рассмотрения... Вероятно, там есть мерзкий пример с постоянным пересчётом по большому интервалу, но мне трудно додумать туда.
В любом случае, дерево тут - путь куда надо.
Но! Деревья медленные. Надо BTree. И я совершенно не понимаю как мне использовать BTreeMap в Rust для этой задачи. Я не понимаю, что является value. Более того, я даже не понимаю, что является key, потому что в моём наивном описании дерева нода - это или ноль (его позиция и информация об нодах слева/справа), либо интервал (leaf).
Получается, мне нужно писать своё дерево? Я к этому совсем не готов, особенно для BTree.
BTreeSet выглядит интересно, мне нужно всего лишь реализовать Ord... Я могу задать Ord на Range ∪ Zero...
Грубо говоря, я гарантирую, что либо у меня ноль, либо интервал без нулей. Я делаю get на позицию нового нуля, получаю None... А мне нужно получить range, в который этот ноль прийдёт. Окей.
Ага... Мне нужно задать очень хитрое отношение с нулём.
Zero(n) === x..y if n ∈ x..y
Но при этом я про себя знаю, что они не равны, и если я получил range, мне нужно его pop, split, insert.
Да, может быть получится.