COOKOFF - Editorial

PROBLEM LINKS

Practice
Contest

DIFFICULTY

MEDIUM

EXPLANATION

Assume, without loss of generality, that C1≤C2 (otherwise swap them). There are 2 cases to consider.

If there are more than M available problems with difficulty ratings between C1 and C2, inclusive, then all problems with a difficulty rating less than C1 or greater than C2 can be ignored. Now, we can decide, given a maximum difficulty gap G, if it’s possible to select M problems such that the difficutly gap does not exceed G in O(N) time (assuming the difficulty ratings have been sorted ahead of time). To accomplish this, we use a greedy method where we select P1 as the problem with the highest difficulty rating not exceeding C1+G, then Pias the problem with the highest difficulty rating not exceeding Pi-1+G for 1 < i ≤ M. If Pm ≥ C2, then there is a solution. The minimum value of G can be found using binary search.

If there are at most M available problems with difficulty ratings between C1 and C2, then we choose all of them. The remaining problems are chosen greedily, always choosing the problem that produces the smallest difficulty gap between itself and the nearest already chosen problem.

SETTER’S SOLUTION

Can be found here.

TESTER’S SOLUTION

Can be found here.

can anyone explain, how to check

if it’s possible to select M problems such that the difficutly gap does not exceed G in O(N) time