И везде его имя

Ну да, потому что это его фул-тайм работа

И почему-то мне показалось что вы вместе с ним работали

Ну да, потому что это его фул-тайм работа

О

Наверное ему тоже можно вопросы задавать

Ну да, потому что это его фул-тайм работа

На нем прям висит bem-react?

Пожизненное наказание? 🤣

Ну да, типа руководитель всего это дела.

Оу, ок, учту)

Пожизненное наказание? 🤣

ну пока не уволится, да 😄

Как я понял, ждем дальше задачи easy

Потому что, если я решил задачу не угробив на неё час минимум… Значит задача легкая…

Да что, ну не надо же сразу выходить

Я на других легких задачах застревал так, что стыдно

хз. я б не сказал, что задачка простая. нормальный такой медиум. в лоб не решается.

хз. я б не сказал, что задачка простая. нормальный такой медиум. в лоб не решается.

Странно, я решил в лоб

Что такое в лоб? 😄

Что такое в лоб? 😄

Просто проитерировал с конца и все

лол. это не в лоб. как вы вообще до этого догадались?

Подсказка в том, что категория Greedy

Подсказка в том, что категория Greedy

да. подсказка слегка выдает.

лол. это не в лоб. как вы вообще до этого догадались?

Ну, подумал, что может быть “ловушка”

Просто проитерировал с конца и все

Тоже так хотел. Работает значит

ну, я к тому что в лоб это когда ты рекурсивно делаешь все прыжки постоянно вперед и вперед

а потом уже понимаешь, что это TLE и начинаешь думать. и понимаешь, что надо назад.

конечно, если вы сразу поняли, что надо назад — ну ок. хорошая интуиция 😄

А, ну значит это задачка, которая для меня простая

Я вот например на элементарных деревьях танцую с бубнами

это, кстати, вполне нормально. какие-то темы лучше идут, какие-то хуже.

ну, я к тому что в лоб это когда ты рекурсивно делаешь все прыжки постоянно вперед и вперед

Ну тут у нас есть четкое знание, что надо добраться до конца. От этого исходим

А если делать сначала, то да. На перебор времени не хватит

А вот и дпшечка началась. Это я про сегодняшнюю задачу. Подсказки хорошие, помогают понять лучше дп.

Да, без подсказок можно долго сидеть)

В целом по сути та же самая задача как и с поиском кратчайшего пути в матрице из левого угла в правый.

В принципе, да. Но эту я рекурсивной решал, начинать слева как-то понятнее.

Хоть и заполнение матрицы будет справа, понятное дело, когда рекурсия назад начнёт разматываться.

я тоже решил рекурсивно. а потом посмотрел решения и, как обычно, почувствовал себя тупым

В целом по сути та же самая задача как и с поиском кратчайшего пути в матрице из левого угла в правый.

Блин, подсказка(

В целом по сути та же самая задача как и с поиском кратчайшего пути в матрице из левого угла в правый.

Т.е. за O(N) решается?

N^2

Но может кто и за N придумает)

Я пытаюсь понять тут решение человека NlogN

N^2

Ну, N^2 я догадываюсь

Просто выпилить лишние символы и прогнать от каждого символа

Мне нравится как все говорят N, хотя там две строки разной длины: пусть их длины N и M.

Мне нравится как все говорят N, хотя там две строки разной длины: пусть их длины N и M.

Ну, это не так важно

А ну да, N*M)

Просто я на квадратном примере разбирал))

Просто можно сказать что N – длина большей

Это неправильно, просто для удобства

Т.е. за O(N) решается?

я правильно понимаю, что вы допускаете, что есть такое решение которое ограничено проходом только по одной строке без учёта второй вообще, да? 😄

Нет, я же сказал что N – большая строка

А на фоне большей N, меньшая M – превращается O(2*N)

А это O(N)

Это наверное не возможно

Но все же

А на фоне большей N, меньшая M – превращается O(2*N)

Да где 2*N если там N*N, если мы принимаем что N=M, пусть так будет.

Я пока не пойму вообще как можно лучше чем за квадрат здесь решить.

А у вас там линия легко получается уже 😄

Хотел бы услышать решение.

Я пока не пойму вообще как можно лучше чем за квадрат здесь решить.

Ну кто-то за NlogN решил

Ну кто-то за NlogN решил

😱

Я пытаюсь понять тут решение человека NlogN

.

Вот

👍

Да, в сабмитах в топах там)

Я пока думаю, N*M сразу приходит, грубо говоря брут форс

Не брутфорс - это N^K

Кажись нашёл — https://en.wikipedia.org/wiki/Hunt%E2%80%93Szymanski_algorithm

на википедии

ну это advanced-уровень уже

в гуголь 😄

Не брутфорс - это N^K

Разве?

Разве?

конечно. на каждый рекурсивный вызов вы ещё два делаете.

стоп, а почему N^M, а не 2^(N + M) 🤔

Идешь от for (i = 0 … N) for (i … M)

@Dastin_DV а какой там брутфорс ты хочешь?

что N^M

Вот здесь классно чувак разобрал и наивный подход и дпшечку в плане оценки сложности

https://stackoverflow.com/questions/34688026/understanding-the-time-complexity-of-the-longest-common-subsequence-algorithm