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.

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.

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.

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

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

Эта задача имеет математическое решение. Нам задан граф на N вершинах, причём степень каждой вершины p (нужно самому понять, откуда берётся p). Требуется покрасить вершины так, чтобы смежные имели разный цвет. Утверждение: покраска возможна <=> цветов >=p+1. Необходимость очевидна. А достаточность реализуется по индукции: пусть мы покрасили k<N вершин, так что смежные имеют разный цвет. Возьмём не покрашенную вершину. Её степень <=p, а цветов >=p+1.Тогда покрасим её в любой из оставшихся цветов.

There is a constructive approach that works in O(n). Hint: LCM(1, 2, ..., 13) > 3*10^5.