Evgeniy
Не все будут ждать тебя три месяца
Evgeniy
Или я ошибаюсь
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
Solution вроде как заблокирована(платно?)
Для разных задач по-разному, но вот для этой открытый solution — https://leetcode.com/problems/shortest-bridge/solution/
Viktor
Но мне кажется, что там треш, а не решение.
Viktor
А где вы читаете теорию про сложность, оптимальные решения/алгоритмы по задачам? Потому что решаю я, допустим, прикидываю сложность, память, но непонятно, оптимальное от решение :)
Вообще говоря, не понятно оптимальное или нет, согласен 🙂
Uladzimir
Я могу только график глянуть после сабмита
Uladzimir
Решение лучше, чем 50% - и что?)
Viktor
Решение лучше, чем 50% - и что?)
Я бы на грейдер литкодовский особенно не ориентировался, он сильно врёт 🙂
Uladzimir
Не, ну если за n в степени n делаешь по времени, увидишь ведь)
Viktor
ну если будет TLE то точно увидишь 😄
Uladzimir
TIL :)
Evgeniy
Залип на 1,5 часа на задаче https://leetcode.com/problems/shortest-bridge/ . Посмотрел потом в решения — а там awice какую-то мурню нечитаемую написал 😂
awice умеет написать простое сложным кодом
Evgeniy
А где вы читаете теорию про сложность, оптимальные решения/алгоритмы по задачам? Потому что решаю я, допустим, прикидываю сложность, память, но непонятно, оптимальное от решение :)
По книгам, статьям на сайтах. И постепенно запоминаешь и можешь уже прикидывать на глаз сложность
Порридж В Ко-ливинге
По книгам, статьям на сайтах. И постепенно запоминаешь и можешь уже прикидывать на глаз сложность
По-моему, надо простотзапомнить сложной функций в языке, и дальше будет очевидно
Evgeniy
По-моему, надо простотзапомнить сложной функций в языке, и дальше будет очевидно
Сложность типовых алгоритмов
Evgeniy
Сегодняшнюю задачу кто-то решил за O(n)?
Порридж В Ко-ливинге
Там разве хуже N принимает?
Порридж В Ко-ливинге
(Сам я еще не решал)
Порридж В Ко-ливинге
Там так пугают "уменьшино врем на 75%!"
Evgeniy
Но не реализовал ещё
Порридж В Ко-ливинге
Ок, ждем
Evgeniy
Там так пугают "уменьшино врем на 75%!"
Я так понимаю это намёк на то, что квадратичное не пройдёт
Evgeniy
Несмотря на малое количество данных
Порридж В Ко-ливинге
На всякий случай, а что N в данном контексте?
Наверное, количество инсертов за тест
Yuri
все ж-таки солюшены стоят что-то типа десяти баксов, а мы все собираемся зарабатывать 300 кк/сек 😊
Viktor
В общем, по-моему, ключевое в сегодняшней задаче это _consecutive days_. Я сперва не обратил на это внимание и пытался считать прямо до самого начала. Задача чем-то напоминает стек с функцией min, там тоже нужно «хранить стейт в каждом элементе стека».
Evgeniy
Для стека с минимумом я заводил отдельный массив
Evgeniy
Но, в принципе, можно и прямо в элементе хранить
Viktor
ну да, либо отдельный стек завести, второй, либо расширить интерфейс для элемента в текущем стеке, чтобы не просто чиселку там хранить, а структурку.
Evgeniy
В этой задаче тоже думал про стек, но не подобрал ему применение
Порридж В Ко-ливинге
Viktor
В этой задаче тоже думал про стек, но не подобрал ему применение
Каждый элемент может хранить в себе знания о том сколько дней до него было с <= ценой, когда встречается следующий день, то мы можем снять со стека предыдущий день и достать оттуда чиселку сколько consecutive дней было меньше до него и всё: добавить для текущего значения и положить на стек. Таким образом не надо постоянно бегать назад и проверять сколько же чисел меньше данного. Это снижает сложность с O(N^2) до O(N), в худшем случае придётся накопить и размотать весь стек целиком один раз, ну и память O(N) под стек.
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
Evgeniy
