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
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.
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
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.
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?
idk the editorial was kind of a miss for me ngl