Viktor
На самом деле если бы я не знал, что существует алгоритм bipartite то догадаться сложно
Viktor
Я не зря сказал про «покрасить в даа цвета»
Viktor
Да они издеваются — https://leetcode.com/explore/challenge/card/june-leetcoding-challenge/ 😄
Порридж В Ко-ливинге
Порридж В Ко-ливинге
Не отдохнуть
Viktor
Это всё карантин этот, людям делать нечего. Уже жду недождусь когда закончится.
Порридж В Ко-ливинге
Пхах, не только вы
Порридж В Ко-ливинге
Мне кажется умру если не устрюсь в Я
Порридж В Ко-ливинге
Будет “Game over” перед лицом
Viktor
А ещё визовые центры Британии открываются с 1 июня в Беларуссии и Украине, но не в России. Вай?! 😄
Порридж В Ко-ливинге
Viktor
Порридж В Ко-ливинге
Вчерашнюю задачу вообще нереально без DFS BFS решить?
Порридж В Ко-ливинге
Я что-то в дискас зашел, там одни DFS BFS
Порридж В Ко-ливинге
Как я догадываюсь, это типикал задачка для дерева
Порридж В Ко-ливинге
https://leetcode.com/explore/featured/card/may-leetcoding-challenge/537/week-4-may-22nd-may-28th/3342/discuss/655026/Using-two-sets-with-out-graph
Порридж В Ко-ливинге
О! Питонист единомышленник!!1!
Порридж В Ко-ливинге
Вместе мы противостоим DFS и BFS захватчикам!
Viktor
Порридж В Ко-ливинге
Я так же решал
Viktor
Порридж В Ко-ливинге
Только… говно код и помощь гугла
Порридж В Ко-ливинге
И у меня очень грязный код был
Порридж В Ко-ливинге
Это было ужасно в общем
Порридж В Ко-ливинге
Но сейчас я приведу его в человеческий вид и покажу вам
Порридж В Ко-ливинге
@vitkarpov а у вас сколько строк дерево заняло?
Порридж В Ко-ливинге
Можете скинуть самое короткое решение с деревом? Мне для изучения
Порридж В Ко-ливинге
А то в discuss так плато текста
Viktor
Порридж В Ко-ливинге
А какая complexity?
Порридж В Ко-ливинге
Лучше N^2 не может быть?
Viktor
Быстрее, ну хз. Наверное, как-то можно 🙂
Порридж В Ко-ливинге
У меня вопрос
Viktor
если память использовать дополнительную
Порридж В Ко-ливинге
А може быть такое, что будет [2,3] и при этом ни 2 ни 3 больше нигде не встречаться
Порридж В Ко-ливинге
Это не сломает алгоритм?
Viktor
Порридж В Ко-ливинге
Логично
Порридж В Ко-ливинге
Вроде не ломает
Порридж В Ко-ливинге
Ладно, походу графы не мое
Viktor
отличный фоллоу-ап сегодня 😂
Порридж В Ко-ливинге
Viktor
Ладно, походу графы не мое
графы это отдельная большая тема, да. кстати, вчера отличный пост сделали на эту тему — https://leetcode.com/discuss/general-discussion/655708/graph-problems-for-beginners-practice-problems-and-sample-solutions
Порридж В Ко-ливинге
В общем
Порридж В Ко-ливинге
Из O(govnoCode) сделал O(log(govnoCode))
Порридж В Ко-ливинге
https://pastebin.com/uqiXqdwe
Порридж В Ко-ливинге
И получилось короче чем у питонистов
Evgeniy
Evgeniy
Понял, убирает те пары, которые на данный момент не подходят "на потом"
Порридж В Ко-ливинге
Порридж В Ко-ливинге
Это было самое сложное
Evgeniy
А как это решение по времени?
Порридж В Ко-ливинге
Вот честно не знаю, но скорее всего N ^ 2
Порридж В Ко-ливинге
Порридж В Ко-ливинге
Это если ВСЕ узлы не связанны
Порридж В Ко-ливинге
И мы будет по 1 каждую итерацию убирать
Порридж В Ко-ливинге
Ну, там же по дефолту убирается 1, а остальные “на потом“
Evgeniy
Хм.. А rest у нас не обнулится (9), когда мы на очередной заход (4) пойдём?
Evgeniy
номера строк
Порридж В Ко-ливинге
Обнулиться
Evgeniy
По скобкам сложно сориентироваться
Порридж В Ко-ливинге
Оно же уничтожается в конце цикла
Evgeniy
аа
Evgeniy
точно, мы же его в dislikes скопировали, всё
Порридж В Ко-ливинге
Порридж В Ко-ливинге
Да, работает на чуде
Evgeniy
Да уж. "Рассовываю пока могу, а если не могу, с остатками разберусь потом снова"
Evgeniy
:)
Порридж В Ко-ливинге
Спонсор решения не на деревьях — “Не любовь Данила к деревьям! Не любовь к деревьям – что угодно лишь бы не DFS или BFS. Hate greenpiece!”
Evgeniy
Зелёные не одобряют)
Порридж В Ко-ливинге
Evgeniy
А если вместо unordered_set сделать set, то операция count будет за логарифм работать, а не за линию
Evgeniy
в худшем случае
Порридж В Ко-ливинге
Какая-то херня
Порридж В Ко-ливинге
Я не считаю что может быть линейная