У них разные цели. Хип для наибольшего и наименьшего. В БСТ - нахожение любого числа за log(N)

извините что вмешиваюсь, но просто вспомнил, что на стак оверфлоу когда смотрел bts vs heap, лучший ответ как раз говорил, что одно из главных заблуждений насчет хипа - что оно нужно (в сравнении с bst), только для того, чтобы иметь возможность за O(1) найти максимум. На самом деле основная фича хипа - вставка нового элемента за константное время (в среднем).

Вы чего, думаете щас побъем за “вмешиваюсь”? 🤣Конечно присоеденяйтесь к дискусии! За O(log N) вставка, и это свойство используется в 50% где в задаче нужен Хип.

в худшем случае - верно. Но на практике при большом количестве элементов оно константно. Скину сорс, чтобы просто пересказом не заниматься: https://stackoverflow.com/questions/6147242/heap-vs-binary-search-tree-bst

Да, я писал хипу, я знаю какая сложность там. Avg: O((log N) / 2) Max: O(log N) https://github.com/Glazomer/sorts/blob/master/sorts/heapsort.ts

это я про сегодняшнюю задачу

впервые решил задачу, и время выполнения не попало на график распределения 😄

Лол, настолько жестко, что даже линия не проходит?

@DmitryKormalev , Вот честно, на наебалово а не O(N) похоже

Это откуда?

Это откуда?

Блин, не в тот чатик отправил. Мне просто сказали что median of medians это O(N). Звучит очень сомнительно, хоть в Википедии и в MIT так написано

Я начал выписывать первые числа и понял что они мне что-то очень напоминают биномиальные коэффициенты 😀

Вернее даже «треугольник Паскаля»

Странно, O(N) у меня нормально проходит

Я половину дня потратил и результат такой что приняло только с третьего раза ))

Я половину дня потратил и результат такой что приняло только с третьего раза ))

Я половину дня потратил и результат такой что приняло только с третьего раза ))

Не плохо. А сколько задачек на Литкоде у тебя?

Я половину дня потратил и результат такой что приняло только с третьего раза ))

перед новым годом решил первую

Рантайм 7.5 секунд это сурово, но проходит.

перед новым годом решил первую

Ты главное не парься. Это мы тут монстры по 250, 400 задачек, которые это решаем на раз два. Если у тебя меньше 50, то решить мидиум за пару часов - нормально

Я бы сказал круто. Зависит от бекграунда, конечно, но обычно и изи по началу не решаются.

Ты главное не парься. Это мы тут монстры по 250, 400 задачек, которые это решаем на раз два. Если у тебя меньше 50, то решить мидиум за пару часов - нормально

Та я не парюсь )) Понемногу буду решать, раньше на codewars сидел, но там сильно проще + нет ограничений по рантайму и памяти

Я половину дня потратил и результат такой что приняло только с третьего раза ))

Happy Monday! 👋 Задача этой недели https://vitkarpov.me/posts/jump-game-vi/

Хорошая. Я дальше квадрата не осилил. Спасибо за разбор.

Happy Monday! 👋 Задача этой недели https://vitkarpov.me/posts/jump-game-vi/

Happy Monday! 👋 Задача этой недели https://vitkarpov.me/posts/jump-game-vi/

Happy Monday! 👋 Задача этой недели https://vitkarpov.me/posts/jump-game-vi/

Задача 1696. Виктор, у вас и так 400 задач, а вы еще новые решаете 🤣 Так и весь литкод прорешать можно)

По 52 задачи в год, раз в неделю 😄 ну там быстрее они добавляются все же.

Happy Monday! 👋 Задача этой недели https://vitkarpov.me/posts/jump-game-vi/

Happy Monday! 👋 Задача этой недели https://vitkarpov.me/posts/jump-game-vi/

Вообще, вот её более распространенная (и более простая) вариация: https://leetcode.com/problems/jump-game/ Я бы, честно, начинал с неё.

ну это в соседней команде, если что. у нас так ещё не упарываются

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

А на каком тесте у тебя в Jump Game VI выдало TLE? У меня 57

там где k=90000

Да, я видел. Я так понимаю это после 57, так как у меня k = 16309

Я прошу прощения, может кто-то в курсе. А что документация для C платная? И стоит $150 на Амазоне? И из-за этого все пользуются драфтом) или это такой способ задонатить?