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)
- https://codeforces.net/gym/104397/problem/A
Auto comment: topic has been updated by miaowtin (previous revision, new revision, compare).
The trick in general looks pretty cool, but I'm not really convinced by the ideas presented in the blog. First of all, what conditions need to be fulfilled for this trick to be available to use in specific problem (except the transitivity of the relation)? Why is the relation in the 1st example transitive? Why does the technique even work in the first place? I'm so confused.
Let's say you have a problem in which you need to take objects in any order. Your comparator should determine, given two adjacent objects A and B in an order, whether placing them in the order AB is always better (or equal) to placing them in the order BA, or vice-versa (If sometimes AB is better and sometimes BA is better, depending on the other elements, this method won't work). Having such a comparator, it is easy to show via an exchange argument that there exists an optimal solution such that the entire sequence is sorted by this comparator (something like this).
This might sound like a special case, but there is a surprisingly high number of problems for which there is, in fact, such a comparator (the blog I linked to gives a list of some of them).
I believe you can use a special case of greedoids to reason about this blog (another reason why including relevant proofs is important).
in the main problem: 1. how exactly we can make the choose using the comprater? 2. why does it say subset(in the main problem), what if order matters?