harsh_bamane17's blog

Need help in C. Longest Good Array
By harsh_bamane17, history, 5 hours ago, In English

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

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
5 hours ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

$$$ \Large{l + \frac{x(x+1)}{2} \leq r} $$$

$$$\newline$$$

$$$ \Large{x^2 + x + 2(l-r) \leq 0} $$$

$$$\newline$$$

$$$ \Large{x = \frac{-1+\sqrt{1-8(l-r)}}{2}} $$$

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

    ll x = (-1 + sqrt((double)(8*r-8*l+1)))/2;
    if (l + x*(x+1)/2 > r) x--; // Just for sure (it can be omitted)
    cout<<x+1<<"\n";

You can view my solution here 279086455

→ Reply
  • »
    »
    5 hours ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      5 hours ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yeah since x can be large as

      $$$ \Large{x = \frac{-1+\sqrt{1-8(l-r)}}{2}} $$$

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

      → Reply
»
4 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
4 hours ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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!

→ Reply