В описании формата выходных данных есть абзац, который как раз посвящен данному тесту:
Команда A занимает более высокое место, чем команда B, если она набрала большее количество очков, или они обе набрали одинаковое количество очков, но команда A одержала больше побед, чем команда B.
Конкретно в данном тесте Cplusplus и Java действительно набрали одинаковое количество очков, но за счет большего числа побед Cplusplus выходит на первое место, а Java занимает второе.
Мы открыли виртуальные контесты для всех отборочных раундов и финала Яндекс.Блица, теперь у всех желающих есть возможность поучаствовать в соревновании в рамках виртуального участника, присоединяйтесь.
Мы сделали задачу такой объемной по нескольким соображениям, вот, пожалуй, основные из них:
как я уже написал в разборе, довольно часто случаются задачи, в которых нужно разобрать входные данные и подготовить результат в нужном формате, специфичный формат вывода заставляет внимательно и аккуратно писать решение;
мы хотели, чтобы для решения одной из задач нужно было написать объемный фрагмент кода, в котором, если будет необходимо, найти и устранить ошибки, выявленные тестирующей системой;
мы хотели посмотреть на то, как участники будут распределять задачи по времени,
предполагали, что к данной они приступят после того, как у них не останется других задач для решения или по ним кончатся все идеи.
Прямо сейчас дорешивание открыто только для тех, кто зарегистрировался в соревновании. Возможно в будущем мы откроем виртуальный турнир для всех желающих.
В первой задаче мы сначала приводим решение, где просто выводим все процессы, которые нужно перезапустить, не учитывая при этом порядок, в котором их нужно выполнить. Для этой задачи действительно не требуется топологическая сортировка, достаточно реализованного обхода в глубину.
Далее мы решаем исходную задачу, где, по завершении обработки вершины внутри функции DFS, добавляем ее в конец вектора с результатом. Так мы гарантируем, что от добавленной на текущем шаге вершины будут зависеть только вершины, добавленные в этот вектор ранее, связей с вершинами, добавленными после текущей, не будет. Именно так и работает алгоритм топологической сортировки. В самом конце мы выводим этот вектор в обратном порядке и получаем ответ задачи.
Спасибо за внимательность! Опечатку в тексте и в формуле исправили.
Что касается T_0, то в сумме эта величина используется только при t=N или при t=0. В обоих случаях все элементы, кроме корня, попадают только в одно из поддеревьев. Значит, количество таких вариантов совпадает с количеством способов составить дерево поиска из N элементов. Поэтому, действительно, в этой задаче нужно положить T_0 = 1.
Конкретно в данном тесте Cplusplus и Java действительно набрали одинаковое количество очков, но за счет большего числа побед Cplusplus выходит на первое место, а Java занимает второе.
предполагали, что к данной они приступят после того, как у них не останется других задач для решения или по ним кончатся все идеи.
Далее мы решаем исходную задачу, где, по завершении обработки вершины внутри функции DFS, добавляем ее в конец вектора с результатом. Так мы гарантируем, что от добавленной на текущем шаге вершины будут зависеть только вершины, добавленные в этот вектор ранее, связей с вершинами, добавленными после текущей, не будет. Именно так и работает алгоритм топологической сортировки. В самом конце мы выводим этот вектор в обратном порядке и получаем ответ задачи.
Что касается T_0, то в сумме эта величина используется только при t=N или при t=0. В обоих случаях все элементы, кроме корня, попадают только в одно из поддеревьев. Значит, количество таких вариантов совпадает с количеством способов составить дерево поиска из N элементов. Поэтому, действительно, в этой задаче нужно положить T_0 = 1.