| ENG RUS | Timus Online Judge |
Discussion of Problem 1798. Fire Circle. Version 2Zergatul This task is driving me crazy [1] // Problem 1798. Fire Circle. Version 2 7 Apr 2021 02:32 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 Zergatul Re: This task is driving me crazy // Problem 1798. Fire Circle. Version 2 8 Apr 2021 01:51 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 [ЛЕСТЕХ] UstinovG`~ The problem is overrated // Problem 1798. Fire Circle. Version 2 5 Apr 2021 11:54 My algorithm is O(R) and i have AC Shen Yang No subject [4] // Problem 1798. Fire Circle. Version 2 19 Sep 2018 18:22 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)) Irakli Khomeriki Re: No subject [3] // Problem 1798. Fire Circle. Version 2 25 Sep 2018 20:54 what do you mean by cut huperbola curve? Shen Yang Re: No subject [2] // Problem 1798. Fire Circle. Version 2 25 Sep 2018 21:33 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 Irakli Khomeriki Re: No subject [1] // Problem 1798. Fire Circle. Version 2 26 Sep 2018 19:41 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. Shen Yang Re: No subject // Problem 1798. Fire Circle. Version 2 26 Sep 2018 20:02 your computer is too strong, ural oj O(1e9) can't fit into 2 sec Edited by author 26.09.2018 20:03 Irakli Khomeriki my solution runs under 1 sec for 10^9 on my pc and still TLE17 here :( // Problem 1798. Fire Circle. Version 2 24 Sep 2018 13:45 Jorjia A HINT [3] // Problem 1798. Fire Circle. Version 2 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). Shen Yang Re: A HINT [2] // Problem 1798. Fire Circle. Version 2 13 Apr 2018 13:26 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 Shen Yang Re: A HINT // Problem 1798. Fire Circle. Version 2 13 Apr 2018 14:08 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 Shen Yang Re: A HINT // Problem 1798. Fire Circle. Version 2 13 Apr 2018 14:08 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 rip&pvs 2ADMINS [1] // Problem 1798. Fire Circle. Version 2 9 Aug 2015 02:08 "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 Sandro (USU) Re: 2ADMINS // Problem 1798. Fire Circle. Version 2 9 Aug 2015 22:14 Statement is fixed, thank you. Sandro (USU) New problem 1798 "Fire Circle. Version 2" was added! [1] // Problem 1798. Fire Circle. Version 2 2 Aug 2015 11:34 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 MVM Re: New problem 1798 "Fire Circle. Version 2" was added! // Problem 1798. Fire Circle. Version 2 6 Aug 2015 05:45 "Площадъю миллион квадратных километров" За пределами зала плит нет?
|