K
Тогда для соседних вершин условие будет нарушено
Тогда для двух вершин с минимальной буквой условие будет нарушено
Size: a a a
2020 May 03
K
А, понял
DK
EZ
чтобы попрактиковаться
Звучит довольно бесполезно, если учитывать что практика будет заключаться в том чтобы набить код центроидной
DK
Что-то типо такого теста, но высоты sqrt(n)
ГА
Доброй ночи. Вопрос такой. Я щас пишу алгоритм Крускала, все работает, но есть один нюанс. В главном цикле, где я уже перебираю отсортированные ребра, я ограничиваю кроме размера списка этих ребер еще и когда размер МОД будет меньше |V| - 1. Это может давать ошибку?
DK
Тогда для двух вершин с минимальной буквой условие будет нарушено
Именно поэтому вершина, в которой записана минимальная буква, обязана быть единственной с такой буквой
K
Именно поэтому вершина, в которой записана минимальная буква, обязана быть единственной с такой буквой
Ага, центроидная
DK
Ага, центроидная
Это задача с раунда на CF и там людей взламывали тестом выше. Они брали середину диаметра
DK
В претестах этого не было
EZ
В претестах этого не было
Найс
AE
Здесь 3 и 4 местами переставлены?
A(
Доброй ночи. Вопрос такой. Я щас пишу алгоритм Крускала, все работает, но есть один нюанс. В главном цикле, где я уже перебираю отсортированные ребра, я ограничиваю кроме размера списка этих ребер еще и когда размер МОД будет меньше |V| - 1. Это может давать ошибку?
что такое МОД в данном случае?
DK
Andrew Evseev
Здесь 3 и 4 местами переставлены?
Да
2020 May 04
AE
Дано дерево из миллиона вершин, в вершинах можешь писать буквы от A до Z. Размести буквы в дереве так, чтобы выполнялось следующее:
на кратчайшем пути между различными вершинами, имеюшими одинаковую букву letter, существует хотя бы одна вершина с буквой в ней, находящаяся в английском алфавите раньше буквы letter
на кратчайшем пути между различными вершинами, имеюшими одинаковую букву letter, существует хотя бы одна вершина с буквой в ней, находящаяся в английском алфавите раньше буквы letter
В корне буква A, её дети B, их дети C и так далее. А дерево какое?
EZ
Andrew Evseev
В корне буква A, её дети B, их дети C и так далее. А дерево какое?
А если глубже 27?)
DK
Andrew Evseev
В корне буква A, её дети B, их дети C и так далее. А дерево какое?
Если так заполнять, то не хватит букв для 1000*(1000+1)/2 вершин
MB
Всем привет, ребята есть задачи на центроидную декомпозицию ? (нашел бы сам через блоги в кф но он лег ( )
Открытая олимпиада, длинный тур, задача D.
AE
Если так заполнять, то не хватит букв для 1000*(1000+1)/2 вершин
Дерево произвольное?
ГА
что такое МОД в данном случае?
Минимальное остовное дерево