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

#	User	Rating
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

#	User	Contrib.
1	cry	167
2	Um_nik	163
3	maomao90	162
3	atcoder_official	162
5	adamant	159
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	Dominater069	153
9	nor	153

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 (5)

Write comment?

Intuition2.0

2 months 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

2 months 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.

I know what you are talking about. But forget for sometime that there's no formal proof exist in the world, so now how u think of proving that sufficient condition. We can prove this by imagining that if there exist a answer, then it must lie on a segment.Till here i hope u clear this, now how many index to start with is the question, then for this part u can think like for every t how much we can stretch to right and left...by doing this for every t and taking final intersection segment(means min end — max start + 1) will be our ans, U have to imagine this don't go around formal mathematical proof...Do this with some test cases with pen and paper u will arrive at a informal proof of the sufficient condition

TheScrasse

This solution is one of the most difficult to prove imo. The proof is contained in the editorial of 2018F3 - Speedbreaker Counting (Hard Version). Is the editorial solution for 2018B - Speedbreaker actually easier?

6 weeks ago, # ^ |

idk the editorial was kind of a miss for me ngl

Negationist's blog