ENG  RUS Timus Online Judge
Online Judge
Problems
Authors
Online contests
Site news
Webboard
Problem set
Submit solution
Judge status
Guide
Register
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

## Discussion of Problem 1832. Arirang Show

Hint
Posted by 198808xc 5 Sep 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
Posted by bsu.mmf.team 7 Sep 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
Posted by 198808xc 8 Sep 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
Posted by bsu.mmf.team 8 Sep 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
Posted by luckysundog 21 Nov 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
Posted by Felix_Mate 14 Jan 2017 00:04
Эта задача имеет математическое решение. Нам задан граф на N вершинах, причём степень каждой вершины p (нужно самому понять, откуда берётся p). Требуется покрасить вершины так, чтобы смежные имели разный цвет. Утверждение: покраска возможна <=> цветов >=p+1. Необходимость очевидна. А достаточность реализуется по индукции: пусть мы покрасили k<N вершин, так что смежные имеют разный цвет. Возьмём не покрашенную вершину. Её степень <=p, а цветов >=p+1.Тогда покрасим её в любой из оставшихся цветов.
Re: Hint
Posted by Yury_Semenov 11 Sep 2019 11:49
There is a constructive approach that works in O(n). Hint: LCM(1, 2, ..., 13) > 3*10^5.