The British Informatics
Olympiad isthe computing competition for schools and colleges. We are proud to present BIO'99. |

**The 1999 British Informatics
Olympiad - Round One
Worked solution to question 3**

*Romulus is playing a game which is divided into rounds. At
the end of each round points are awarded depending on the result,
and at the end of the game these points are summed for the final
score. Given a final score, Romulus is interested in finding the
minimum number of rounds that might have taken place.*

**3 (a). ***Write a program that
inputs a list of possible points that can be awarded in a round,
followed by a list of final scores. For each final score you
should output the minimum number of rounds that might have taken
place, along with the corresponding points scored.*

*The first line of input will consist of a single integer ***n***
(1<=***n***<=10) denoting the number of
possible points that can be scored in a round. The second line
will consist of ***n*** integers (between 1
and 500) giving the possible points. Note that the numbers in the
second line will not necessarily be sorted.*

*The third line of input will be a single integer ***m***
(1<=***m***<=10) indicating the number
of final scores to be considered. The fourth line will give the ***m***
final scores to be considered (between 1 and 1,000).*

*Your output should consist of ***m***
lines, one for each of the final scores. Each line should contain
the minimum number of rounds, followed by a corresponding example
set of points. You should follow the format given in the sample
run; note that the example set does not need to be sorted. If it
is not possible to produce a given score you should just output ***Impossible
***on that line.*

**Overview of solution.**

To illustrate the different approaches that can be used to solve this question we will begin with a naive algorithm that is simple to solve, but which will not always be correct. We will then look at a recursive search method that will always be correct but could be very slow. Finally, we examine the problem in a different way to produce an elegant and efficient solution.

A Java example program solving parts 3(a) and 3(c) is in file bio99q3.java. The equivalent Turbo Pascal example program is in file bio99q3.pas, and a DOS executable of this program (compressed with PKZIP) is in bio99q3.zip. Basic procedures such as input/output will not be described below but can be seen in these programs.

We assume that the following global variables that give the
input data have already been read in by function `read_input`
in bio99q3.pas
or bio99q3.java:

`n`- the number of possible scores`m`- the number of totals`scores`- an array giving the possible scores (not necessarily sorted)`totals`- an array giving the required totals.

**Greedy solution.**

The idea of a greedy algorithm is to solve the problem step by step, without going back. It is assumed that each step made must be correct. A greedy algorithm that many competitors used is as follows.

Start with a variable `s` holding the current total.
Repeatedly take away the largest score less than or equal to `s`
until `s=0` or no further subtraction can take place.

This algorithm is implemented using function `solve_greedy`
in bio99q3.pas
or bio99q3.java,
which also includes code to sort the `scores` in
decreasing order (using a simple bubblesort algorithm) and
display the solutions.

Test cases 1-3 and 5 used for marking this question were chosen so that a greedy algorithm would actually find the correct answer. However it is not difficult to find an example where it fails. Consider the following example. The available scores are 3 and 4 and the required total 10. This can be reached by:

10 = 4 + 3 + 3

The greedy algorithm works through the following stages

s Scores chosen 10 6 4 2 4+4 Impossible

This finds that no solution is possible because the score 2 is not available.

**Checking every solution.**

An algorithm that would be guaranteed to be correct could be as follows. For each total, see if the required score can be found in one round using a single score, then any two scores (two rounds), every combination of three scores, and so on, terminating when a solution is found. This will always find an optimum solution (using as few rounds as possible), but how fast will it be?

In the worst case, there could be 10 different scores - but potentially many more rounds may required to reach the necessary total, and very many possible combinations.

A simple check of complexity would be as follows. Two possible
scores (e.g. 5, 7). Given *k* rounds there are *k*+1
combinations of the two scores. If we actually need *j*
rounds, we could have to check

2 + 3 + ... + *j*+1 = (j+1)*(j+2)/2-1

combinations, which grows with *j*^2. Checking each
combination of *k* scores also takes time proportional to *k*,
so the time taken to find the solution grows with *j*^3. A
total of 994 would require *j*=142 and of the order of
3x10^6 operations. As the number of scores increases, the number
of possible combinations also grows rapidly. It can therefore be
seen that fully checking every solution is going to be
impractical.

**Dynamic programming solution.**

A better way to solve this problem is to find out the "best" way to get to each possible value given a set of scores, rather than to waste time checking every possible combination from scratch. The solution then consists of simply displaying the correct set of scores.

Taking the scores 3 and 4 as before, we can find all the possible scores and the best ways of reaching them by working through a list.

total Scores chosen 0 (none) 3 3 4 4 6 3+3 7 3+4 8 4+4 9 3+3+3 10 3+3+4 11 3+4+4 12 4+4+4 (not 3+3+3+3) ...

Assume that we have a total and the optimum set of scores
required to reach it. By taking each available score in turn we
can find a new total and check if this combination is also
optimum. Investigating every possible combination now takes no
more than *total***n* simple checks, which will not
be more than 10^4.

We can fully represent the best combination for every number up to 1000 using two 1001-element arrays:

`num_rounds[i]`- the minimum number of rounds required to reach the total*i*`last_score[i]`- the score in the last round of a game giving total*i*.

`num_rounds[0]` is 0 and the other elements can be
initialised to some dummy value (I used 9999) to mean that score
cannot be reached.

Starting from 0, we work through the list up to a total of
1000. If a given value is a possible score (i.e. `num_rounds[i]<9999`),
then for every possible score `scores[j]` we know that we
can reach the new total `i+scores[j]` in `num_rounds[i]+1`
rounds. All we have to do is to check if this is the best way
found so far of reaching this new total, and if so set `num_rounds`
and `last_score` to the appropriate value. Once we have
tried all `m` scores we move on to the next valid total,
knowing that we have checked every possible way to reach it.

The last step is to find the required scores given a total. To
do this we use the `last_score` array, stepping down round
by round.

This algorithm is illustrated by the following code in bio99q3.pas and bio99q3.java.

*Pascal*

procedure find_dynamic( show: boolean ); var i, j: integer; begin { Initialise the arrays that store the number of rounds required to reach each value, and the last score. } for i := 1 to 1000 do begin num_rounds[i] := 9999; last_score[i] := 9999; end; num_rounds[0] := 0; last_score[0] := 0; { Find the scores required to reach each total } i := 0; while i <= 1000 do begin { For each possible score, see if the new totals are reached in fewer rounds than before. } for j := 1 to n do if i + scores[j] <= 1000 then if num_rounds[i + scores[j]] > num_rounds[i] + 1 then begin num_rounds[i + scores[j]] := num_rounds[i] + 1; last_score[i + scores[j]] := scores[j]; end; { Show the steps leading to this point } if (i > 0) and show then begin write( i, ':' ); j := i; while j > 0 do begin write( last_score[j], ' ' ); j := j - last_score[j]; end; writeln; end; { Find the next valid total } repeat inc(i); if i > 1000 then break; { We are off the end of the array } until num_rounds[i] < 9999; { We have a valid total } end; end;

*Java*

public void find_dynamic( boolean show ) { int i, j; /* Initialise the arrays that store the number of rounds required to reach each value, and the last score. */ for( i = 1; i <= 1000; i++) { num_rounds[i] = 9999; last_score[i] = 9999; } num_rounds[0] = 0; last_score[0] = 0; /* Find the scores required to reach each total */ i = 0; while( i <= 1000 ) { /* For each possible score, see if the new totals are reached in fewer rounds than before. */ for( j = 0; j < n; j++ ) if( i + scores[j] <= 1000 ) if( num_rounds[i + scores[j]] > num_rounds[i] + 1 ) { num_rounds[i + scores[j]] = num_rounds[i] + 1; last_score[i + scores[j]] = scores[j]; } /* Show the steps leading to this point */ if( (i > 0) && show ) { System.out.print( i + ":" ); j = i; while( j > 0 ) { System.out.print( last_score[j] + " " ); j = j - last_score[j]; } System.out.print( "\n" ); } /* Find the next valid total */ while( true ) { i++; if( i > 1000 ) break; /* We are off the end of the array */ if( num_rounds[i] < 9999 ) break; /* We have a valid total */ } } }

To produce a full solution to this problem we need to call `find_dynamic(false)
`to calculate all of the possible totals, then count up the
number of times each score is required to produce the output in
the appropriate format. This is done by procedure `solve_dynamic`.

- Java example solution program for 3(a) and 3(c)
- Pascal and Java example solutions, and compiled zipped DOS executable
- Statement of question 3
- Index of BIO'99 round one

**Marking.**

There are five tests for 3(a). Tests 2-5 should give more than one line of output; for these tests each output line is marked individually, and the corresponding marks (which are not always equal) are shown. All parts of an output line must be correct for it to receive marks. The output values may be given in any order; for example, in test 2 case 2, an equally valid output would be

4 1x2 1x10 1x5 1x1.

**Test 1.**

1 1 1 10 [1] 10 10x1

**Test 2.**

4 1 2 5 10 3 10 18 24 [1] 1 1x10 [1] 4 1x10 1x5 1x2 1x1 [2] 4 2x10 2x2

**Test 3.**

5 81 9 27 1 3 3 80 50 972 [2] 8 2x27 2x9 2x3 2x1 [2] 6 1x27 2x9 1x3 2x1 [1] 12 12x81

**Test 4.**

8 2 15 31 83 115 222 223 461 6 60 78 144 170 224 299 [2] 4 4x15 [2] 5 1x2 3x15 1x31 [2] 4 2x15 1x31 1x83 [2] 4 2x2 2x83 [2] 2 1x2 1x222 [2] 4 1x15 2x31 1x222

**Test 5.**

4 8 13 27 32 2 7 33 [2] Impossible [2] Impossible

A maximum of [26] marks is available for 3(a).

- Java example solution program for 3(a) and 3(c)
- Pascal and Java example solutions, and compiled zipped DOS executable
- Statement of question 3
- Index of BIO'99 round one

**3 (b). ***Romulus is playing a game
where it is possible to score 1, 3, 9, 27 or 81, and after he is
finished Remus also plays the same game. When they compare their
final scores Romulus has scored 80 more than Remus. What is the
minimum number of rounds they may have played between them? How
about if Romulus has 50 more points than Remus? [Give an example
in each case.]*

*i.* To make a difference of 80 using as few rounds as
possible, two rounds have been played (one each): Romulus scores
81 and Remus 1.

*ii. *To make a difference of 50, there are two
possibilities that both require 4 rounds, the minimum number. The
first is Romulus 81, Remus 27+3+1=51. The second is Romulus
27+27=53, Remus 3+1=4. Only one of these needs to be given.

**Marking.**

**"80" case**:

[1] 2 rounds

[1] Romulus: 81, Remus: 1

**"50" case**:

[1] 4 rounds

[1] Romulus: 81 Remus: 1, 3, 27 OR Romulus: 27, 27 Remus: 3, 1

(Supplementary. Students who mix up Romulus and Remus should lose no marks.) A maximum of 4 marks available for 3 (b).

**3 (c). ***Remus is playing a game
where it is possible to score 1, 4, 5, 17, 28, 43 or 100 each
round. At the end of the game the final score is 100.
Furthermore, the scores for each round never got worse, e.g. if
17 was scored in one round then the score for every future round
was at least 17. How many different ways might this have
happened?*

To solve this problem it is necessary to write a program. Rather than try to adapt the program from part (a), a simple recursive solution is all that is required to solve this.

The goal is to return the number of permutations required
using numbers from the set {1, 4, 5, 17, 28, 43, 100} in strictly
increasing order that reaches a total of 100. Let us define an a
array `scores3c` containing these elements. We require a
function `perms_3c(total, num)` that returns the number of
valid permutations of the first `num` elements of `scores3c`
that sum to `total`. When called with `total=100`
and `num=7`, this returns the required answer.

This is convenient because it allows us to break the problem down into some simple cases, calling itself.

Each time `perms_3c` is called it tries zero or more
rounds with the score `scores_3c[num]`, calling itself
with the remaining `total` and `num-1`. The
following code illustrates this and shows the special cases.

*Pascal*

const scores3c: array[1..7] of integer = ( 1, 4, 5, 17, 28, 43, 100 ); function perms_3c( total, num: integer ): integer; { Returns the number of permutations of the first num scores that sum to total, in strictly increasing order. Calls itself. } var perms, current: integer; begin perms := 0; current := total; if total = 0 then { There is only one way to reach a total of zero. } perms_3c := 1 else if num = 1 then { There is only one way to reach any total using only 1s. } perms_3c := 1 else begin { Otherwise we count the permutations that finish with zero or more instances of the last number. } while current >= 0 do begin perms := perms + perms_3c( current, num-1 ); current := current - scores3c[num]; end; perms_3c := perms; end; end; procedure part_3c; begin writeln( 'Number of different ways: ', perms_3c( 100, 7 ) ); end;

*Java*

int[] scores3c = { 1, 4, 5, 17, 28, 43, 100 }; public void part_3c() { System.out.println( "Number of different ways: " + perms_3c( 100, 6 ) ); } public int perms_3c( int total, int num ) { /* Returns the number of permutations of the first num scores that sum to total, in strictly increasing order. Calls itself. */ int perms = 0; int current = total; /* There is only one way to reach a total of zero. */ if( total == 0 ) return 1; /* There is only one way to reach any total using only 1s. */ if( num == 0 ) return 1; /* Otherwise we count the permutations that finish with zero or more instances of the last number. */ while( current >= 0 ) { perms = perms + perms_3c( current, num-1 ); current = current - scores3c[num]; } return perms; }

(Note the differences between the code for the two languages, which are due to Java arrays being indexed from 0, while the Pascal arrays count from 1 in this case.)

A Java example program solving parts 3(a) and 3(c) is in file bio99q3.java. The equivalent Turbo Pascal example program is in file bio99q3.pas, and a DOS executable of this program (compressed with PKZIP) is in bio99q3.zip.

**Marking.**

The correct solution to 3(c), getting [5] marks, is 1333. No other solutions get marks.

- Java example solution program for 3(a) and 3(c)
- Pascal and Java example solutions, and compiled zipped DOS executable
- Statement of question 3
- Index of BIO'99 round one

The British Informatics Olympiad