Відео

На последних часах пятичасовых соревнований нередко есть выбор между поиском ошибки в решении одной задачи или написанием с нуля решения другой задачи. Стресс-тестирование в такой ситуации может очень сильно помочь. Кроме того, есть форматы соревнований, когда решения отправляются «втёмную» (то есть итоговый вердикт становится известен только после окончания). В этом случае стресс-тестирование просто незаменимо.

Спасибо за наблюдательность, здесь на слайдах ошибка. Правильная последовательность шагов при поиске элемента 33: L = 0, R = 19, M = 9; A[M] > 33, смещаем R на M - 1 L = 0, R = 8, M = 4; A[M] < 33, смещаем L на M + 1 L = 5, R = 8, M = 6; A[M] > 33, смещаем R на M - 1 L = 5, R = 5, M = 5; A[M] < 33, смещаем L на M + 1 L = 6, R = 5; индексы зашли друг за друга, следовательно, элемента 33 в массиве нет.

@@op_ulstu понял, большое спасибо за уточнение! И за курс в целом - он отличный!

Мы начали с такого примера и такого решения потому, что для начинающих зрителей они являются более понятными и естественными. Далее мы придём к более общему решению. Задача, которая решается при помощи бинпоиска, чаще состоит не в том, чтобы найти какое-то заданное значение, а в том, чтобы найти первый или последний элемент, обладающий определённым свойством. Для таких задач уже проще запомнить общее решение, когда цикл while идёт до 2 элементов, а l и r всегда смещаются на m (без +1/-1). Подробнее об этом рассказано в следующем видео: ua-cam.com/video/_u2yypDA6R0/v-deo.html Когда нужен поиск заданного значения в массиве, его можно выполнять так, как показано здесь, но можно воспользоваться и вышеупомянутой общей схемой, например, искать первый элемент, который больше или равен заданному значению (цикл while в этом случае идёт до 2 элементов, l и r смещаются на m).

@@op_ulstu благодарю! Вы один из топовых авторов по объяснению алгоритмов.

acm.khpnets.info/wiki/Алгоритм_Флойда

Здравствуйте. Увы, нет.

Что именно вас смутило? a и b в split() - это указатели на вершины результирующих деревьев, они имеют тип Node *. Это выходные параметры, мы хотим изменять их внутри split, поэтому передаём их по ссылке: Node *&. Если хотите, можете возвращать из split пару указателей: pair<Node *, Node *> split(Node *n, int key).

@@op_ulstu это некоторый мем с лабораторных работ по C в моём универе, если подойти с таким на сдачу лабы, то вас не будут принимать следующие полчаса, так как в си такая конструкция не имеет смысла. Если говорить о том что меня смутило в этом видеоролике, то мне и словами не описать ту боль которую мне пришлось пережить чтобы понять как дерево на самом деле работает, то как вы объяснили на визуализации конечно складно и понятно, но код так не работает, (я говорю о ф-ии split). Возможно этого поверхностного "понимания" достаточно чтобы использовать такой подход как инструмент в олимпиадных задачах и далеко не всем хочется знать как обстоят дела на самом деле

@@klausvreinherz7145 Код в видео написан на C++, а не на C. Здесь & - это не операция взятия адреса (в объявлении типа эта операция всё равно не имела бы смысла), а признак ссылки. В показанном коде *& - не две взаимообратные операции, а ссылка на указатель.

@@op_ulstuпоэтому я и упомянул что лабораторные мы писали на си

@@op_ulstu так как этот мем был несколько неуместен, но всё же достойным упоминания в обществе моих одногрупников, с коими я и пытался смотреть ваше видео

Проверка, существует ли ребро между вершинами a и b, - не бесплатная операция. Представьте себе запуск DFS на пустом графе из 1000 вершин. Если граф был сохранён в виде списков смежности, то после запуска DFS от каждой вершины мы сразу делаем вывод, что у неё нет соседей, так как соответствующий список смежности пуст; в цикл for мы даже не входим. Итого O(1) на обработку каждой вершины и общая сложность O(V) для запусков от всех вершин. Если граф был сохранён в виде матрицы смежности, после запуска от любой вершины алгоритму придётся просмотреть 1000 ячеек соответствующей строки матрицы, чтобы понять, что там всюду нули и соседних вершин нет. Итого O(V) на обработку каждой вершины и общая сложность O(V^2).

Задачу

А случаем не в нлогн

Кружок такой есть

Ответ на ваш вопрос - чуть далее по плейлисту, в видеозаписях про алгоритм Флойда-Уоршелла.

@@op_ulstu Я неправильно наверно выразилась - алгоритм Floyd ищет все кратчайшие пути попарно, но у меня всё-таки задачи более похоже на алгоритмДейкстры. То есть мне нужно найти все возможные пути от Start до Finish, где Start и Finish фиксированной… В отличие от видео нужно распечатать все пути от Start до Finish если их несколько. Надо структуру from дополнить? Или другой алгоритм искать?

@@vidruska Вы можете попробовать сделать вектор from двумерным, чтобы в ячейке с индексом to сохранять не одного, а сразу всех возможных предков вершины to на каком-то кратчайшем пути (добавится условие else if (dist[to] == dist[nearest] + weight) from[to].push_back(nearest); ). Затем вам придётся написать рекурсивную функцию, перебирающую все возможные пути от finish до start по этому массиву. Правда, имейте в виду, что количество кратчайших путей между start и finish в графе может быть экспоненциальным, и в общем случае вывести их все не получится. Рассмотрите, например, граф: 7 12 1 2 100 1 2 100 2 3 100 2 3 100 3 4 100 3 4 100 4 5 100 4 5 100 5 6 100 5 6 100 6 7 100 6 7 100 Даже в этом маленьком графе между вершинами 1 и 7 есть 64 различных кратчайших пути.