Easy- and medium-difficulty competitive programming problems generally involve a single core technique, for example one graph algorithm, or one computational geometry tool, or one greedy method. Harder problems generally involve more than one technique.
Farmer is probably the easiest problem on the IOI 2004 paper. The task goes: fences consist of fenceposts and the segments in between the posts. Some fences are closed, and these have equal numbers of fenceposts and segments. Other fences are open , and these consist of one less segment than the number of fenceposts. You are given $M$ closed fences (loops) with $m_1, \dots, m_M$ fenceposts each and $K$ open fences (strips) of $k_1, \dots, k_K$ fenceposts each. You must choose any $Q$ fenceposts from among these fences. Whenever you pick two consecutive fenceposts, you earn the the segment in between. What is the maximum number of segments you can earn?
When presented with a non-trivial problem, it's a good idea to try make some observations.
- We obviously want to always choose sequences of consecutive posts where possible.
- Loops are "high-value", in the sense that if we pick all the posts in a loop with $n$ posts we earn $n$ segments. But if we pick a strip of $n$ posts, or a portion of a loop with $n$ posts, we earn just $n-1$ segments.
- Loops are equal value regardless of size. Two loops of size 3 each has the same value as one loop of size 6.
- When presented with a long strip and a short strip, we can always take a portion of the long strip of equal size to the short strip, earning the same number of segments. So there is never a situation where picking a short strip is advantageous to picking a portion of a long strip.
- We earn more segments by taking $n$ posts from a long strip than by taking $n$ posts from two or more short strips. In combination with the previous observation, this means we should always take posts from long strips over short strips.
At this point we can start forming an algorithm. The best case scenario would clearly be to take only full loops, in which case we earn exactly $Q$ segments. To determine if this is possible, we must determine if some subset $m_1, \dots, m_M$ sums to $Q$. This is the subset sum problem which can be solved by dynamic programming. So this is what we check first, and if it's possible than we're done. If not, then we cannot achieve $Q$, since any other selection of posts must select at least one strip or at least one portion of a loop.
If we can't achieve $Q$, then there are two cases to consider:
- Suppose $\sum_i m_i > Q$. Loops are higher-value than strips, and all loops are equal value, so suppose we just keep taking full loops in any order while we haven't depleted the quota. For each of these loops, we get a number of segments equal to the number of posts. Eventually we will have taken a total of say $u$ posts, earning $u$ segments, and we will reach a loop which has more posts than our remaining quota $Q-u$. If we take a strip of $q$ posts from this loop, we earn $Q-u-1$ segments, for a total of $Q-1$ segments earned. We know that $Q$ segments are unattainable, so if we earn $Q-1$ we have achieved the best possible result. Hence this greedy algorithm solves this case.
- Suppose instead $\sum_i m_i < Q$. Start by taking all the loops, because they are highest-value. Now only strips remain. By our earlier observations on strips of differing lengths, we can just greedily consume strips in descending order of length while quota remains.
Even in this relatively simple problem, there are two intertwined components that require different techniques: a dynamic programming component followed by a greedy component. One of the most important skills demanded of a competitive programmer is to be able to disentangle a seemingly intractable problem into its components in this way.
