Не могу понять разбор задачи 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: Кажется, стало немного понятнее, но до конца не уверен.
Условия задач — 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: Кажется, стало немного понятнее, но до конца не уверен.
