Evgeniy
Не все будут ждать тебя три месяца
Evgeniy
Или я ошибаюсь
Uladzimir
Наверняка от контракта зависит, просто мне такие условия называли
Uladzimir
Uladzimir
Evgeniy
Интересно, как у них с текучкой
Evgeniy
При таких условиях
Uladzimir
Так и в обратную сторону работает. Увольняют - через 3 месяца уходишь)
Uladzimir
И 3 зп как минимум получаешь
Uladzimir
Но после 6 месяцев испыталки
Evgeniy
Я где-то читал, кстати, что немцы "покупают" часы на работе. Что позволяет потом выйти раньше на пенсию
Uladzimir
Все может быть, не особо любят впахивать. Work life balance
Viktor
Залип на 1,5 часа на задаче https://leetcode.com/problems/shortest-bridge/ . Посмотрел потом в решения — а там awice какую-то мурню нечитаемую написал 😂
Viktor
Задачка огонь.
Порридж В Ко-ливинге
А, ну тут в теории можно за O(log(N))
Uladzimir
А где вы читаете теорию про сложность, оптимальные решения/алгоритмы по задачам? Потому что решаю я, допустим, прикидываю сложность, память, но непонятно, оптимальное от решение :)
Uladzimir
Может быть это типовая задача и есть разобранное решение
Uladzimir
Solution вроде как заблокирована(платно?)
Viktor
Но мне кажется, что там треш, а не решение.
Viktor
Uladzimir
Я могу только график глянуть после сабмита
Uladzimir
Решение лучше, чем 50% - и что?)
Uladzimir
Не, ну если за n в степени n делаешь по времени, увидишь ведь)
Viktor
ну если будет TLE то точно увидишь 😄
Uladzimir
TIL :)
Evgeniy
Evgeniy
Порридж В Ко-ливинге
Evgeniy
Evgeniy
Сегодняшнюю задачу кто-то решил за O(n)?
Порридж В Ко-ливинге
Порридж В Ко-ливинге
Там разве хуже N принимает?
Порридж В Ко-ливинге
(Сам я еще не решал)
Порридж В Ко-ливинге
Там так пугают "уменьшино врем на 75%!"
Evgeniy
Но не реализовал ещё
Порридж В Ко-ливинге
Ок, ждем
Evgeniy
Несмотря на малое количество данных
Порридж В Ко-ливинге
Yuri
Viktor
Yuri
все ж-таки солюшены стоят что-то типа десяти баксов, а мы все собираемся зарабатывать 300 кк/сек 😊
Evgeniy
Viktor
В общем, по-моему, ключевое в сегодняшней задаче это _consecutive days_. Я сперва не обратил на это внимание и пытался считать прямо до самого начала. Задача чем-то напоминает стек с функцией min, там тоже нужно «хранить стейт в каждом элементе стека».
Evgeniy
Для стека с минимумом я заводил отдельный массив
Evgeniy
Но, в принципе, можно и прямо в элементе хранить
Viktor
ну да, либо отдельный стек завести, второй, либо расширить интерфейс для элемента в текущем стеке, чтобы не просто чиселку там хранить, а структурку.
Evgeniy
В этой задаче тоже думал про стек, но не подобрал ему применение
Порридж В Ко-ливинге
Порридж В Ко-ливинге
Viktor
В этой задаче тоже думал про стек, но не подобрал ему применение
Каждый элемент может хранить в себе знания о том сколько дней до него было с <= ценой, когда встречается следующий день, то мы можем снять со стека предыдущий день и достать оттуда чиселку сколько consecutive дней было меньше до него и всё: добавить для текущего значения и положить на стек. Таким образом не надо постоянно бегать назад и проверять сколько же чисел меньше данного. Это снижает сложность с O(N^2) до O(N), в худшем случае придётся накопить и размотать весь стек целиком один раз, ну и память O(N) под стек.
Evgeniy
Evgeniy
Там не постоянно возрастающая последовательность
Evgeniy
Я об этом тоже думал. Но как
Viktor
пока последовательность возрастает, надо на стек складывать, как только возрастание прерывается, надо размотать и сложить на стек последнюю цену + чиселку, которая показывает как раз длину этого отрезка, на будущее.
Evgeniy
Тогда получится n^2
Viktor
я на стеке храню структурку из двух полей.
Evgeniy
если разматывать
Evgeniy
Хотя
Viktor
в худшем случае он накопится целиком если все цены возрастают и никогда не прерываются
Evgeniy
т.е. 2n
Evgeniy
хм
Viktor
ну я бы сказал K * N
Evgeniy
ну или так
Evgeniy
смотря сколько пиков
Viktor
какой именно этот K — хз, но главное, что коэффициент
Evgeniy
ну тут надо пробовать
Viktor
смотря сколько пиков
ну, кстати, да. смотря сколько целиком непрерывных убывающих подпоследовательностей
Evgeniy
пройдёт ли по времени
Evgeniy
New
Viktor
https://t.me/c/1239078613/3883
Evgeniy
Реализация задачи на стеке медленная очень. Зато по памяти 100%. И всего несколько строк.