Need help in C. Longest Good Array

Правка en1, от harsh_bamane17, 2024-09-03 06:18:34

Codeforces Round 970 (Div. 3)

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?

Thank you in advance

Теги precomputation, mle, help me, tle

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский harsh_bamane17 2024-09-03 06:18:34 1544 Initial revision (published)