This is a cp-tricki article, inspired by the dead project tricki. The idea of the project is to publish short blogs elaborating on ideas that are too small or simple for a comprehensive tutorial, but still useful for many people.
We do not claim any authorship of these tricks, taking our primary purpose to popularise them, so we hope that somebody will find these ideas fruitful.
Acknowledgements.
We start from a simple trick, which was exposed by Sergei Kopeliovich at Winter Programming School in Kharkiv in 2013.
Short description.
If it seems that a problem can be solved by an algorithm of the form: "arrange the objects in a suitable way and then work greedily", there is a general strategy to devise a comparator for this sort.
Prerequisites.
No specific knowledge is required, though familiarity with greedy algorithms would be useful.
General description
The auxiliary problem: find an order that optimises a construction (that is the essential part of the considered problem) if it is known that such an order exists.
We first consider a simplified problem, when only two objects exist, say $$$A$$$ and $$$B$$$. Then our comparator should determine which order is better: $$$AB$$$ or $$$BA$$$. To do so, we can normally introduce a penalty (or a cost) function $$$f(A,B)$$$ denoting the amount of penalty (or cost) we have if one takes object $$$A$$$ first and object $$$B$$$ second. Then our comparator chooses that order in which the penalty is minimal (or cost is maximal). If this comparator (relation) $$$A\prec B$$$ (which is $$$A\prec B \iff penalty(A,B)<penalty(B,A)$$$ or $$$cost(A,B)>cost(B,A)$$$) is transitive (i.e. if $$$A\prec B$$$ and $$$B\prec C$$$ then $$$A\prec C$$$) then after sorting all the objects with respect to it we shall obtain the optimal order.
The main problem: find a maximal-size subset that optimises a construction. (The difference from idea 1 is that we are not forced to take all elements.)
To do so, we use the comparator from the auxiliary problem, and take objects greedily one by one. At each step, we make a choice:
Put this object into the answer set,
Replace an instance in the answer set with this object.
More generally one can write here a knapsack-like dp (if we have a subset we know the order by the auxiliary problem).
Example 1.
Given $$$n$$$ boxes, each of which has its weight $$$m_i$$$ and the weight it can carry on the top $$$a_i$$$, determine the size of the largest tower one can build.
Example 2 (this CSES problem).
Given $$$n$$$ people and their programmer skill ($$$skill_1$$$) and artistic skill ($$$skill_2$$$). We need to take exactly $$$a$$$ programmers and $$$b$$$ artists. Maximise total skill.
Online Judges
- https://www.eolymp.com/en/problems/4701 (problem from Example 1, only Russian statement available)
- https://www.eolymp.com/en/problems/9640
- https://www.eolymp.com/en/problems/1591
- https://www.eolymp.com/en/problems/2219
- https://www.eolymp.com/en/problems/4699 (only Russian statement available)
