Topcoder 16498. GreedyKiller
Problem Statement
Peter is attempting to solve a well-known problem: given a collection of open intervals, find the largest set of pairwise disjoint intervals in the collection.
Peter has no idea how to solve this problem correctly. Hence, he is trying to tweak parameters in a greedy solution, hoping to get it accepted. Prove him wrong by finding a test case on which his solution will fail.
Peter's reasoning is as follows: Long intervals are bad (they can block many others). Intervals that overlap many others are bad (if we take it, we definitely have to discard many others). Hence, Peter came up with the algorithm described below. In the algorithm he uses three constants: lengthPenalty, overlapPenalty, and takeThreshold. You are given their values.
function PetersAlgorithm(collection of intervals):
start with an empty solution
while the collection is non-empty:
for each interval in the collection, calculate:
its length L
the number M of other intervals in the collection this interval overlaps
if M is 0:
the current badness of this interval is 0
else:
the current badness of this interval is (lengthPenalty * L + overlapPenalty * M)
if the smallest badness of an interval is less than or equal to takeThreshold:
take the interval with the smallest badness
add this interval to the solution
remove this interval, and all intervals it overlaps, from the collection
else:
take the interval with the largest badness
remove this interval from the collection
return solution
You have no control over what happens in Peter's algorithm in case of a tie between multiple intervals. Your counterexample must work regardless of how Peter's algorithm breaks ties. Additionally, your counterexample must satisfy the following constraints:
- The number of intervals must not exceed 16.
- The endpoints of all intervals must be integers in [0, 10^5].
- Each interval must have a positive length.
If your counterexample consists of the intervals (a0, b0), (a1, b1), ..., return the <type>int[]</type> {a0, b0, a1, b1, ...}. A solution always exists, and any valid solution will be accepted.
Definition
- Class:
- GreedyKiller
- Method:
- kill
- Parameters:
- int, int, int
- Returns:
- int[]
- Method signature:
- int[] kill(int lengthPenalty, int overlapPenalty, int takeThreshold)
- (be sure your method is public)
Constraints
- lengthPenalty will be between 0 and 10^3, inclusive.
- overlapPenalty will be between 0 and 10^3, inclusive.
- At least one of lengthPenalty and overlapPenalty will be positive.
- takeThreshold will be between 0 and 10^9, inclusive.
Examples
1
0
47
Returns: {0, 150, 200, 230, 235, 935, 225, 238 }
The sample output describes the following collection of intervals: (0, 150), (200, 230), (235, 935), (225, 238).
Peter's algorithm will proceed as follows:
These four intervals have badness 0, 30, 700, and 13. We take the interval with the smallest badness: (0, 150). We are left with the intervals (200, 230), (235, 935), (225, 238). These three intervals still have badness 30, 700, and 13. We take the interval with the smallest badness: (225, 238). Then, we have to eliminate the remaining two intervals from the collection, as they overlap the interval we took.
Thus, Peter's algorithm has constructed a set containing two intervals. However, the optimal solution has three, so we have indeed found a counterexample for Peter's algorithm.
1000
47
0
Returns: {0, 490, 500, 990, 435, 512 }
With takeThreshold = 0 we are only willing to take intervals that have badness 0. In the test case described by the sample input there are no such intervals, so we will discard the interval with the largest badness. This will be one of the two long intervals. We do not know which one Peter's algorithm will discard, but we do know that by discarding either it will make a mistake - the only optimal solution consists of those two intervals.