ENG  RUS Timus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

## Обсуждение задачи 1832. Шоу «Ариран»

Hint
Послано 198808xc 5 сен 2011 12:33
I have got AC with bruteforce. You need only to state larger memory for stack (if you use stack), and perform some little optimization when enumerating.

PS: Solution always exists. For n <= 300000, the task could be finished with only 14 (or 15?) colors.

BTW: If anyone could provide me a method of construction, I would be very glad to see it. Please paste it here, and let others see.
Re: Hint
Послано bsu.mmf.team 7 сен 2011 03:26
What do you mean under "the method of construction"? For example I solved it using greedy algo. And, as I know, it's very hard to prove that for some fixed n solution doesn't exist. Therefore jury checked a possibility of coloring artists for all n <= MAXN with a help of their own method (maybe, also greedy). According to this time limit and MAXN for this problem were selected.
Re: Hint
Послано 198808xc 8 сен 2011 21:29
What I said under "the method of construction" means that you have such a method, that you could use some formula or equation to calculate elements at each place DIRECTLY.

More precisely, you have a formula for a[n]:
a[0] = ...
a[1] = ...
...
a[n - 1] = ...
That is "the method of construction". Many problems in TIMUS could be solved with this kind of method, and I wonder whether this problem could be done too.
Re: Hint
Послано bsu.mmf.team 8 сен 2011 21:58
Hmm, it's very interesting. But I don't know such method. And I guess, such solution doesn't exist for every natural N.

Edited by author 08.09.2011 22:00

Edited by author 09.09.2011 11:11
Re: Hint
Послано luckysundog 21 ноя 2011 12:52
Look at author rating for this problem. There are 0.031 and even 0.015 solutions. I don't think they did bruteforce too.

Edited by author 24.11.2011 00:33
Re: Hint
Послано Felix_Mate 14 янв 2017 00:04
Эта задача имеет математическое решение. Нам задан граф на N вершинах, причём степень каждой вершины p (нужно самому понять, откуда берётся p). Требуется покрасить вершины так, чтобы смежные имели разный цвет. Утверждение: покраска возможна <=> цветов >=p+1. Необходимость очевидна. А достаточность реализуется по индукции: пусть мы покрасили k<N вершин, так что смежные имеют разный цвет. Возьмём не покрашенную вершину. Её степень <=p, а цветов >=p+1.Тогда покрасим её в любой из оставшихся цветов.
Re: Hint
Послано Yury_Semenov 11 сен 2019 11:49
There is a constructive approach that works in O(n). Hint: LCM(1, 2, ..., 13) > 3*10^5.