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

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

ахаха. всем б такой брутфорс 😄 мне нравится ваш настрой. это точно в гуголь надо.

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

Стоит почитать

А брутфорсом тут TLE будет

А, нет. Тут ограничение в 1000 символов

Ребята

Кто-нибудь решил через матрицу?

Я решил через матрицу, но не заполнял в цикле, а через рекурсию.

Так проще показалось, хотя может и нет.

А как вы матрицу делали?

vector<vector<int>> dp(n, vector<int>(m)) или не про это речь?

т.е. как в прямом смысле или в каком 🙂

Сверху буквы первого слова, слева второго, и где сходится там 1?

vector<vector<int>> dp(n, vector<int>(m)) или не про это речь?

Ну вот да

Щас скину

Сверху буквы первого слова, слева второго, и где сходится там 1?

да, именно так

. . g h b r g c h 0 1 0000 c 00 000 1 b 00 1 000 g 1 0 00 10 c 00 000 1 r 00 0 100 c 00 000 1 b 00 1 000 h 0 1 0000

да, именно так

Я тоже до этого дошел

А как его обойти, не понимаю(

Уже полчаса сижу

Глазами все нашел

Понимаю что надо по диагонали прыгать если 1 нашел

ну вот я обходил рекурсивно, прямо по определению

А вот как что складывать чтобы результат получить – хз(

ну вот я обходил рекурсивно, прямо по определению

А какие числа добавляли?

Ну, что делали если встречали 1?

ща, прямо из второй подсказки делаю — если буковки на i и j позициях равны, то делаю 1 + dp[i + 1][j + 1], по диагонали идём, если не равны то максимум из dp[i + 1][j] и dp[i][j + 1]

т.е. выбрать максимум между вниз и направо

Ой...

А я и забыл про подсказки

Спасибо, сейчас попробую

Ещё там матёрые литкодеры пишут, что есть вариант с одномерным dp

не для средних умов говорят, поэтому я решил не пробовать 😄

Ещё там матёрые литкодеры пишут, что есть вариант с одномерным dp

Ну предыдущую, где тропинку найти тоже вроде одномерным можно было

Но что-то голова перегреется

Ещё там матёрые литкодеры пишут, что есть вариант с одномерным dp

Можно, нужно массив в две строки

Можно, нужно массив в две строки

Матёрый литкодер детектед 🙂

Можно, нужно массив в две строки

Всм?

Матёрый литкодер детектед 🙂

Да не. У меня даже 200 задач нет ещё

Масив с двумя масивами?

да, двумерный

но маленький

А, ну это да

Там же выше строчки отпадают

Знаю я одного гуглера из Варшавы, который решил 500 задач и устроившись спрашивал у других чуваков, которые крутили пальцев у виска, мол, мы и 200 не решили 😄

dp[2][len2]

Зависит все-таки от того насколько глубоко копать каждую задачку, там ж можно со всем сторон рассматривать.

И ещё от удачи в значительной стенени 😄

но маленький

Ну на самом деле это не имеет значени так то, поидее память просто в sqrt превратиться

И ещё от удачи в значительной стенени 😄

Это точно)

Кстати, объясните лентяю, sqrtN это же logN?

sqrt это корень квадратный

И ещё от удачи в значительной стенени 😄

Мне кажется не удача, а склад ума, т.к. предыдущую задачу за рекрное время решил, а над это танцую как из племени

sqrt это корень квадратный

Я это знаю, я про сложность

@vitkarpov выбает сложность O(sqrtN)?

Зависит все-таки от того насколько глубоко копать каждую задачку, там ж можно со всем сторон рассматривать.

На литкоде чем хорошо, есть задачи с усложнёнными версиями. Например, Unique Paths

Кстати, объясните лентяю, sqrtN это же logN?

ну, не совсем. они рядом, но корень всё-таки быстрее логарифма растёт.

@vitkarpov выбает сложность O(sqrtN)?

Конечно. В решете Эратосфена например есть что-то типа n * sqrt(n)

Ну можно найти и другие задачи.

Мне кажется не удача, а склад ума, т.к. предыдущую задачу за рекрное время решил, а над это танцую как из племени

хз. дпшечка традиционно у всех сложно идёт.

это нормально как раз.

Читал, кстати, твою статью про простые числа, где решето используется

Читал, кстати, твою статью про простые числа, где решето используется

О, крутяк! Давай фидбек 🙂

Мне понравилось. Разные варианты рассмотрел, и подробно.

Стараюсь придерживаться подхода от простого к сложному, в смысле чтобы и брутфорс был и потом усложнение постепенное.

Оно так и на реальном собесе должно идти, по идее, если ты решаешь незнакомую задачу.

Если знакомую, все равно надо сделать вид, что «пытаешься решить»

😄

В идеале, надо рассказать несколько вариантов, словами просто, сравнить, выбрать оптимальный и уже писать.

Мне понравилось. Разные варианты рассмотрел, и подробно.

🙇‍♂️

Конечно. В решете Эратосфена например есть что-то типа n * sqrt(n)

Конечно. В решете Эратосфена например есть что-то типа n * sqrt(n)

Если знакомую, все равно надо сделать вид, что «пытаешься решить»

Лишь бы не подумали, что ты только брутфорсом и можешь решать. И собеседование не закончили на этом)

Да, совсем чуть чуть

Мне кажется часто округляют

Как ни как действия со степенями

Обратные

Обратные

(Ну, в рациональном/комплексном поле)

Лишь бы не подумали, что ты только брутфорсом и можешь решать. И собеседование не закончили на этом)

ну не, ты ж рассуждаешь и приходишь к оптимальному решению. вот если ты начинаешь писать брутфорс и говоришь «лучше решить не можно!»

то ну такое себе… 🙂