ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

Обсуждение задачи 1798. Огненный круг. Версия 2

No subject
Послано Shen Yang 19 сен 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))
Re: No subject
Послано Irakli Khomeriki 25 сен 2018 20:54
what do you mean by cut huperbola curve?
Re: No subject
Послано Shen Yang 25 сен 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
Re: No subject
Послано Irakli Khomeriki 26 сен 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.
Re: No subject
Послано Shen Yang 26 сен 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