Hepic_Antony_Skarlatos's blog

SEGMENTS spoj problem
By Hepic_Antony_Skarlatos, history, 7 years ago, In English

Hello people. I am trying this problem http://www.spoj.com/problems/SEGMENTS/ few hours and I can't come up with any good solution. Also I did not find any tutorial or any solution for that problem online and this is why I am posting it here. If anyone can suggest any idea or full solution it would be great.

Thank you !

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

»
7 years ago, # |
  Vote: I like it +19 Vote: I do not like it

First of all, notice that the height given in the input is useless, since we can collapse all the segments on the vertical line y = 0 and the answer will remain invariant.

The next observation that is crucial for the specific problem is that you can binary search for the answer. If you can achieve your goal with answer = K you can obviously achieve it with answer = K +1 and vice versa. So, the problem is now equivalent to: Given some line segments and an integer K, is there a way to cover all the segments by drawing vertical lines in such a way that the maximum number of lines that cross a segment is less than or equal to K?

Suppose that your segment endpoints are in the range [ 1, N ], this is a fairly reasonable assumption since you can compress your numbers without influencing the final answer. We seek to construct a solution for our problem and that seems kinda hard, instead of doing that we may ask, what would such a solution look like?

What we are looking for, in essence, is a binary vector, A[ 1..N ] such that A[ i ] = 1 if and only if we draw a verctical line in the position x = i and zero otherwise. What conditions do we want our vector to meet? For every segment [li, ri] we demand that but that doesn't seem to be convenient. Therefore it's best to express the above using the partial sums table of the vector A. If we define our condition above transforms to Sri - Sli - 1 ≤ K. Our table S will also satisfy the inequality Si - Si - 1 ≥ 0, 1 ≤ i ≤ N (that is, our table must increasing since it expresses partial sums).

It is easy to prove that having the table S satisfying those two conditions is equivalent to having the vector A since we can transform from one form to another in linear time.Therefore, after all this reasoning, we seek to find whether there is a table S = (S1, S2, ..., SN) that satisfies:

Sri - Sli - 1 ≤ K, 1 ≤ i ≤ N

Si - Si - 1 ≥ 0, 1 ≤ i ≤ N

Every table that satisfies the above conditions gives us a solution to our original problem and every solution to the problem can be transformed to a table that satisfies the above conditions. Therefore the existence of such a table is a necessary and sufficient condition for our problem to have a solution. But this is just a system of 2N linear differences and it is fairly known how to solve it with bellman-ford( or determine that it can't be solved) in Θ(N2) time.

Complexity: We perform a binary search for our answer K and each value is checked for validity in Θ(N2) time, therefore we have a total of Θ(N2logN) time complexity.

-References: http://www.cs.huji.ac.il/course/2002/dast/slides/BellmanFord.pdf

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

    How to compress numbers?

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

      singleLOOP

      set<int>st;
map<int,int>compress;
vector<pair<int,int>>v(n);
for(int i=0; i<n; i++){
    cin>>v[i].first>>v[i].second;
    st.insert(v[i].first);
    st.insert(v[i].second);
}
int j=1;
for(auto it:st)compress[it]=j++;
for(int i=0; i<n; i++){
    v[i].first = compress[v[i].first];
    v[i].second = compress[v[i].second];
}
      → Reply