start_over's blog

maximum points covered by segments
By start_over, history, 8 months ago, In English

There are N points and M segments, the ith point is located at p[i] and the ith segment's size is s[i]. What is the maximum number of points that can be covered by these segments?

My current solution is O(N * 2^M * M). Is there any better solution?

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

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

can you provide the link to the problem

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

    No. I'm preparing some problems for our company contest and I came up with this problem.

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

I think you solution is something like this:

Let's sort points, then do this DP:

$$$dp(i, msk) =$$$ Maximum number of points $$$\leq p_i$$$, where $$$msk$$$ is a bitmask of used segments.

$$$dp(i, msk) = min(dp(i-1, msk), dp(lowerbound(i-sz_j), msk \oplus 2^j))$$$

→ Reply