**Problem C.Longest Good Array**

- When I realized that the solution is related to (n)*(n+1)/2, I tried to find the value of n where the absolute diff between the range is d. Where d<=(n)*(n+1)/2 for some n.
- I decided to precompute all the values of (n)*(n+1)/2 from n=1,2,.....(till where?), I didn't know where I should stop, I thought as it is going to be n^2+n = 2x, then we should consider n till SQRT(1e9) but it gave WA on 1, then I tried 1e2, 1e4 it gave the wrong answer on 1 279159310
- after increasing and decreasing the limit for n, I started getting my answer getting closer and at n = 44730 279164491 it got accepted!

```
vl pree;
vl precomp(){
ll r = 44730;
vl pre;
for(int i=1;i<=r;i++){
pre.pb((i*(i+1))/2);
}
return pre;
}
int32_t main()
{
fastio()
auto solve = [&] () {
ll n;
cin>>n;
ll m ;
cin >> m;
ll diff = m-n+1;
auto it = lower_bound(pree.begin(),pree.end(),diff);
ll ans = it - pree.begin();
cout << ans+1<< endl;
};
int t;
t=1;
pree=precomp ();
cin>>t;
while(t--)
{
solve();
}
return 0;
}
```

Can anyone help me with the detailed analysis of the code? Why my n = 44730 worked? and what should be the ideal limit? And also why other people's brute force solution didn't give TLE?

Well I don't think you should do this. Well my approach is to use the quadratic formula since you have this nice inequality here

$$$\newline$$$

$$$\newline$$$

And since it is always rounding down so it can be guaranteed that the inequality is satisfied. So when coding it should looks something like this

You can view my solution here 279086455

oh, that's a good one! How did I miss that? Can you please help with my approach?

Yeah since x can be large as

So when $$$r = 10^9$$$ and $$$l = 1$$$ then $$$x \rightarrow max$$$ which is $$$\sqrt{10^9}$$$

When you build the array the difference between abjacent elements is like this:

1 2 3 4 5 6 ......

so if l = 10 and r = 20 the longest good array is 10 11 13 16 20

If you keep adding 1, 2, 3, 4, 5, 6 .... to build the next element in the array you will realize that after 44730 iterations you are already above 10^9 which is the max of r, this is why your n = 44730 works and without pre-computing and bruce forcing should work too

yeah got it ! Thanks

In this case, brute force works because of a mathematical concept known as the harmonic series, which states that 1 + 1/2 + 1/3 + 1/4 + ... + 1/n ≈ log n. For this problem, we would be adding 1 + 2 + 3 + 4 + ... + n such that the sum of all elements ≤ r-l, where the upper limit for r is 1e9 and the lower limit for l is 0. Therefore, we can assume that for each testcase, it runs in roughly log 1e9(note that log = log_2 and not log_10) operations. Multiply that by t, and we get roughly 300000(assuming my math isn't off) operations per test.

Hope this helps!

You dont need to precompute values, Just use the quadratic formula for the difference (r-l). you just need to equate n^2+n = 2*(r-l)

then we can use the quadratic formula to find the no of elements (n+1) in the array.

This code works fine if you want to try it for debugging purposes.

The maximum length of array $$$a$$$ is obtained when the difference of two consecutive differences is minimized ; Thus we set the difference of two consecutive differences is only 1 , For example consider $$$l=1,r=10$$$ thus we can consider the following array as the optimal choice

thus the maximum length is $4$ , Notice we can form an $$$\textbf{Optimal Model}$$$ , $$$a$$$ can be considered as :

since each time we've an element $l$ + Sum of First $$$n$$$ integers called Triangular Numbers

We want to determine the value of $x$ above i.e.

First approachSimulate the process with brute force inCodeSecond approach: $T(n)$ is increasing , thus we can use binary search in $$$\mathcal{O}(\log(r-l))$$$Code$$$\textbf{Third Approach}$$$ : We can reverse this with Quadratic Formula in $$$\mathcal{O}(1)$$$ :

Consider

Since we may have rational part We've to perform ceiling , thus

CodeYes impressive , thanks