CALCULUS - Editorial

PROBLEM LINK:

Practice
Division 1

Author: Ildar Gainullin

Tester: Alexander Morozov

Editorialist: Srikkanth

DIFFICULTY:

Medium

PREREQUISITES:

Parseval’s theorem, Fourier transforms, Definite integrals

PROBLEM:

Evaluate

\int\limits_{0}^{\infty} \frac{e^{2 \pi x}-1}{e^{2 \pi x}+1}(\frac{1}{x}-\frac{x}{N^2+x^2}) dx

EXPLANATION:

Let the answer be I_N, we can rewrite the integral as

I_N = \int\limits_{0}^{\infty} \tanh(\pi x)(\frac{1}{x}-\frac{x}{N^2+x^2}) dx

We will use Parseval’s theorem for convolution which is :

\int\limits_{0}^{\infty} f(x) g(x) dx = \frac{2}{\pi}\int\limits_{0}^{\infty} F_c(\omega) G_c(\omega) d\omega

where

F_c(\omega) = \int\limits_{0}^{\infty} f(x) sin(\omega x) dx

F_c(\omega) is known as the sine fourier transform of f(x)

Let’s take f(x) = \frac{e^{2 \pi x} - 1}{e^{2 \pi x} + 1} = \tanh(\pi x) and

g(x) = \frac{1}{x} - \frac{x}{N^2 + x^2} and apply Parseval’s theorem.

The fourier transforms for the functions are \mathcal{F}_c\{\tanh(\pi x)\} = \frac{1}{2\sinh(\frac{\omega}{2})} = \frac{1}{e^{\frac{\omega}{2}} - e^{-\frac{\omega}{2}}}

\mathcal{F}_c\{\frac{x}{N^2 + x^2}\} = \frac{\pi}{2} \text{sgn} (\omega) e^{-N | \omega |}

\mathcal{F}_c\{\frac{1}{x}\} = \frac{\pi}{2} \text{sgn}(w)

Substituting we get

I_N = \frac{2}{\pi}\int\limits_{0}^{\infty} \frac{1}{e^{\frac{\omega}{2}} - e^{-\frac{\omega}{2}}} \frac{\pi}{2} \text{sgn} (\omega) (1 - e^{-N | \omega |}) d\omega

\text{sgn}(w) = 1, |\omega| = \omega for the values of \omega in the limits and multiplying the numerator and denominator by e^{-\frac{\omega}{2}} we get,

I_N = \int\limits_{0}^{\infty} \frac{1 - e^{-N \omega}}{1 - e^{-\frac{\omega}{2}}} e^{-\frac{\omega}{2}}d \omega

Using the substitution t = e^{-\frac{\omega}{2}} we get

I_N = 2\int\limits_{0}^{1} \frac{1-t^{2N}}{1-t^2} dt

Clearly I_1 = 2 and

I_N - I_{N-1} = 2 \int_{0}^{1}\frac{t^{2N-2}-t^{2N}}{1-t^2} dt

= 2 \int_{0}^{1}t^{2N-2} dt = \frac{2}{2N-1}

Summing up we get

\sum\limits_{n=2}^{N}I_n - I_{n-1} = \frac{2}{3} + \frac{2}{5} + \ldots \frac{2}{2N-1} = I_N - I_1

\implies I_N = \frac{2}{1} + \frac{2}{3} + \ldots \frac{2}{2N-1}

We can obtain the answer by calculating the fractions I_n for all n by maintaining the numerator and denominator as a_n, b_n for each n from 1 to N.

Specifically if I_n = \frac{a_n}{b_n} then

\frac{a_n}{b_n} = \frac{a_{n-1}}{b_{n-1}} + \frac{1}{2N-1}

\implies a_n = a_{n-1} * (2n-1) + b_{n-1}

b_n = b_{n-1} * (2n-1)

COMPLEXITY:

TIME: \mathcal{O}(N)

SPACE: \mathcal{O}(1)

SOLUTIONS:

Setter's Solution

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

#ifdef iq

  mt19937 rnd(228);

#else

  mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());

#endif

const int mod = 998244353;

void add(int &a, int b) {

  a += b;

  if (a >= mod) a -= mod;

  if (a < 0) a += mod;

}

int mul(int a, int b) {

  return (a * (ll) b) % mod;

}

int pw(int a, int n) {

  int ret = 1;

  while (n) {

    if (n % 2 == 0) {

      a = mul(a, a);

      n /= 2;

    } else {

      ret = mul(ret, a);

      n--;

    }

  }

  return ret;

}

int inv(int x) {

  return pw(x, mod - 2);

}

int main() {

#ifdef iq

  freopen("a.in", "r", stdin);

#endif

  ios::sync_with_stdio(0);

  cin.tie(0);

  int n;

  cin >> n;

  int ans = 0;

  for (int i = 1; i <= 2 * n; i++) {

    int x = mul(inv(i), 1 + (i > n));

    add(ans, x);

  }

  cout << ans << '\n';

}

VIDEO EDITORIAL:

2 Likes

Why very very weak test cases :frowning_face: only for 4 different N values ?

9 Likes

they didn’t know about the sniper

38 Likes

even 2 and 3 were known already

People who print just 4 values -

https://bit.ly/3oP3kxR

10 Likes

I used sniper

2 Likes

Reading the comments it’s obvious the tests were extremely weak. Can the problem authors elaborate why it was challenging to put some random test-cases? I mean you only need to put N as part of the test, not exactly hardest to generate. I am guessing they thought “if you can solve it for N=10^6, you must have solved it for all”, but there are some tricks that allow you to guess what the test case was, if they were only few, and than offline find some solution one way or another (you can make repeated submissions and binary-search on size of N).

P.S. I am not one of those people who did it, I figured out the formula for N.

6 Likes

this is not fair i have gone through the solutions of many participants they were only printing ans for four corresponding testcases and they are only printing ans not any sort of calculation this is not fair this is clear cheating codechef should do something about this yesterday only 400 participants were getting ac in this question and today above 500 this is clear cheating and these things are ruining the objective of these long challenges codechef should also consider the timing of submission for final score and rank and should change rating according to that

9 Likes

true, just add more TC and re-run evaluation. The question constraints were for x < N < y, so the submitted code should work for all.

3 Likes

Agreed,They should re-evaluate all submissions :grinning:

6 Likes

agree

1 Like

Where can i practice some problems similar to this? (not necessarily programming problems ).

I really want to know how did most people solve this question? Did they use a software like WolframAlpha to solve the integral or did they really solve it.
Finally, I guess most people binary searched to find out the input.

From WolformAlpha I found answer for N=2, 3
so now a0=0, a1=2, a2=8/3, a3= 46/15
After some trail and guessing, I got the formula
aN = 2(1/1+1/3+1/5+…+1/(2*N-1)

I don’t know if it was a good experience.

7 Likes

How to use these? As they just give the approx values in decimal. How you found the generalised result?

Same

you should checkout https://projecteuler.net/

What is wolformalpha??

What was your approach??

We can also use complex analysis: Find the residues at the poles of a contour integral, and in the limit, show that the contour integral equals the value of the given integral.

1 Like