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
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!