4

How to solve the dual of this famous problem?

 1 year ago
source link: https://codeforces.com/blog/entry/111004
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
neoserver,ios ssh client

Hello, beautiful people of Codeforces.

Yesterday I spent several hours trying to solve the following problem, which feels that should be an easy dp. I then tried to search it on Google and failed. I feel like it's almost impossible to find solutions to algorithmic problems via search engines, they always return stuff that matches with one or two words from the statement but not the problem itself. Anyway, here's the problem:

You are given nn line segments [li,ri][li,ri] (1≤li≤ri≤2n1≤li≤ri≤2n) and a number kk. You are allowed to select kk points on the number line. What is the maximal number of segments that conitain at least one of the selected points you can obtain?

Example:

6
1 7
3 5
6 8
2 7
7 11
10 12
2

The answer is 5. We can select points 4 and 7, hitting all segmets but the last one. Hitting all segments is impossible, as [3, 5], [6, 8] and [10, 12] are disjoint. Note that even though segment [1, 7] is hitted twice, it is only counted towards the solution once.

We are also given that kk is much less than nn. I expect the solution to run in O(nk)O(nk) with possibly some loglog s.

Note 1: When k = 1 this is a well know problem and can easily be solved in O(nlogn)O(nlog⁡n):

  1. Create 2n2n event of the form (li,+1)(li,+1) and (ri,−1)(ri,−1);
  2. Sort the events by the first coordinate;
  3. The answer is the maximal sum of the second coordinate over the events with the first coordinate up to some ii (this can be computed with a single loop);

Note 2: I called it a "dual" problem to another well know problem: Given nn line segments [li,ri][li,ri] (1≤li≤ri≤2n1≤li≤ri≤2n), what is the minimal number of points to hit all the segments?

This "primal" problem is easily solvable in O(nlogn)O(nlog⁡n) by a greedy, selecting always the first end of not-yet-hit segments.

5 hours ago, # |

← Rev. 2 →  

+69

Let's consider a relaxation: Say that there is a variable xixi for every point (1≤i≤2n1≤i≤2n) which means "how many times we take this point" and a variable yjyj for every segment (1≤j≤n1≤j≤n) which means "how many times we cover this segment". The limitations are:

  • xi≥0xi≥0

  • ∑2ni=1xi≤k∑i=12nxi≤k

  • yj≤∑rji=ljxiyj≤∑i=ljrjxi

  • yj≤1yj≤1

and we want to maximize ∑nj=1yj∑j=1nyj.

In the original problem xixi and yjyj should be integers (0 or 1, but it doesn't matter). For relaxation we will drop this requirement, now xixi and yjyj can be real. This is a linear programming problem (and the original was ILP).
I'm not strictly sure here, but it seems that the answers for LP and for ILP are the same. The reasoning is along the lines of: Let's look at the optimal solution for LP which is not integer, there is a leftmost non-integer xixi, if ∑2ni=1xi<k∑i=12nxi<k we can just increase it until it either becomes 1 or the sum reaches kk, so now we can assume that the sum is kk, that means that there should be another non-integer xx, let's take the second leftmost, now we can increase one of them by ΔΔ and decrease another by ΔΔ, one of those actions is not making the answer smaller, thus we can eliminate all non-integer variables.

It is easy to see that if we take a valid solution of LP for some value of kk (k1k1) and another value of kk (k2k2), and choose some 0≤λ≤10≤λ≤1, then look at the linear combination of those two solutions with coefficients λλ and (1−λ)(1−λ) we will get a valid solution for value of kk equal to λk1+(1−λ)k2λk1+(1−λ)k2. If we take optimal solutions for k1k1 and k2k2, let's say that their corresponding values of target function are c1c1 and c2c2, we will get a valid solution for λk1+(1−λ)k2λk1+(1−λ)k2 with value of target function equal to λc1+(1−λ)c2λc1+(1−λ)c2, which means that the answer for this value of kk is at least that, so answer as a function of kk is concave.

Thus we can apply lambda optimization: binary search on λλ and find the optimal solution when the target function is s−λks−λk, where ss is the number of segments we have covered and kk is the number of points we used.

To solve this problem we can use a DP: dp[x]dp[x] — best value of target function if the rightmost taken point is xx, so further we will only be able to cover segments that has left border strictly to the right of xx. It is O(n2)O(n2), but we can optimize it with scanline and segment tree:

We will move current point to the right and in segment tree we will store what will be the value with which we will update DP if we do update from xx. When we encounter new segment, we should do +1 for all xx before it. When we encounter an end of a segment, we will do -1 for all xx before its left end. Thus the DP works in O(nlogn)O(nlog⁡n) and the whole solution is O(nlog2n)O(nlog2⁡n).

4 minutes ago, # |

← Rev. 2 →  

0

See this (official solution is O(nα(n)logn)O(nα(n)log⁡n)

report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK