| Show all threads Hide all threads Show all messages Hide all messages |
| To Authors: Solution check program | Sirko | 1541. Chase | 24 Apr 2017 23:10 | 2 |
Have you guys thought about exact, long arithmetic check? |
| Can someone give me an answer for this test? | Ostap Korkuna (Lviv NU) | 1541. Chase | 20 Apr 2017 21:42 | 7 |
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! what is the answer for test
2 1
???? 38 41 also leads to
9
1230 615 41 30 15 10 6 5 3
Edited by author 11.02.2016 18:00 |
| is there a solution? | RAVEman | 1541. Chase | 24 Aug 2011 02:48 | 5 |
is there any solution for this problem that is not based on the exhaustive search? 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. 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 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 |
| To judjes: very funny! | bsu.mmf.team | 1541. Chase | 21 Mar 2010 12:34 | 2 |
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? Your tests were added, and problem was rejudged. Thank you. |
| Could V[i] be negative? | bsu.mmf.team | 1541. Chase | 6 Mar 2010 14:05 | 1 |
Edited by author 14.05.2010 21:41 |
| Simple recursive algo get AC. Good Luck! | Victor Barinov (TNU) | 1541. Chase | 11 May 2009 17:29 | 11 |
Yes, my stupid bruteforce algo got AC within 0.2 secs. Funny! 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 Mine is O(C(K,5000)) Yes it's just ~10^50 operations It's easy for Timus supercomputers:) But I don't know all details but shortly
It can be said that we haven't an algorithm
but have Ac-prog. 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:30This is fine information.
Or the problem is not NP type and therefore
must be understood and solved 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 Also solved ... 0.001 Brute force ...
Very strange problem.
i don't like such problems ... AC in Java 0.093.
Complexity O(n*m*20). |
| Where are answer is "No solution"? | Cat36 | 1541. Chase | 17 Dec 2008 03:35 | 4 |
I want to use greedy algorithm with particular cases
Number of particular cases is no more when 141 :) The answer always exists. Greedy will not work - use brute-force AC 0.015 without brute-force
one random value + greedy |
| 2<m/n<3 | Mehas (PSU #1) | 1541. Chase | 15 Jul 2008 02:18 | 5 |
2<m/n<3 Mehas (PSU #1) 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? Hm... Now the main problem is constraint of v<100000... Hm... Now the main problem is constraint of v<100000... 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... 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) |
| Hm... Limitation 10^5 is too big | Burunduk1 | 1541. Chase | 11 Apr 2007 12:11 | 3 |
I've just accepted solution, which searches for velocities <= 350. =) With limitations less than 3000 and more than 10000 my stupid BF got TLE. With 5000 I've ACed this problem :) |
| Can you verify the test data or the special judge? | Yiming Li | 1541. Chase | 3 Mar 2007 16:32 | 1 |
I think at least one of them is incorrect. |
