ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1621. Definite Integral

Two solutions
Posted by Teacher30 (Burunduk1) 27 Oct 2012 08:07
Solution #1: AC in 0.8 sec

Just calculate sum using Gauss's method.

Int[-1..1] f(x)dx ~= (5*f(-sqrt(3/5)) + 8*f(0) + 5*f(+sqrt(3/5))) / 9

Number of parts, N = (int)7e6

Length of part number i = (1e-4)*koef^i, where koef = 1 + x/N. Try some different x = 0.1 ... 10, and get AC =)

Solution #2: WA 11 on MSVC or AC on Java, Pascal, GNU C++

http://en.wikipedia.org/wiki/Residue_theorem says that we have to find all complex roots of the polynom.

I do not like exact formulas for degree 3 and 4.

There is numerical way to find all complex roots for any degree of polynom.

Just take point z = (0,0) and shift it to any direction in such a way that |P(z+shift)| < |P(z)|. Shift it while |P(z)| > eps. Now z is a root. This method works not only for polynoms, it works even for arbitrary "holomorphic function" (see Complex Analysis). Prove is smth like this http://en.wikipedia.org/wiki/Maximum_modulus_principle

The only thing that I need now -- to calculate f(z) for any complex z.

And using only "double" of Microsoft Visual C++ I can't. I have no enough precision and get WA 11 =(

Using BigDecimal (java), extended (pascal) or long double (GNU C/C++) this method gets AC (the task is from Petrozavodsk, so I have original tests).

P.S. 2 Admins: Ну сколько можно добавлять задачки с контестов, где у С++ программистов был под рукой long double, и это было важно. Даешь GNU C/C++!

Edited by author 27.10.2012 08:08
Re: Two solutions
Posted by Felix_Mate 12 Aug 2018 21:03
I found many other ways.
1)Monte Carlo - slow for this problem
2)Separation of real and complex roots. Can be used to solve this problem. Binary search for Re(z)=alfa, Re(z)=beta, Im(z)=gamma, Im(z)=delta
  Березин И.С., Жидков Н.П. Методы вычислений, Т.2. М.: ГИФМЛ, 1959.
3)Ferrari method.
  Куликов Л.Я. Алгебра и теория чисел
4)Barstow method. It's numeric iterative method.
  Саманчук_билеты_с_ответами.pdf
  Численные методы

I use combination from 3):
binary search for yo
then formulas

Edited by author 12.08.2018 21:04
Re: Two solutions
Posted by Gilles Deleuze 16 Feb 2020 23:45
https://en.wikipedia.org/wiki/Adaptive_quadrature

with Gaussian method to estimate value of definite integral:

approx_integrate(Func f, long double l, long double r) {
    long double A = sqrtl(3.0l/5.0l)/2, x1=0.5-A, x2 = 0.5+A;
    return (5*f(l*x1 + r*x2) + 8*f((l+r)/2) + 5*f(l*x2+r*x1))/18 * (r-l);
}

AC in 0.015.

That is, you don't even need to think to solve this problem.

Edited by author 16.02.2020 23:48