Negationist's blog

Why is this solution sufficient for the problem "Speedbreaker"?
By Negationist, history, 3 weeks ago, In English

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.

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

»
3 weeks ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

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
  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      3 weeks ago, # ^ |
      ← Rev. 3   Vote: I like it 0 Vote: I do not like it

      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

      → Reply
»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

→ Reply