Surgeon_of_Hell's blog

Facing TLE in a problem
By Surgeon_of_Hell, history, 22 hours ago, In English

Problem Statement: Given an integer $$$ n $$$, find the sum of $$$ f(k) $$$, where $$$ f(k) = 1 + 2 + 3 + \ldots + k $$$ and $$$ 1 <= k <= n $$$ . Output the result modulo $$$ 10^9 + 7 $$$. max(n) = $$$10^9$$$.

MY approach: Firstly , very very sorry for my poor english. My approach was to use the formula n(n + 1)/2 in a loop. But I am getting TLE every time. But I don't know how to fix it any further. I first I used 2 nested loops and then only one loop. But not working.

Can some generous person help me?

  • Vote: I like it
  • +19
  • Vote: I do not like it

»
21 hour(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by Surgeon_of_Hell (previous revision, new revision, compare).

→ Reply
»
21 hour(s) ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

Ok so we're summing this

$$$\displaystyle \sum_{i=1}^n \sum_{j=1}^{i} j$$$

which is

$$$\displaystyle \sum_{i=1}^n \frac{i(i+1)}{2}$$$
$$$\displaystyle = \frac{1}{2} \left ( \sum_{i=1}^n i^2+i \right ) $$$

The sum of

$$$\displaystyle \sum_{i=1}^n i^2=\frac{n(n+1)(2n+1)}{6}$$$

and

$$$\displaystyle \sum_{i=1}^n i=\frac{n(n+1)}{2}$$$

so now the sum is

$$$\displaystyle \frac{1}{2} \left ( \frac{n(n+1)(2n+1)}{6} + \frac{n(n+1)}{2} \right ) $$$

this runs in constant time

some stress test for $k=100$

stress-test
→ Reply
  • »
    »
    21 hour(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    What is stress test budyy? (exp: haha) Just kidding...

    → Reply
    • »
      »
      »
      21 hour(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      It's how you check if your optimized solution works as the naive one

      like proof by AC

      → Reply
»
21 hour(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Basically, there is a $$$O(1)$$$ solution for this problem. You can convert the problem into the following equation: 1 + (1 + 2) + (1 + 2 + 3) + ... + (1 + 2 + ... + n). Then, solve the equation like this:

$$$ \displaystyle 1 + (1 + 2) + (1 + 2 + 3) + \dots + (1 + 2 + \dots + n) $$$
$$$ \displaystyle = \sum_{i=1}^{n} \sum_{j=1}^{i} j $$$
$$$ \displaystyle = \sum_{i=1}^{n} \frac{i^2 + i}{2} $$$
$$$ \displaystyle = \frac{1}{2} \left( \sum_{i=1}^{n} i^2 + \sum_{i=1}^{n} i \right) $$$
$$$ \displaystyle = \frac{(n^2 + n)(2n + 1)}{12} + \frac{n^2 + n}{4} $$$

And lastly, you must use long long data type instead of int because there are many $$$n^2$$$ terms in the resultant equation.

→ Reply
»
21 hour(s) ago, # |
  Vote: I like it +32 Vote: I do not like it

https://usaco.guide/adv/line-container?lang=cpp#half-plane-intersection it should become clear after this.

→ Reply