Tessellate S.T.E.M.S - Computer Science - School - Set 3 - Problem 5

As said by the problem, if one chooses the $(i)$ th chocolate, one cannot then choose $(i-1)$ th or $(i+1)$ th chocolate. Therefore, in order to get the highest outcome, you have two possible start points for this: either $a_1 = 13$ or $a_2 = 14$ (you could start with any, but if you start with a later number, you'll miss some of the largest numbers of this set).

1) Choosing the $(i+2)$ th option each time

• If you were to start with $a_1 = 13$ , then following this pattern will result with this: 13 + 2 + 1 + 4 + 17 + 5 + 9 = 51
• If you were to start with $a_2 = 14$ , then you'll get: 14 + 3 + 5 + 18 + 19 + 6 + 1 = 66

Starting with $a_2$ gives you a better outcome, but we can do better than this. Why? The 6 largest numbers in this set are 9, 13, 14, 18, 17 and 19, which total to 90. We know that we cannot reach this total as (1) 17, 18 and 19 are besides each other, hence we cannot choose all three and (2) 13 and 14 are also besides each other. The first one includes 3 of them (13 + 17 + 9 = 39) and the second one also has 3 of them (14 + 18 + 19 = 51). However, they both have extremely small integers, too, such as 1. Choosing the $(i+2)$ th method doesn't prove to be in this case.

2) Alternating between choosing the $(i+2)$ th AND the $(i+3)$ th option. This involves a little bit of looking ahead at the rest of the numbers in order to come up with the best result of happiness. Taking $a_1 = 13$ again, we now have the option of choosing $a_3 = 2$ or $a_4 = 3$ . Looking at solely these values will lead one to think about choosing $a_4$ , but before choosing that, we need to look at the option that would follow if we were to choose either. If I chose $a_3 = 2$ , then the (i+2)th option is $a_5 = 1$ . The addition of these two equals 3. Similarly, if I were to take a_4 = 3, then the next one would be $a_6 = 5$ , which both add up to 8 > 3. Therefore, we choose $a_4$ and $a_6$ . Using this method, we will get: 13 + 3 + 5 + 18 + 19 + 9 = 67.

However, going back to the start, if we were to choose $a_4$ , then we could start with both $a_1 = 13$ (as we did earlier) or alternatively $a_2 = 14$ . This addition of 1 to the total gives you 68. This number is also made up of 4 of the 6 largest numbers: 9, 14, 18 and 19.

Final solution: 14 + 3 + 5 + 18 + 19 + 9 = 68

(I don't really have an efficient method, so please do correct me or suggest improvements where possible.)

Explanation:

The maximum attainable happiness using the first $k$ chocolates is going the be the largest of either

1. The maximum attainable happiness using the first $k-2$ chocolates plus the happiness value of the $k$ th chocolate, or
2. The maximum attainable happiness using the first $k-1$ chocolates

Python implementation:

1
2
3
4
5
6
7
8
9

def happiness(a):
    # Requires len(a) >= 2
    trial = a[1]
    optim = a[0]
    for i in range(2, len(a)):
        trial_copy = trial
        trial = optim + a[i]  # try adding the ith chocolate to the i-2 optimal subset
        optim = max(optim, trial_copy)  # this is now the max happiness of the i-1 optimal subset
    return max(trial, optim)