![[BIO99 Logo]](../../../images/bio99-logo.gif){kind=logo}
the computing competition for schools and colleges.
We are proud to present BIO'99.
![[Data Connection logo]](../../../images/dc_logo3-s.gif){kind=logo}
| |
The British Informatics
Olympiad is the 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:
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[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.
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).
| |
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.