Mopriestt's blog

A difficult interval problem
By Mopriestt, history, 2 years ago, In English

I saw this on AIO 2020 and have no idea.

On an interval ranged 1 ~ L there are N segments (Ai, Bi)

You can add at most k extra segments with length X.

What is the longest continuous interval you can get that is covered by segments?

2 <= L <= 10^9

0 <= k <= 10^9

N <= 10^5

sample

  • Vote: I like it
  • +20
  • Vote: I do not like it

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by Mopriestt (previous revision, new revision, compare).

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by Mopriestt (previous revision, new revision, compare).

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Doesn't something simple like two pointers and binary search work here?

We'll use binary search to find out what actual asnwer is and then we'll go through segments considering the begin of our interval is A[i]. We are also going to update pointer to last segment lying in the interval. When moving iterators we'll also count how many segments we need. A little dirty and messy solution but should work anyways.

→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I think the prerequisite of sliding window is: if you move head or tail, middle solution doesn't change. Which might not be true in this problem

    → Reply
    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Can't really see where's the problem. Maybe I'll code this solution later and check whether it works.

      → Reply
»
2 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Sliding window might work

You'd first sort the intervals by A[i], and then merge any touching/overlapping intervals. Then the space between two consecutive intervals i,j would have cost (A[j]-B[i]-1)/X, i.e. the number of extra segments required to fill the gap. Since an optimal solution will always fill consecutive gaps, you could fill the first k gaps and then use sliding window

→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    How are you going to handle the case that one extra X covers multiple intervals? Also, when the head of sliding window changes, all the extra X in the middle might change.

    → Reply
»
2 years ago, # |
← Rev. 3   Vote: I like it +13 Vote: I do not like it

This is a sketch of a possible $$$O(n \log n)$$$ solution (possibly optimizable to $$$O(n)$$$?).

It's easy to see that we can only consider the ranges that start at $$$a_i$$$ values. For a given start point $$$a_i$$$, we can compute the solution in $$$O(n)$$$ time by greedily assigning intervals to bridge between gaps. We'll describe this process and then come up with a way of simulating it faster than $$$O(n)$$$.

Let's look at the first step of this process. In essence, what happens is that we reach the end $$$b_i$$$ of the first interval, where we have a gap. At this point we assign some number $$$cnt$$$ of ranges (as few as possible) until $$$b_i + X \cdot cnt$$$ is within some other range $$$[a_j, b_j]$$$. Afterwards, continue the process as if starting from $$$j$$$.

Let's compute for each $$$i$$$ some value $$$cnt_i$$$ which is the number of ranges that we need to "bridge the gap" and $$$nxt_i$$$ the corresponding $$$j$$$ that we reach. Because $$$nxt_i > i$$$, the edges $$$(i, nxt_i)$$$ form a tree. Let's build binary lifting on this tree. At this point this should give you enough data to binary search how much up this tree you can go starting from $$$i$$$ such that the total sum of $$$cnt_{(*)}$$$ values doesn't exceed the budget $$$k$$$. The answer if starting from $$$i$$$ is now $$$b_j + X \cdot rem - a_i$$$, where $$$j$$$ is the final position you reach after binary searching, and $$$rem$$$ is the remaining budget (number of ranges).

The only question that remains is how to compute $$$nxt_i$$$ ($$$cnt_i$$$ is easy, just $$$\lceil \frac{a_{nxt_i} - b_i}{X} \rceil$$$). This should be a rather good exercise to come up with a solution yourself. (hint: range DS might help).

→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It's brilliant! Thank you bicsi, this is a really neat solution.

    I have another solution to this problem that may work

    Use f[i][j]=X to represent the X extra segments are needed to cover from i to i + 2^j Use g[i][j]=Y to represent when adding f[i][j] extra segments after segment i, the actual terminating node is Y.

    DP to calculate f, g, then loop every starting node and lookup f, g to calculate the answer in logK. Go through this process and reverse all segments to do it again, to cover the case that first extra segment is not starting from i_right

    → Reply
    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Sounds good, although I’m not exactly sure how easy is to precalc that dp. Might be doable.

      I don’t think you need reversing, you should be able to safely assume that the first segment starts at some $$$b_i$$$ (you can always take the contiguous prefix of segments that don’t start at some $$$b_i$$$ and move them to the end instead).

      → Reply