Доказательство корректности авторского решения со Всероссийской олимпиады

Revision ru1, by StasyaCat, 2018-04-21 20:05:43

Доброго времени суток!

Недавно я решал задачи с ХХХ Всероссийской олимпиады школьников по информатике. Меня весьма поразило авторское решение задачи 6 (подобный метод я не встречал нигде).

Может ли кто-либо объяснить мне почему авторское решение на 100 баллов корректно? А именно, почему метод построения обратной перестановки и решение задачи "наоборот" работает? Связано ли это с какими-то особыми свойствами обратной перестановки? Могу ли я подобный метод использовать для любых задач на перестановки (строить обратную данной и решать задачу с конца, заменив все действия обратными им)?

Условие задачи: http://neerc.ifmo.ru/school/archive/2017-2018/ru-olymp-roi-2018-day2.pdf

Разбор: http://neerc.ifmo.ru/school/archive/2017-2018/ru-olymp-roi-2018-analysis.pdf

Tags всероссийская олимпиада, доказательства, перестановки

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
ru1 Russian StasyaCat 2018-04-21 20:05:43 848 Первая редакция (опубликовано)