### harsh_bamane17's blog

By harsh_bamane17, history, 10 days ago,

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?

 » 10 days ago, # | ← Rev. 2 →   0 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<
•  » » » 10 days ago, # ^ |   0 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}$
 » 9 days ago, # |   0 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. #include #include using namespace std; #define int long long signed main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int t; cin>>t; while(t--){ int l,r; cin>>l>>r; int diff = r-l; int x = (8*diff)+1; int sq = sqrt(x); int ans = (sq-1)/2; cout<
 » 9 days ago, # |   0 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 $a=[1 \xrightarrow{+1} 2 \xrightarrow{+2} 4 \xrightarrow{+3} 7]$thus the maximum length is $4$ , Notice we can form an $\textbf{Optimal Model}$ , $a$ can be considered as : $a=[l,l+\text{T}(1),l+\text{T}(2),l+\text{T}(3),.....,l+\text{T}(\max)]$since each time we've an element $l$ + Sum of First $n$ integers called Triangular Numbers $T(n)=\frac{n(n+1)}{2}$We want to determine the value of $x$ above i.e. $\text{What's maximum } x \text{ such that } l+\text{T}(x) \le r$First approach Simulate the process with brute force in $\mathcal{O}(\sqrt{r-l})$ Codefor _ in range(int(input())): l,r=map(int,input().split()) x=1 m=1 while(l<=r): l+=x x+=1 m+=1 if(l==r): print(m) else: print(m-1) Second approach : $T(n)$ is increasing , thus we can use binary search in $\mathcal{O}(\log(r-l))$ Codedef f(x): l,r=0,x while(l<=r): m=(l+r)//2 v=(m*(m+1))//2 if(v>x): r=m-1 else: l=m+1 return r+1 for _ in range(int(input())): l,r=map(int,input().split()) print(f(r-l)) $\textbf{Third Approach}$ : We can reverse this with Quadratic Formula in $\mathcal{O}(1)$ : $\frac{n(n+1)}{2}=f \implies n=\frac{\sqrt{8f+1}-1}{2}$Consider $(f=r-l+1)$Since we may have rational part We've to perform ceiling , thus $\max(x)= \lceil \frac{\sqrt{8(r-l+1)+1}-1}{2} \rceil$ Codefrom math import * def f(n): return ceil((sqrt(1+8*n)-1)/2) for _ in range(int(input())): l,r=map(int,input().split()) print(f(r-l+1))