A key step in making progress towards a solution to a problem is to make an observation. That is, discover some key fact about the problem that might help us towards a solution.
Do you remember the problem Frog from the tutorial on brute-force? Our brute-force algorithm looked like this:
It's certainly very slow to check every triplet of fences. Since we're looking for large jumps, it seems like it would make sense to use the tallest fence for the middle post, and to use the shortest fence for one of the side posts. Don't be fooled though! Only one of these observations is true:
for i = 1 to N: for j = i+1 to N: for k = j+1 to N: # Check if the i-th, j-th and k-th fence posts form a valid obstable course. # If they do, record the difficulty. # Print the greatest difficulty seen.
You should not always use the tallest fence post! Let's show with a counterexample that it is not always best to pick the tallest fence post.
The fence post of height 6 can create an obstacle course with difficulty \(1+5=6\) (using the fence posts of height 5, 6 and 1). This isn't optimal though: by using the fence posts of height 1, 5 and 2, we can get an obstacle course with a difficulty of \(4+3=7\). This doesn't use the tallest fence post.
You should always use the shortest fence post! To prove this, let's suppose that there is a counterexample. That is, there is some arrangement of fences where the best triplet of fences does not include the shortest fence. We can always replace one of the side fences with the shortest fence (we replace whichever side fence is on the same side of the middle fence as the shortest fence). This swap produces a better answer if the old fence was taller -- which it must be, since the new fence is the shortest one! The diagram below shows two examples of the swap being made.
Using this observation, we can now improve our brute-force solution:
# First, find the shortest fence post. Let's say it's the k-th fence post. for i = 1 to N: for j = i+1 to N: # Check if the i-th, j-th and k-th fence posts form a valid obstable course. # If they do, record the difficulty. # Print the greatest difficulty seen.
This solution is much the same as the previous one, except it's got one less nested loop. We did add one additional step at the start, finding the shortest fence post, but this is nothing compared to dropping from a triple nested loop to a double nested loop.
Let's look at a different problem: Giant Hippos TODO: Hippos is missing from ORAC2!
There are a lot of options for placing fences (why do so many problems involve fences?). Try to simplify the problem by working out where you should place your fences.
To save a group flowers, you need to place two fences -- one to defend from hippos on the left, and one to defend from hippos on the right.
Since each group of flowers takes 2 fences to save, we can save a total of \(F/2\) groups of flowers, rounded down. Of course, we should save the \(F/2\) groups with the most flowers.
This is mostly correct, but we still have to worry about the two end-groups that only need one fence to save from the hippos. Fortunately, we can just try all three possible cases: