The allowed time is 4 hours although this may be split into two 2 hour sessions provided papers and materials are kept secure and Question Two is only given at the start of the second session.
Students need to bring pens, a ruler and a calculator and you should provide paper, an appropriate computer and programming language. The solution to Question One should be typed on an IBM PC or compatible in Pascal, C or QBasic; Borland (Turbo) Pascal (version 6.0 or later) is very strongly recommended. Note that QBasic is supplied with MS-DOS version 5 or later.
The penultimate page of this document is a form which should be photocopied and used to enter pupils for the BIO. The last page is a cover sheet to be filled in by pupils before taking Round One. Closing dates are arrival by 19 April for entries to the 1995 BIO and by 29 April for scripts/cover sheets. Results will be sent out by about 13 May and the BIO Second Round, for the top students, is currently planned for Saturday 20 May.
Please try and arrange for the exam to be sat between 19 and 28 April 1995.
Pupils who achieve 50% or more of the marks for the BIO will be eligible for certificates. Those with between 50 and 69% need only have their cover/mark sheets sent in by 29 April; those with over 70% should also have their scripts sent, together with
* written answers to Question Two
* printout of solution to Question One
attached to the script cover sheet, and copies of all solutions (both source code and, if appropriate, executable file) from pupils at your school in clearly named subdirectories on a floppy disk. Rough working paper is not required.
Antony Rix
The British Informatics Olympiad
Christ's College
Cambridge
CB2 3BU
Question One should be marked straightaway on the computer it was written on, to prevent tampering. Please take a copy on disk of all program, source and data files produced as part of the solution before doing anything else - if you have many candidates to submit, these can all be entered on the same disk in clearly named subdirectories such as SMITH-J or ADAMS-F. When testing the program, you should use both the sample data given on the question sheet and that given below.
The marking scheme for Question Two given here has what we hope are sufficient details for you to mark the answers. Any case of ambiguity in the answers should be given zero marks and cases about which you are uncertain should be referred to the Secretary.
Note: additions were made to the Round One marks scheme in an additional document, so what is given here should not be regarded as complete. This is because other (better) solutions exist and were suggested by several candidates.
Mark
1.1 Required menu structure and exit message. 10
1.2 Correctly inputs and creates the key.
If options 2 and 3 fail, marks may still
be awarded if this can be shown, for
example by an extra menu option. 10
1.3 Correctly reads in and filters messages to
be coded.Output of what decoded message
will look like is correct. 10
1.4 Outputs correctly encoded messages. 15
1.5 Outputs correctly decoded messages. 15
1.6 All program output is correct (format
included). Only available if all
requirements of question are fulfilled. 10
Total marks available for Question 1 70
Choose a menu option: 1) Enter an encoding "key" string. 2) Encode a section of text using the current key. 3) Decode a section of text using the current key. 4) Exit the program. Choice? 1 Enter a code key: abracadabra Press <enter> to continue... Choose a menu option: 1) Enter an encoding "key" string. 2) Encode a section of text using the current key. 3) Decode a section of text using the current key. 4) Exit the program. Choice? 2 Encode a message using the current key. Enter Message (250 characters max) with # to finish. aladdin genie# Message is ALADDIN GENIE# Coded message is BMNSWRPPX MW.# Press <enter> to continue... Choose a menu option: 1) Enter an encoding "key" string. 2) Encode a section of text using the current key. 3) Decode a section of text using the current key. 4) Exit the program. Choice? 3 Decode a message using the current key. Enter Message (250 characters max) with # to finish. bmnswrppx mw.# Decoded message is ALADDIN GENIE# Press <enter> to continue... Choose a menu option: 1) Enter an encoding "key" string. 2) Encode a section of text using the current key. 3) Decode a section of text using the current key. 4) Exit the program. Choice? 2 Encode a message using the current key. Enter Message (250 characters max) with # to finish. alpha beta gamma delta epsilon zeta eta theta iota\ kappa lambda mu nu psi omicron pi rho sigma tau upsilon phi chi omega are all letters of the Greek Alphabet. Socrates was a man. All men are mortal. Socrates is therefore, by a process of deduction, mortal. # Message is ALPHA BETA GAMMA DELTA EPSILON ZETA ETA THETA IOTA\ KAPPA LAMBDA MU NU PSI OMICRON PI RHO SIGMA TAU U\ PSILON PHI CHI OMEGA ARE ALL LETTERS OF THE GREEK \ ALPHABET. SOCRATES WAS A MAN. ALL MEN ARE MORTAL.\ SOCRATES IS THEREFORE, BY A PROCESS OF DEDUCTION# Coded message is BMAHIIKPGHHOPAMNNSXF,..CTISBPBB.CXYYAUVVLUZPQQ,LCD\ DOPCTUUCDQTXYYHAANFFWLVVGUACVGVVHQQFNAAT FTUUKLDDZ\ LRKXIXXJS..BISSDQWABBRUZZ,IVVDIAUZNDDTZZPYAAGZBFQQ\ SBQZ, DYXXM RUVLQGGBRVVWWFGVUUUVDPPAETTUINN.MRWXFE\ EEYJMRCX SS.QQHPVJOVGZB B,,..NCSV,PFFV..RGKCF,FVF# Press <enter> to continue... Choose a menu option: 1) Enter an encoding "key" string. 2) Encode a section of text using the current key. 3) Decode a section of text using the current key. 4) Exit the program. Choice? 4 Exiting...End of Additional Test Data
1.2 Full marks are to be awarded for this if all of the problems from the additional test data are correctly encoded. Otherwise, full marks are to be given if the program has a menu option to show the key which should be, for the given inputs,
'I wandered lonely as a cloud' --> 'I WANDERLOYSCUBFGHJKMPQTVXZ,.'
'abracadabra' --> 'ABRCDEFGHIJKLMNOPQSTUVWXYZ,. '
Zero marks should be awarded if there is any discrepancy or if the key cannot be shown.
1.3 Full marks if the program correctly removes invalid characters and converts to upper case a message to be decoded. This should be shown from option 2 by using the examples in the question and given above. Deduct 5 marks if \ characters are misplaced or absent, 5 marks if filtering/upper case not done, and 5 marks if the # character is absent or misplaced, with a minimum of zero.
1.4 Full marks if encoded output exacly matches the sample data for encoding messages - make sure you've entered the correct key beforehand. Zero marks otherwise.
1.5 Full marks if decoded output exacly matches the sample data for decoding messages for the given keys. The last example in the paper, where the input has a single wrong character, is also to be included in the tests. Zero marks if failure with any one of the test messages.
1.6 Full marks are to be awarded if the program's output exacly corresponds with that given in the sample data, in particular the last example above where text of more than 250 characters is typed. No partial marks.
Mark
Question 2.1 including explanation. 5
Question 2.2 - any suitable form. 5
Question 2.3 with good description of
a valid technique. 5
Question 2.4
to within a few orders of magnitude
and with justification. 5
Question 2.5 5
Marks for clear handwriting and
concise answers. 5
Total marks available for Question 2 30
2.1 Are magic squares (as defined above) unique or not? Why?
Additive marking:
Not unique: +1 mark
Grids may be rotated and reflected to give 8 possibilities for same effective arrangement: +2 marks
Transposition, column and/or row swaps do not affect the sums and allow many different grids: +3 marks
Several possible arrangements of numbers will give non-equivalent magic squares: +3 marks
Example of two non-identical valid magic squares (please check): +1 mark
Addition of further constrains such as diagonals summing to same total may make the solutions effectively unique with only rotation/reflection possible, or may mean no solutions exist for a given n: +1 mark
Maximum for 2.1: 5 marks
2.2 Devise a data structure to represent the grid for up to n = 10.
Any data structure that can uniquely represent the grid is acceptable and gets 5 marks. This basically means arrays (either 2d or 1d with a mapping scheme) of integers or characters (including text strings) are acceptable. It is also possible to store a grid as an n2-digit base n number, although this is not feasible for n approaching 10 and this comment should be made for this answer to be accepted. Use of the term 'matrix' on its own will not suffice.
2.3 How would your program find magic squares?
There are three methods of investigating the problem, all of which are easier if an appropriate representation is chosen. Full marks should only be given for a method which clearly tries all valid possibilities and states when and how the constraint test of row and column sums is applied. Optimisation methods are the subject of question 2.5 and no extra marks should be awarded here. See the sample answer below for one method; a faster but more complex alternative uses queues to track which possibilities are being investigated. The other possible method is a mathematical approach based on permutations and is unlikely to be offered.
2.4 Give a rough estimate of how long your program is likely to take for different values of n, explaining what assumptions you make.
Estimation of how long the program should take is difficult: see the example below for the method used by one of the organisers. A solution that shows awareness of * rapid growth of number of possibilities as approximately (n2)! (factorial), * effect of optimisation on reducing this number, * the time taken by computing each case that is checked; * and quotes values within the following ranges
n approx. time (PC) approx. time (Cray) 3 1 second - 1 hour < 1 second 4 1 month - 100 years(103 - 106 hours) 1 minute - 10 hours 5 over 100 years > 10 hours > 5 not feasible expensiveshould receive the full 5 marks. One mark should be deducted for each small mistake.
2.5 Are there any ways in which the algorithm you have chosen reduces the size of the problem? Suggest further ways of speeding up the search while still finding the correct solution.
Optimisation in this case can be termed as any method which applies the row and column sum constraint at any point earlier than the final grid (when all numbers have been placed) - that is, examines less than (n2)! grids. Any intelligent answer which mentions both reducing the number of possibilities examined and reducing the time taken to examine each should get full marks. If an optimising method was described in part 2.3 it should be referred to here, otherwise one mark should be deducted; no deduction should be made if there is no form of optimisation given in 2.3. Partial marking is left to your discretion.
2.6 Marks for clear handwriting and concise answers.
These marks are to be awarded for legible handwriting (2 marks), brief answers (total question length less than or equal to 6 pages unless there is very detailed analysis) (2 marks) and use of diagrams and/or a clear computer-like language for describing the algorithm used (1 mark).
The above definition does not give unique solutions: many magic squares may exist for each n >= 3. Each 'basic' magic square has seven equivalent permutations by reflection or rotation (a diagram can show this) of the n by n grid, multiplying the number of solutions by 8. Transposition is equivalent to a diagonal reflection. Columns and/or rows may be swapped freely while retaining the sums, giving a large number of "equivalent" solutions.
Furthermore, several possible non-equivalent solutions exist where different arrangements of numbers can still fulfil the row and column summation conditions.
2.2 Devise a data structure to represent the grid for up to n = 10.
A suitable data structure that can be used for n <= 10 is
grid_type = array[1..10, 1..10] of integer;
where only the first 1..n by 1..n elements are used.
2.3 How would your program find magic squares?
To find all possible magic squares - including equivalent ones that are reflections/rotations of squares already found - a suitable algorithm is a backtracking method which places numbers in order in all possible combinations in the grid, rejecting those permutations which have invalid solutions.
A good method (see 2.5) of detecting these is to detect invalid solutions when each element is placed. This is done by starting with placing n2 and working down to 1, checking that each row or column that is added to is less than or equal to the total. Unallocated squares count as zeros so this does not reject valid solutions. This is coded by a recursive procedure
procedure Place(p: integer; grid: grid_type);
var i,j: integer;
newgrid: grid_type;
begin
if p = 0 then
Output_Solution(grid)
else
{ try to place p in all possible places }
for i := 1 to n do for j := 1 to n do if Free(i, j, grid) then
begin
newgrid := grid;
newgrid[i,j] := p;
if (RowSum(i, newgrid) <= LineSum) or (ColSum(j, newgrid) <= LineSum) then
Place(p - 1, newgrid);
end;
end;
where Free returns true if the given location is empty, which is marked by starting with all zeros. RowSum and ColSum return the appropriate sums. This procedure is called with
Place(n*n, emptygrid);and calls Output_Solution whenever a magic square is found.
2.4 Give a rough estimate of how long your program is likely to take for different values of n, explaining what assumptions you make.
It is hard to investigate the precise consequences of the short-cut constraint used here, so we will consider a worst case where all possible permutations are produced. There are thus (n2)! (factorial) solutions to be tested. Assuming each takes 1ms to test, that gives 6 minutes for n = 3, 500 years for n = 4 and 1014 years for n = 5, if all possible solutions are to be found.
In practice, it may be possible to find a solution (of which there may be many) in much less time: the example in the question has 16 and 15 in the first squares, reducing the search by a factor of 240. This is not, however, exhaustive.
Optimisation such as the constraint described can have the effect of reducing the size of the search tree, perhaps by a couple of orders of magnitude, by cutting most of the searching when low-valued numbers are being placed. Thus my estimates for the program time to find all solutions on a PC are 10 seconds for n = 3, a year for n = 4 and, using a Cray, perhaps one month for n = 5. n = 6 is simply enormous.
2.5 Are there any ways in which the algorithm you have chosen reduces the size of the problem? Suggest further ways of speeding up the search while still finding the correct solution.
The optimisation described in 2.3 cuts the problem size by rejecting impossible grids relatively early on in the search and hence reducing the average search depth. It can itself be improved by using a closer estimate of the values of the blank squares: 1 would do; 1 + 2 + .. + m for m blanks would be even better, while still not throwing away valid solutions. The closer this model is taken, the greater the computing expense, and the extra computational effort required to implement the optimisation must be balanced with the saving it produces.
It is also possible to cut the number of solutions by a factor of eight by detecting or avoiding equivalent grids. In practice, this is quite complex to do, but the saving is very significant.
The other way to reduce the calculation time is to cut the processing time per grid. This can be done by using a more powerful processor, or by optimising the algorithm to use fewer or faster machine instructions. For instance, (as in 2.3) copying a 100-element array each time for a 4 by 4 grid is not necessary and slows the program down. Thus many more orders of magnitude less search time can be achieved.
Entry of Students for the 1995 British Informatics Olympiad - to arrive by 19 April CONFIDENTIAL Name of teacher: Position/Department: School: Address: Tel: Fax: Students to be entered for the 1995 BIO - continue on a second sheet if necessary. Name Sex m/f Date of Birth Year in School Predicted Grades Send to: British Informatics Olympiad, Antony Rix Christ's College Cambridge CB2 3BU
1995 British Informatics Olympiad - Round One - Script Cover Sheet To be filled in by the student - please write clearly Name: ___________________________________ Date exam taken: ________________ Programming Language Used: ____________________________ (state computer type if not a PC) Solution to Question One is in a file named: ____________________________________________ You should place all your program code in one file and, if appropriate, also produce a compiled executable file. ________________________________________________________________________________ To be filled in by the teacher Question One Part: 1.1 (10) 1.2 (10) 1.3 (10) 1.4 (15) 1.5 (15) 1.6 (10) Q1 Total (70) Mark: Question Two Part: 2.1 (5) 2.2 (5) 2.3 (5) 2.4 (5) 2.5 (5) 2.6 (5) Q2 Total (30) Mark: Total Mark for BIO 1995 Round One: _________ (100) Script attached: Yes / No Name: ___________________________________ Signed: _______________________________ School and address: _______________________________________________________________ ________________________________________________________________________________ Send to: British Informatics Olympiad, Antony Rix Christ's College Cambridge CB2 3BU