|
|
| Show all threads Hide all threads Show all messages Hide all messages | | This task is driving me crazy | Zergatul | 1798. Fire Circle. Version 2 | 8 Apr 2021 01:51 | 2 | I've implemented several approaches, ones calculate 1/4 of circle, another ones calculate 1/8 of circle. All of them works fine for R < 60000000. With R > 60millions there is a chance (and it increases with bigger R) 2 approaches can give different results. They use the same calculations (sqrt, ceiling). I also tried to implement 1/8 without float point numbers, by integers only. Same result with same difference. Maybe these "magic" numbers can help someone
r: 67250001 correct: 14208049816923164 diff: 12
r: 67250051 correct: 14208070944129524 diff: 4
r: 67250211 correct: 14208138551359320 diff: 4
r: 67250249 correct: 14208154608083608 diff: 8
r: 67250321 correct: 14208185031387396 diff: 16
r: 67250433 correct: 14208232356606236 diff: 4
r: 67250449 correct: 14208239117361224 diff: 4
r: 67250505 correct: 14208262780007696 diff: 4
r: 67250601 correct: 14208303344588340 diff: 8
r: 67250697 correct: 14208343909213316 diff: 4
r: 67250769 correct: 14208374332717888 diff: 4
r: 67250825 correct: 14208397995480888 diff: 4
r: 67250835 correct: 14208402220968636 diff: 4
r: 67251315 correct: 14208605045441340 diff: 8
r: 67251347 correct: 14208618567139620 diff: 12
r: 67251457 correct: 14208665047975948 diff: 4
Edited by author 07.04.2021 02:35 Forget about what I said earlier. It is always good idea to return to the problem with fresh mind :)
It turned out my correct solution was actually incorrect, and my incorrect solutions were correct.
If you are using sqrt and ceil, try to calculate ceil(sqrt(2 * 63611501 * 67250001 - 63611501 * 63611501)), and you will get wrong result
I was able to get AC C# solution with 467286474 int64 multiplications for R=10^9, no divisions, and no floating point usage.
Edited by author 08.04.2021 01:53
Edited by author 08.04.2021 01:53 | | The problem is overrated | [ЛЕСТЕХ] UstinovG`~ | 1798. Fire Circle. Version 2 | 5 Apr 2021 11:54 | 1 | My algorithm is O(R) and i have AC | | No subject | Shen Yang | 1798. Fire Circle. Version 2 | 26 Sep 2018 20:02 | 5 | the number of integer point inside circle is sigma(r*r/(4*i+1)-r*r/(4*i+3))
use stern borcot to cut hyperbola curve it can be done O(r^(2/3)) what do you mean by cut huperbola curve? maybe we can directly use stern borcot tree to cut circle I think it is faster...
basic idea is use line segment (x1,y1) --->(x2,y2） with slope -a/b(a>0,b>0) to cut quadric curve so that all of integer point strictly under this line segment is inside the quadric curve (x1,y1) and (x2,y2) is strictly outside the curve
if we know (x1,y1),(x2,y2) and -a/b we can find next -(a1/b1) a/b and a1/b1 is neibour in stern borcot tree .it can be proved there are O(n^1/3) state if the quadric curve is huperbola curve x*y==n
My solution convert this problem to compute simga(r*r/(4*i+1)-r*r/(4*i+3)) so it is huperbola curve (4*x+1)*y==r*r and (4*x+3)*y==r*r I have done twice ,so it is slow, dirctly cut circle only do once...
Edited by author 25.09.2018 21:34
Edited by author 25.09.2018 21:37 will try that for sure, I don't see any way I can speed up my current solutoin, I only need to calculate squares n-(n/sqrt(2)) times, and I do only +/- operations per iteration(no sqrt and multiplication/divisions). and for any n, it runs 0.75-0.8 sec on my pc, but I still get TLE18 here. your computer is too strong, ural oj O(1e9) can't fit into 2 sec
Edited by author 26.09.2018 20:03 | | my solution runs under 1 sec for 10^9 on my pc and still TLE17 here :( | Irakli Khomeriki | 1798. Fire Circle. Version 2 | 24 Sep 2018 13:45 | 1 | | | A HINT | Jorjia | 1798. Fire Circle. Version 2 | 13 Apr 2018 14:08 | 4 | A HINT Jorjia 18 Jan 2018 15:49 Solution is a sum( [ sqrt(2*i*R - i^2) ], i = 1,2,...,R), where [ x ] - round to up.
But, I always GOT TL on 17 test). if we notice f(i)==sqrt(2*i*R-i*i); and f(i+1)-f(i) always >=sqrt(R)
we can change to count howmany i satisfy c==sqrt(2*i*R-i*i) then answer+=ways*c
then this problem will be solved in O(sqrt(R))
thank you for your hint my fault but increment of f(i) seems to be monotonic decreasing and increment <=sqrt(2*r)
so we can binary search and divide them to sqrt(2*r) segment with same increment and add each segment using sum of arithmetic series my fault but increment of f(i) seems to be monotonic decreasing and increment <=sqrt(2*r)
so we can binary search and divide them to sqrt(2*r) segment with same increment and add each segment using sum of arithmetic series | | 2ADMINS | rip&pvs | 1798. Fire Circle. Version 2 | 9 Aug 2015 22:14 | 2 | "floor space one million square kilometers", so maximum number of slabs damaged by the fire is 1e12, but brute force solution (TL17) with ad-don "if(res>1e12)res=1e12" has WA14 Statement is fixed, thank you. | | New problem 1798 "Fire Circle. Version 2" was added! | Sandro (USU) | 1798. Fire Circle. Version 2 | 6 Aug 2015 05:45 | 2 | It is the problem 1490 "Fire Circle" with the limitation of R equal to 10^9 instead of 10^5. If you have an efficient solution of problem 1490, try to solve this one.
Edited by author 02.08.2015 11:36 "Площадъю миллион квадратных километров"
За пределами зала плит нет? |
|
|
|
