Задача сортировки на графах в олимпиадах по программированию

Михаил Иванович Киндер, Андрей Витальевич Казанцев

Аннотация


Разобрана задача сортировки данных, отношение порядка между которыми описано в виде отношения смежности вершин на произвольном графе. Выделены подзадачи и вопросы, относящиеся к «окрестности» проблемы; их решение представляет собой своеобразные уровни «погружения» в решение общей задачи. Обсуждены алгоритмы решения отдельных подзадач для графов специального вида, а также различные подходы к решению проблемы сортировки в общем случае. Задача сортировки такого типа предлагалась на Кубке международной школы ISI-Junior по спортивному программированию в июле 2019 года (г. Иннополис).

Ключевые слова


олимпиады по информатике; олимпиады по математике; олимпиады по спортивному программированию; многоуровневые задачи; исследовательские задачи для школьников; задача сортировки на графах

Полный текст:

PDF


DOI: http://dx.doi.org/10.26907/1562-5419-2019-22-5-384-391