Why is this solution sufficient for the problem "Speedbreaker"?

#	User	Rating
1	tourist	4009
2	jiangly	3839
3	Radewoosh	3646
4	jqdai0815	3620
4	Benq	3620
6	orzdevinwang	3612
7	Geothermal	3569
7	cnnfls_csy	3569
9	ecnerwala	3494
10	Um_nik	3396

#	User	Contrib.
1	Um_nik	164
2	maomao90	160
3	-is-this-fft-	159
4	atcoder_official	158
4	awoo	158
4	cry	158
7	adamant	155
8	nor	154
9	TheScrasse	151
9	maroonrk	151

In the speedbreaker question, why do we need to do: c++ mn[i]=min(mn[i],mn[i-1]),mx[i]=max(mx[i],mx[i-1]);

Full Code

#include<bits/stdc++.h>
using namespace std;
int T,n,a[200005],mn[200005],mx[200005],l,r;
void solve(){
	cin>>n;
	for(int i=0;i<=n;i++)mn[i]=n+1,mx[i]=0;
	for(int i=1;i<=n;i++)cin>>a[i],mn[a[i]]=min(mn[a[i]],i),mx[a[i]]=max(mx[a[i]],i);
	for(int i=1;i<=n;i++){
		mn[i]=min(mn[i],mn[i-1]),mx[i]=max(mx[i],mx[i-1]);
		if(mx[i]-mn[i]>=i){cout<<"0\n";return;}
	}
	l=1,r=n;
	for(int i=1;i<=n;i++)l=max(l,i-a[i]+1),r=min(r,i+a[i]-1);
	cout<<r-l+1<<'\n';
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>T;
	while(T--)solve();
	return 0;
}

Also, I get why the first condition is necessary for there to be a solutions and I get why the second part of the code finds that good interval, but I'm having a little trouble piecing together the sufficiency of the two to guarantee the right answer. Perhaps this is also why I font understand why you have to do the operations on the mins and maxes too.

Comments (2)

Write comment?

Intuition2.0

4 hours ago, # |

← Rev. 3 →

Consider any simple test case like : 6 3 3 3 5 5 there is no 4 in the test case but don't you consider the segment for 4(from l=2 to r=4)? that's why we do mn[i] = min(mn[i], mn[i-1]) and the same for mx

→ Reply

Negationist

16 minutes ago, # ^ |

Oh I kind of get it, it just ensures that not only does each interval have a low enough length, but also that they also all intersect, guaranteeing a solution. This makes sense now. Lastly, could you help me explain how the last check is sufficient to find the solution? I understand that anything out of the bounds we set is guaranteed not to work(so why it is necessary), but not necessarily why it is sufficient? How do these all the things we do come together to make a set of both necessary and sufficient conditions? Like I get it but I don't if you know what I mean.

Negationist's blog