Чарівні мішки#12975

Чарівні мішки (Розбір)

Author:

Roman Bilyi

Solved by:

First to solve:

Infinity

The condition on is equivalent to:

We can create a segment [min(X), max(X)] that characterize a bag. Two bags are good iff their corresponding segments intersect (have at least one common point).

  1. It’s never optimal to leave more than 2 objects in a bag. That’s because to check all conditions, we only use at most 2 values: minimum and maximum in the bag. If some bag contains 3 values a < b < c, we will never use to check whether a pair of bags is good and therefore could be removed.

  2. So all bags should contain either 1 or 2 object, and we want to maximize the number of bags with 1 object. For now, consider the case when all bags have at least 2 objects initially. Bags with one object don’t create any corner cases, it is just easier to explain the solution.

  3. If a pair of bags isn’t good initially, it can’t become good after removing objects. It also means that if we leave 2 objects in a bag , it should the minimum and the maximum. We want the segment corresponding to bag to intersect with some other segments, and there are no conditions that it can’t intersect with some other segments. That means it’s optimal to choose the segment as large as we can – [min(X), max(X)].

  4. Let’s call a bag promising if we can leave 1 object in this bag and 2 objects in all other bags. Let’s find whether the bag is promising. How to find whether we can leave the value x \in A as the only remaining value?

  5. We can’t leave as the only remaining value if and only if there exist bag such that min(A)<max(B)<x or there exist bag such that x<min(C)<max(A). In such case, bag and bag or were initially good but not good anymore. To implement this, we can sort all values for all bags , sort all values and use binary search to find whether a value in a given range exist. Note that we should check every value x \in A, not only x=min(A) or x=max(A).

  6. Now, let’s call a bag special if we leave 1 object in it. Obviously, each special bag should be promising. We know that the condition holds for each pair of two non-special bags. Also, the condition holds and for each pair of special and non-special bag by the definition of promising.

  7. Any pair of special bags can’t be good initially. If we leave only one value a \in A and only one value b \in B, a<b and a>b can’t hold simultaneously.

  8. This means that we should choose the largest subsequence of promising bags, such that each pair of chosen bags is not good. If we denote each bag by its segment, we should find the largest subsequence of non-intersecting segment. Such problem is well-known and can be solved greedily: sort all segments by right end and choose a segment if it doesn’t intersect with the last chosen segment.

  9. If we have bags that contain 1 element initially, those will be promising and then chosen, so no corner case required. The complexity of the solution is O(m \log n), where is the total amount of objects.