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?
