Evgeniy

Поэтому ребра графа будут 1-2 и 3-3 для второго случая

Логично

Evgeniy

Собственно, к чему веду: всегда ли путь до клетки, достигнутый с минимальными усилиями (в сумме) будет гарантированно содержать максимальное значение веса ребра, которое будет ответом?

Ilia

не, тут точно не сумма нужна же

Ilia

1-1-1-1-1 и 2-2 как пример

Evgeniy

Ну да, вот и думаю поэтому, можно ли тут дп применить

Evgeniy

Да, все же тут просто нужно писать минимальное усилие

Evgeniy

Нестандартный Дейкстра получается)

Viktor

не, тут точно не сумма нужна же

ага, я в это же упёрся. то есть рекуррентную зависимость просто от соседних клеток не вывести.

Evgeniy

ага, я в это же упёрся. то есть рекуррентную зависимость просто от соседних клеток не вывести.

Вот вот...

Evgeniy

Два нижних с хешсетом, два верхних — с обычным булевым массивом (причем код одинаковый). Как так? Такая разница аж 200мс.

Lynn «Кофеман»

Собственно, к чему веду: всегда ли путь до клетки, достигнутый с минимальными усилиями (в сумме) будет гарантированно содержать максимальное значение веса ребра, которое будет ответом?

Ну так собственно вес пути и есть вес максимального ребра

Evgeniy

Ну так собственно вес пути и есть вес максимального ребра

Ага. Получается так.

Lynn «Кофеман»

Но я пока не понял как работают чужие решения. У меня брутфорсный алгоритм как я бы сам решал на бумажке. С поиском в ширину

Evgeniy

Например, я сначала ищу минимальный и максимальный effort по всему массиву. А потом бинарным поиском, совместно с dfs подбираю минимально возможный, который позволяет достичь правого нижнего угла.

Ilia

брутфорс всех efforts в runcode выдает правильный ответ, а в submit TLE 🙁

Nikita

Поясните плиз, где вы берете "задачу на сегодня"? Из запиненных сообщений?

Ilia

Поясните плиз, где вы берете "задачу на сегодня"? Из запиненных сообщений?

Литкод соревнование месяца

Ilia

Поясните плиз, где вы берете "задачу на сегодня"? Из запиненных сообщений?

https://leetcode.com/explore/featured/card/january-leetcoding-challenge-2021/

Nikita

@vitkarpov читал эту статью https://grfia.dlsi.ua.es/ml/algorithms/references/editsurvey_bille.pdf ?) Увидел у тебя в твите про виртуальный дом видео)

Nikita

@vitkarpov читал эту статью https://grfia.dlsi.ua.es/ml/algorithms/references/editsurvey_bille.pdf ?) Увидел у тебя в твите про виртуальный дом видео)

Пожалуй лучшее с чем я познакомился, когда занимался фронтом

Порридж В Ко-ливинге

@vitkarpov читал эту статью https://grfia.dlsi.ua.es/ml/algorithms/references/editsurvey_bille.pdf ?) Увидел у тебя в твите про виртуальный дом видео)

С учетом того, что последние 2 фамилии - в топ 5 самых популярных в Китае, то мне кажется не самое лучшее название 🤣🤣🤣

Viktor

@vitkarpov читал эту статью https://grfia.dlsi.ua.es/ml/algorithms/references/editsurvey_bille.pdf ?) Увидел у тебя в твите про виртуальный дом видео)

да, это крутая история, не читал, но одобряю. надо. я помню сами ребята из реакта писали, что сравнение деревье в общем виде N^3 кажись и поэтому они всякие предположения делали, которые помогали срезать углы.

Nikita

По правде сказать, я ее не до конца понял. Читал летом и у меня там были вопросы к паре лемм, но когда я скинул своей тиме никто видимо кроме меня особо не заинтересовался ¯\_(ツ)_/¯ Так что можно будет потом обсудить)

Evgeniy

брутфорс всех efforts в runcode выдает правильный ответ, а в submit TLE 🙁

А пройденные клетки запоминаешь?

Evgeniy

С учетом того, что последние 2 фамилии - в топ 5 самых популярных в Китае, то мне кажется не самое лучшее название 🤣🤣🤣

Хорошо, что не Нгуен :)

Ilia

А пройденные клетки запоминаешь?

да я же говорю, тесты на которых TLE запускаю через runcode ответ правильный )

Ilia

Хорошо, что не Нгуен :)

учитывая, что у китайцев очень уважаемая и считает удачной Hui, то я бы посппорил с этим выражением ))

Ilia

даже статья на вики есть, лол https://en.wikipedia.org/wiki/Hui_(surname)

Evgeniy

да я же говорю, тесты на которых TLE запускаю через runcode ответ правильный )

Там все тесты суммируются, тоже такое было с другими задачами. А какой тест падает? У меня 15тый падал

Ilia

Там все тесты суммируются, тоже такое было с другими задачами. А какой тест падает? У меня 15тый падал

41/75

Evgeniy

учитывая, что у китайцев очень уважаемая и считает удачной Hui, то я бы посппорил с этим выражением ))

Ого, сколько популярных людей с таким именем)

Ilia

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

Evgeniy

Например, я сначала ищу минимальный и максимальный effort по всему массиву. А потом бинарным поиском, совместно с dfs подбираю минимально возможный, который позволяет достичь правого нижнего угла.

@goodhoopoe попробуй этот подход

Ilia

я не умею в бинарный поиск ) я взял все эффорты в сет, отсортировал и по ним иду через dfs

Evgeniy

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

"На букву Ха, окончание на Уи" Так?))

Ilia

"На букву Ха, окончание на Уи" Так?))

точно не помню, помню были шутки на эту тему ))

Viktor

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

Viktor

но код чистенький получился, на 28 строк

Ilia

Сегодня впервые за долгое время потребовалось применить простеньких алгоритмов фильтрации дублей, понял что не зря это всё решаю :D

Viktor

Сегодня впервые за долгое время потребовалось применить простеньких алгоритмов фильтрации дублей, понял что не зря это всё решаю :D

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

Ilia

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

Как всегда в условиях 10 минут перед релизом вылезло, так что думаю новый навык быстрого размышления помог ))

Порридж В Ко-ливинге

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

Не факт что о таком вы вооьще могли подумать)

Порридж В Ко-ливинге

Как это хранить список подписчиков не в массиве? Ну ходим каждый раз по массиву, чтобы удалить, ну и что? Ну будет на старых телефонах тормозить если по 3-4 пользователя блокировать (их будут удалять из массива)

Порридж В Ко-ливинге

Как это хранить список подписчиков не в массиве? Ну ходим каждый раз по массиву, чтобы удалить, ну и что? Ну будет на старых телефонах тормозить если по 3-4 пользователя блокировать (их будут удалять из массива)

Понятно что это можно обойти 100500 способов, но это абстрактный пример, первое что в голову

Порридж В Ко-ливинге

Google Amazon Facebook Apple LinkedIn Uber Lyft Twitter Pinterest ByteDance Netflix Cloudera Square Tesla Stripe Dropbox Snap AirBnb Snowflake Robinhood DoorDash

Порридж В Ко-ливинге

Google Amazon Facebook Apple LinkedIn Uber Lyft Twitter Pinterest ByteDance Netflix Cloudera Square Tesla Stripe Dropbox Snap AirBnb Snowflake Robinhood DoorDash

@azarovalex у тебя конкурент 🤣

Evgeniy

но код чистенький получился, на 28 строк

А по времени как?

Viktor

А по времени как?

по-моему, быстрее 30% что ли