ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

Обсуждение задачи 1218. Episode N-th: The Jedi Tournament

Another approach
Послано andreyDagger 11 ноя 2021 22:35
I see many people solved this with graph algorithms, there is also greedy approach.

Let's build graph: u->v, if jedi u is winning v.
You are doing n iterations, on every iteration you check, can current Jedi win, or not. There is greedy strategy to check this. You can eliminating enemies in order of the number of incoming edges. The fewer edges lead to a Jedi, the earlier we should eliminate him

Edited by author 11.11.2021 22:35

Edited by author 11.11.2021 22:35

Edited by author 11.11.2021 22:36