|
|
| Показать все ветки Спрятать все ветки Показать все сообщения Спрятать все сообщения | | Hint | 198808xc | 1832. Шоу «Ариран» | 11 сен 2019 11:49 | 7 | 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. 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. | | AC | JAMSHID AKHMEDOV | 1832. Шоу «Ариран» | 31 янв 2013 21:46 | 1 | AC JAMSHID AKHMEDOV 31 янв 2013 21:46 /*
* Created by SharpDevelop.
* User: Жамшидбек
* Date: 31.01.2013
* Time: 20:02
*
* To change this template use Tools | Options | Coding | Edit Standard Headers.
*/
using namespace System;
int main(array<System::String ^> ^args)
{
Console::WriteLine(L"Hello World");
return 0;
} | | How to get 0.031 ? | luckysundog | 1832. Шоу «Ариран» | 24 ноя 2011 00:33 | 1 | |
|
|
|
