Taxman Programming Project: Model Solution

Description of the Algorithm

Now p is usually the best number to take, but there is one situation when it is not. This is when there is a proper multiple q of p where the only proper factors left for q are factors of p AND there are no proper multiples of q left. In that case, removing p would strand q, leaving it for the taxman at the end, so the best thing to do is to take q yourself. Naturally, if there are several such proper multiples q available, then always take the biggest one!

Implementation Details

We also maintain an array number[i] containing the number of factors left for i.

At each stage we have a total order defined on the set of numbers from 1 to n, like this:

p is more desirable than q if:

• p and q have the same number of factors left, and p is bigger than q.
• The number of factors left for p comes before the number of factors left for q in the following list: 2, 3, 4, ..., 1, 0.

Note that the array number[i] makes this order very easy to calculate.

Now we arrange our numbers 1 up to n in a binary heap, where the topmost element is the most desirable number. (Note that the definition of desirability means that the topmost number is always available for us to take right until the end.)

The algorithm now goes as follows:

• Take the topmost element p from the heap, if p is not available to take then we are done.
• Check that p doesn't have any proper multiples that are better (see Description of the Algorithm), if so set p to be the largest one of these.
• Calculate the factors left for p.
• For each factor f left for p, reduce by one number[i] for all the multiples i of f. Every time we change number[i] for any i, we may also need to move it up or down the heap a few places.

Complexity Analysis

  for (i = 1; i <= n; i = i + 1) {
    factor[i] = 1;
  }

  for (i = 2; i <= n; i = i + 1) {
    if (factor[i] == 1) {
      for (j = i; j <= n; j = j + i) {
        factor[j] = i;
      }
    }
  }

Heapifying takes O(n).

Now whenever we remove a number p (for whatever reason) we must reduce number[q] by 1 for every multiple q of p. By a similar analysis as for the seiving, the number of reductions we must perform is O(n log n). In addition, every time this is done we may need to move i up or down the heap some places. In the worst case, O(log n) swaps may be required. Therefore, the total time required by the main body of the algorithm is O(n (log n)²).

The complexity of the whole algorithm is O(n (log n)²).

Performance Information