@Mashush

Как решить данную олимпиадную задачу?

Юбилейная задача
Каждый из расположенных вдоль Н-ского проспекта N фонарных столбов покрашен в один из трех цветов: серый, бурый или малиновый. Главный архитектор хочет, чтобы к юбилею города все столбы имели одинаковый цвет. Он решил составить план перекраски, но знакомиться с имеющейся раскраской у него нет времени. Поэтому план должен быть универсальным, то есть приводить к нужному результату при любой начальной раскраске. План состоит из списка пар столбов. Этот список просматривается последовательно. Если оба столба очередной пары списка имеют одинаковый цвет, то их не трогают, иначе они перекрашиваются в третий цвет (не совпадающий с их цветами).
Помогите главному архитектору составить такой план, по возможности меньшей длины.
Входные данные
Требуется решить задачу для следующих входных данных: 5, 7, 8, 12, 25, 32, 34, 128, 253, 511, 999, 1000
Выходные данные
Решением задачи являются выходные файлы. Первая строка выходного файла должна содержать число N для данного теста. Если задачу решить невозможно, вторая строка должна содержать число 0. В противном случае вторая строка должна содержать число M — количество пар в плане, каждая из следующих M строк должна содержать пару чисел — номера столбов.
Пример 1
N = 3
3
0
Пример 2
N = 4
4
4
1 2
3 4
1 3
2 4
Комментарий
И так, я даже не знаю с чего начать. На первый взгляд задача кажется простой, но для меня лично лишь на первый взгляд. Сам я учусь на 3 курсе в колледже, мне почти 19 и самим программированием я начал заниматься сравнительно недавно. Пишу на JS, не отлично, но вполне неплохо в нем разбираюсь. Но на текущей задаче у меня просто затуп. Что я только не пытался делать, но мне никак не дается понять, почему при N = 3 не существует решения.
В задаче четко сказано - количество фонарей изначально неизвестно, точно также неизвестна и их раскраска. Получается, что вариант "3 фонаря = 3 разных цвета => два перекрашиваются и задача решена" имеет место быть.
Прошу помочь, если хоть и не решить задачу, то хоть как-то примерно объяснить словами, а на код я уже попытаюсь перенести сам
  • Вопрос задан
  • 651 просмотр
Решения вопроса 1
wataru
@wataru Куратор тега Алгоритмы
Разработчик на С++, экс-олимпиадник.
Это задача на придумывание паттерна и доказывание его. Тут надо рисовать всякие случаи на бумажке и обобщать.

Во-первых, когда встает вопрос о можно-нельзя ли какими-то операциями получить что-то, первая мысль должна быть - придумать инвариант. Какое-то свойство, которое не меняется при применении операции. С опытом наберетесь идей для инвариантов. Тут сразу приходит в голову такой: Обозначим цвета цифрами от 0 до 2. Тогда при любом перекрашивании сумма всех чисел по модулю 3 не меняется. Если столбы одинаковые - сами числа не меняются, если 01 перекрасить в 22, 02 в 11 и 12 в 00, то сумма остается с таким же остатком от деления на 3.

Отсюда можно сразу сделать вывод, что при N делящемся на 3 ответа нет. Потому что в конце мы должны получить все цвета одинаковые, а значит сумма будет 0, N или 2N - делится на N. Раз N делится на 3, то и итоговая сумма дает остаток 0 (по модулю 3). Но изначальная раскраска может иметь любой остаток (например, 00..0001). Значит решения для таких N нет.

Далее, можно легко придумать, как "удваивать" решение. Пусть мы умеем получать какой-то N, то можно получить алгоритм для 2N. Сначала перекрашиваем первую половину по известному плану. Потом вторую половину. Потом попарно столбы из двух половин. Надеюсь, очевидно, почему это работает?

Так можно получить ответ для 2,4,8,16, но этого мало.

Следующая мысль, как можно построить универсальный план покраски - это воспользоваться тем, что если мы сделаем все столбы одинаковыми, то все последующие действия ничего не испортят. Т.е. можно взять конкретную раскраску столбов, составить план для нее. Потом взять следующий вариант входных данных, прогнать его через уже составленный план. Если результат не одноцветный - дополнить план так чтобы раскрасить все в один цвет и для этого варианта изначальной раскраски. Повторить со всеми возможными входными данными. Использовать эту идею для всех вариантов N раскрасок слишком медленно (их же 3^N). Вернемся к ней попозже.

Следующая идея должна быть - раз для существования решения важно неделимость на 3, то возможно мы сможем к группе одинаковых столбов добавить 3 столба?

После разбора нескольких случаев на бумаге я понял, что надо отдельно рассматривать случаи N%3=1 и N%3=2.

Рассмотрим первый случай. У нас есть 3k столбов цвета А, и в конце еще 4 столба - AXYC (один из N и 3 новых). Задача - получить в конце 4 одинаковых цвета. У нас уже есть решение для N=4 в примере. Просто примените его к 4-м последним столбцам. Теперь у нас есть ...AAAZZZZ. Если A=Z, то все наши операции ничего не сделают. Рассмотрим только случай A!=Z. Красим A+Z, получаем AAYYZ..Z на конце Красим 2 раза A+Y. Т.е. за 3 операции мы перекрасили 3 последние A в Z. Повторяем операцию, пока все A не перекрасим (их же 3k, напоминаю).

Теперь случай N=3k+2. У нас есть 3k A, и в конце AAXYC. Если у вас есть решение для 5, то получаете на конце 5 Z и аналогично предыдущему случаю перекрашиваете 3 последних A в цвет последних столбов.

Т.е. отдельно рассматриваете случай разных остатков N%3. Потом решаете задачу для N=4 или 5 первых столбцов, потом добавляете по 3 столба: решаете задачу для 4/5 последних столбов и итеративно перекрашиваете по 3 столба из предыдущих.

Это решение потребует максимум N/3*(F(5)+N) шагов, где F(5) - сколько нужно операций для решения N=5.

Теперь решение для N=5. Тут и надо будет воспользоваться наблюдением о дополнении плана для разных входных данных. Вот есть 5 столбов. Покрасим 1+2 и 3+4. Теперь у нас есть AABBC. Возможно какие-то цвета одинаковые. Но сначала допустим, что они все три разные. Красим попарно A+B(1+3 и 2+4). Все. Но что, если B=C, B!=A? У нас было AABBB. Мы покрасили 1+3 и 2+4 - получили ССССA. Красим 4+5 - CCCBB. Теперь, как раньше, перекрасим 3С в B: 3+4 (CCAAB), 1+3(BCBAB), 2+4 (BBBBB).
Теперь надо рассмотреть случай B=A, C!=A: AAAAC. Надо аккуратно повторить все операции выше - получим BBBBB. План для этого случая работает, ничего дописывать не надо. Остался случай A=C, C!=B. Т.е. дано AABBA. Применяем шаги выше и получим (перепроверьте!) AAAAA.

Т.е весь план для N=5 1+2, 3+4, 1+3, 2+4, 4+5, 3+4, 1+3, 2+4.

Вот и все решение. Привел целиком, чтобы вы идей набрались и могли понять как к нему можно прийти.

Его можно соптимизировать по количеству операций. В начале я привел простой вариант удвоения. который быстро получает план для степеней двойки. Ниже я привел как имея 2 группы одноцветных столбов, если одна группа состоит из троек, перекрасить все в один цвет. Воспользуемся этими двумя приемами.

Возьмите максимальную степень двойки, помещающуюся в N. Пусть это k (2k > N, k <= N). Примените план для первых k. потом для последних k. Итого вы получите N-k столбов одного цвета и k столбов (возможно) другого цвета в конце. Если N-k делиться на 3 то, по известному плану "перекрашивания по тройкам" перекрасьте первые N-k в цвет последних k. Если же N-k не делиться на 3, то покрасьте попарно столбы цвета первых N-k и цвета вторых N-k. Потом останутся какие-то столбы в конце другого цвета, но их количество точно будет делиться на 3 (доказательство этого факта придумайте сами. Рассмотрите какие могут быть остатки от деления на 3 у k и N-k). Раз у нас группа другого цвета состоящая из троек, то мы умеем ее перекрашивать.

Этот вариант будет требовать не квадратичное, а O(n log n) количество операций.
Ответ написан
Комментировать
Пригласить эксперта
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы