| ENG RUS | Timus Online Judge |
Discussion of Problem 1832. Arirang Show198808xc Hint [6] // Problem 1832. Arirang Show 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. bsu.mmf.team Re: Hint [3] // Problem 1832. Arirang Show 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. 198808xc Re: Hint [2] // Problem 1832. Arirang Show 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. bsu.mmf.team Re: Hint [1] // Problem 1832. Arirang Show 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 luckysundog Re: Hint // Problem 1832. Arirang Show 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 Felix_Mate Re: Hint [1] // Problem 1832. Arirang Show 14 Jan 2017 00:04 Эта задача имеет математическое решение. Нам задан граф на N вершинах, причём степень каждой вершины p (нужно самому понять, откуда берётся p). Требуется покрасить вершины так, чтобы смежные имели разный цвет. Утверждение: покраска возможна <=> цветов >=p+1. Необходимость очевидна. А достаточность реализуется по индукции: пусть мы покрасили k<N вершин, так что смежные имеют разный цвет. Возьмём не покрашенную вершину. Её степень <=p, а цветов >=p+1.Тогда покрасим её в любой из оставшихся цветов. Yury_Semenov Re: Hint // Problem 1832. Arirang Show 11 Sep 2019 11:49 There is a constructive approach that works in O(n). Hint: LCM(1, 2, ..., 13) > 3*10^5. JAMSHID AKHMEDOV AC // Problem 1832. Arirang Show 31 Jan 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; } luckysundog How to get 0.031 ? // Problem 1832. Arirang Show 24 Nov 2011 00:33 subj
|