Не могу понять разбор задачи E из ИОИП прошлого года. Условия задач — http://neerc.ifmo.ru/school/ioip/problems-2016.pdf Разбор — http://neerc.ifmo.ru/school/io/archive/20160327/analysis-20160327-individual.pdf Мне понятно всё до последнего слайда. Вопрос номер один: в разборе утверждается, что при решении задачи для отрезка [0; 2d + 1] задачу можно будет легко решить и для остальных позиций путем проставления 0 и 1 в соответствии с их классом эквивалентности. Но почему не может возникнуть ситуации, когда такое проставление не даст корректного ответа для других отрезков(то есть сумма там не будет равняться требуемой)?

Первый вопрос снимается, если ответить на второй: в последнем пункте говорится, что cj равны между собой, то есть в отрезке [0; 2d + 1] у нас одинаковое количество непроставленных элементов для каждого класса эквивалентности. Действительно, тогда в других отрезках эти числа тоже будут одинаковыми и мы получим ответ на первый вопрос. Но каким образом можно доказать или хотя бы обнаружить это свойство? По-моему это утверждение совсем не очевидно.

Если у кого-нибудь есть другие идеи по поводу этой задачи, буду очень благодарен, если вы их озвучите).

Update: Кажется, стало немного понятнее, но до конца не уверен.