а это уже подстава...
Dec. 5th, 2022 04:13 pm![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
amaraoМоя задача про максимальный сегмент после удаления элемента...
Моё решение o(n log n). Предыдущая попытка была отвергнута как timed out... Вторая попытка (практически тот же текст):
И я чувствую себя слегка обиженным, потому что я не менял решение.
Моё решение: хранить сегменты в BTree, при удалении элемента вынимать сегмент и вставлять на его место два.
Максимум хранится в BTree в виде размер сегмента: количество сегментов с таким размером.
При удалении сегмента, его размер удаляется из дерева сегментов (или делает -1). При добавлении - либо вставляется, либо делает (+1).
Максимум из Btree находится за n log n. Решение - n log n амортизированное, n^2 - worst case (на который я наткнулся в бенчмарке - удалять элементы по-очереди).
... А вот теберь я готов пойти читать про finger tree, и может быть, я открою для себя что-то новое.
UPD: Даже сравнить не с чем:
Моё решение o(n log n). Предыдущая попытка была отвергнута как timed out... Вторая попытка (практически тот же текст):
Runtime: 1874 ms, faster than 100.00% of Rust online submissions for Maximum Segment Sum After Removals.
Memory Usage: 6.1 MB, less than 100.00% of Rust online submissions for Maximum Segment Sum After Removals.
И я чувствую себя слегка обиженным, потому что я не менял решение.
Моё решение: хранить сегменты в BTree, при удалении элемента вынимать сегмент и вставлять на его место два.
Максимум хранится в BTree в виде размер сегмента: количество сегментов с таким размером.
При удалении сегмента, его размер удаляется из дерева сегментов (или делает -1). При добавлении - либо вставляется, либо делает (+1).
Максимум из Btree находится за n log n. Решение - n log n амортизированное, n^2 - worst case (на который я наткнулся в бенчмарке - удалять элементы по-очереди).
... А вот теберь я готов пойти читать про finger tree, и может быть, я открою для себя что-то новое.
UPD: Даже сравнить не с чем:
Accepted Solutions Runtime Distribution
Sorry. We do not have enough accepted submissions to show distribution chart.
Accepted Solutions Memory Distribution
Sorry. We do not have enough accepted submissions to show distribution chart.
А теперь пятиминутка унижения: есть решение за O(n) в примерно 10 строк.
Вздох... Но я пытался.
А теперь пятиминутка унижения: есть решение за O(n) в примерно 10 строк.
Вздох... Но я пытался.