| ENG RUS | Timus Online Judge |
Discussion of Problem 1541. ChaseSirko To Authors: Solution check program [1] // Problem 1541. Chase 21 Apr 2017 20:58 Have you guys thought about exact, long arithmetic check? Sandro (USU) Re: To Authors: Solution check program // Problem 1541. Chase 24 Apr 2017 23:10 Sure :) Ostap Korkuna (Lviv NU) Can someone give me an answer for this test? [6] // Problem 1541. Chase 3 Mar 2007 18:33 38 41 ??? Yermak Re: Can someone give me an answer for this test? [2] // Problem 1541. Chase 4 Mar 2007 14:19 5 16236 99 6 4 2 It's a really good test! My program answers that there is no solution! But I found it! Amazingly! TEST Re: Can someone give me an answer for this test? [1] // Problem 1541. Chase 8 Mar 2007 03:00 what is the answer for test 2 1 ???? [SPbSU ITMO] WiNGeR Re: Can someone give me an answer for this test? // Problem 1541. Chase 8 Mar 2007 06:53 4 6 3 2 1 Denis Koshman Re: Can someone give me an answer for this test? // Problem 1541. Chase 15 Jul 2008 02:23 38 41 also leads to 9 1230 615 41 30 15 10 6 5 3 yeziqing10 Re: Can someone give me an answer for this test? // Problem 1541. Chase 11 Feb 2016 14:51 Edited by author 11.02.2016 18:00 Sirko Re: Can someone give me an answer for this test? // Problem 1541. Chase 20 Apr 2017 21:42 Or: 5 1804 492 11 3 2 RAVEman is there a solution? [4] // Problem 1541. Chase 8 Mar 2007 04:42 is there any solution for this problem that is not based on the exhaustive search? MikleB Re: is there a solution? // Problem 1541. Chase 14 Mar 2007 01:35 Google aliquot fractions Denis Koshman Re: is there a solution? // Problem 1541. Chase 15 Jul 2008 02:21 Yes, there is. I recursively try all denominators <= 100000 walking on primes - this way I automatically get all of its divisors at no cost and then DP in order to sum up to nominator using <20 of denoninator's divisors. Interestingly, the bigger the limit, the faster it performs. svr Re: is there a solution? [1] // Problem 1541. Chase 6 Jan 2011 08:49 Next reasoning should work: if (1/(n+1)<A<1/n => A=1/(n+1)+B, where B<1/(n*(n+1)) and cannot contain 1/(n+1) again Thus 1/v1,1/v2,... is basis that converges to A very quickly A is rational then sequence must be finite bsu.mmf.team Re: is there a solution? // Problem 1541. Chase 24 Aug 2011 02:48 It's true, but there exists the limit for a denominator of fractions in this problem. I tried this algo in my first solution, and got WA#3. Edited by author 01.12.2015 19:01 bsu.mmf.team To judjes: very funny! [1] // Problem 1541. Chase 6 Mar 2010 16:38 My AC program runs about 10 seconds on following tests; 4 41 4 49 (on this test it works more, that 1 minute!!!) 17 43 19 49 41 43 50 41 50 43 I can write about 10 more tests, but, I think, it's enough:) Could you add some of these tests? Sandro (USU) Re: To judjes: very funny! // Problem 1541. Chase 21 Mar 2010 12:34 Your tests were added, and problem was rejudged. Thank you. bsu.mmf.team Could V[i] be negative? // Problem 1541. Chase 6 Mar 2010 14:05 Edited by author 14.05.2010 21:41 Victor Barinov (TNU) Simple recursive algo get AC. Good Luck! [10] // Problem 1541. Chase 4 Mar 2007 19:41 Vedernikoff Sergey Re: Simple recursive algo get AC. Good Luck! [9] // Problem 1541. Chase 6 Mar 2007 11:03 Yes, my stupid bruteforce algo got AC within 0.2 secs. Funny! svr Re: Simple recursive algo get AC. Good Luck! [8] // Problem 1541. Chase 6 Mar 2007 11:16 In this situaton great interst has a proven right algorithm with garantee result on all posiible tests in described ranges For me it much more valuable than fact of AC P.S. What comlexity of brute force? ~(100000)^K*K? Edited by author 06.03.2007 11:46 Edited by author 06.03.2007 11:46 Edited by author 06.03.2007 11:47 Vedernikoff Sergey Re: Simple recursive algo get AC. Good Luck! [7] // Problem 1541. Chase 6 Mar 2007 19:54 Mine is O(C(K,5000)) KIRILL(ArcSTU) Re: Simple recursive algo get AC. Good Luck! [6] // Problem 1541. Chase 6 Mar 2007 20:25 Vedernikoff Sergey wrote 6 March 2007 19:54 Mine is O(C(K,5000)) Yes it's just ~10^50 operations It's easy for Timus supercomputers:) svr Re: Simple recursive algo get AC. Good Luck! // Problem 1541. Chase 6 Mar 2007 20:38 But I don't know all details but shortly It can be said that we haven't an algorithm but have Ac-prog. Vedernikoff Sergey Re: Simple recursive algo get AC. Good Luck! [4] // Problem 1541. Chase 7 Mar 2007 09:30 KIRILL(ArcSTU) wrote 6 March 2007 20:25 Yes it's just ~10^50 operations It's easy for Timus supercomputers:) Quicksort time estimate is also O(N^2), but really - O(NlogN). My algo with asympthotic time O(C(K,5000)) in worst case makes about 10^7 operations, that is acceptable. Edited by author 07.03.2007 09:30 svr Re: Simple recursive algo get AC. Good Luck! [3] // Problem 1541. Chase 7 Mar 2007 09:39 This is fine information. Or the problem is not NP type and therefore must be understood and solved svr Re: Simple recursive algo get AC. Good Luck! [2] // Problem 1541. Chase 8 Jul 2007 15:48 Also solved now. I used double for fractions ,eps=1e-11 for comparisons(1e-10 gives WA),prepocessing for numbers 1/i and it's sums, stac instead of recursion in full search, NN=5000 as upper bound for Vi(value NN=350 couldn't verify because of TLE) and finally had 0,593c. AC. I think that times 0.001 adjust to tests list only. Edited by author 08.07.2007 15:51 Chmel_Tolstiy Re: Simple recursive algo get AC. Good Luck! // Problem 1541. Chase 2 Mar 2008 03:15 Also solved ... 0.001 Brute force ... Very strange problem. i don't like such problems ... Alex Tolstov (Vologda STU) Re: Simple recursive algo get AC. Good Luck! // Problem 1541. Chase 11 May 2009 17:29 AC in Java 0.093. Complexity O(n*m*20). Cat36 Where are answer is "No solution"? [3] // Problem 1541. Chase 31 Oct 2008 03:49 I want to use greedy algorithm with particular cases Number of particular cases is no more when 141 :) Vedernikoff Sergey (HSE: EconomicsForever!) Re: Where are answer is "No solution"? [2] // Problem 1541. Chase 31 Oct 2008 12:55 The answer always exists. Greedy will not work - use brute-force Cat36 Re: Where are answer is "No solution"? // Problem 1541. Chase 31 Oct 2008 21:26 Thanks! Cat36 Re: Where are answer is "No solution"? // Problem 1541. Chase 17 Dec 2008 03:35 AC 0.015 without brute-force one random value + greedy Mehas (PSU #1) 2<m/n<3 [4] // Problem 1541. Chase 5 Sep 2007 00:04 I got AC on this problem with normal solution, when 0<m/n<2, and with search when 2<=m/n<=3. Is there some smart solution in that case? Mehas (PSU #1) Re: 2<m/n<3 // Problem 1541. Chase 5 Sep 2007 00:50 Hm... Now the main problem is constraint of v<100000... Mehas (PSU #1) Re: 2<m/n<3 [2] // Problem 1541. Chase 5 Sep 2007 00:50 Hm... Now the main problem is constraint of v<100000... Vedernikoff Sergey Re: 2<m/n<3 [1] // Problem 1541. Chase 5 Sep 2007 01:06 My brute-force solution process any test with constraint v < 5000. So, in you algo you can also assume that v <= 5000. Amazingly, but this will speed up your algo dramatically... Denis Koshman Re: 2<m/n<3 // Problem 1541. Chase 15 Jul 2008 02:18 In case of my algo decreasing the limit slows things down (fair AC w/o tables as it meets TL for every pair or M/N) Burunduk1 Hm... Limitation 10^5 is too big [2] // Problem 1541. Chase 4 Apr 2007 00:57 I've just accepted solution, which searches for velocities <= 350. =) Sandro (USU) Good ;) (-) [1] // Problem 1541. Chase 4 Apr 2007 01:43 Vedernikoff Sergey Re: Good ;) (-) // Problem 1541. Chase 11 Apr 2007 12:11 With limitations less than 3000 and more than 10000 my stupid BF got TLE. With 5000 I've ACed this problem :) Yiming Li Can you verify the test data or the special judge? // Problem 1541. Chase 3 Mar 2007 16:32 I think at least one of them is incorrect.
|