How to solve CERC 17 problem I? (Intrinsic Interval)

Revision en2, by SebiSebi, 2018-10-18 16:53:34

Hi!

I am trying to solve problem I from the 2017-2018 ACM-ICPC Central Europe Regional Contest (CERC 17) as indicated by the official solution. I understood the divide and conquer argument but it's not clear how to compute the left intervals and the right intervals in O(hi — lo). Basically, I cannot understand how this step in the solution works: "Starting from subsequence [mid, mid + 1], we expand it to the left, storing all intervals we encounter until we exit the [lo, hi] window". How to implement this in linear time? Can someone explain this in more detail? It seems that I am missing something which may be obvious :)

Thanks!

Tags acm, divide and conquer, greedy, #acmicpc2017

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English SebiSebi 2018-10-18 16:53:34 38 Tiny change: ' window". Can someo' -> ' window". How to implement this in linear time? Can someo'
en1 English SebiSebi 2018-10-18 16:52:33 759 Initial revision (published)