Making Observations

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.

The Troublesome Frog returns

Do you remember the problem Frog from the tutorial on brute-force? Our brute-force algorithm looked like this: 

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.
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: Try and figure out which one it is. Can you prove that it's true? Can you give an example that shows the other one is false (a counterexample)?

False Observation True Observation

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.

Frog

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.

Frog

Using this observation, we can now improve our brute-force solution:

Spoiler 

# 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.

Giant Hippos

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.

Hint

Let's say you wanted to save a group of flowers. Where should the fences be to save those flowers? Which groups of flowers should you save?
Solution

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.

Frog
The two groups of flowers on the very ends only need one fence though, but we'll ignore these flowers for a bit.
Frog

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:

  • We don't save either of the two end-groups. Our algorithm proceeeds normally.
  • We save both of the end-groups. This leaves us able to save only \((F-2)/2\) groups, rounded down.
  • We save one of the end-groups. Of course, we should save whichever side is has more flowers. This leaves us able to save only \((F-1)/2\) groups, rounded down.
We can handle each of these cases separately.

Exercises