TheLucidSTEM · Informatics olympiad feeder round mock · 90 minutes · 50 marks · No calculator
Name: ______________________ Date: ____________ · MARK SCHEME
Data sheet
Python reminders
range(a, b)gives a, a + 1, ..., b - 1.//is whole-number division (rounding down) and%is the remainder.max(p, q)gives the larger of p and q;sum(a)adds up a list.- Lists are indexed from 0:
a[0]is the first item. not,andandorcombine true/false conditions;!=means "not equal to".
Section A: multiple choice
Suggested time 35 minutes. Two marks each, no penalty for wrong answers.
n = 12
steps = 0
while n != 1:
if n % 2 == 0:
n = n // 2
else:
n = 3 * n + 1
steps += 1
print(steps)steps counts the changes, so it prints 9. 10 counts the values instead of the steps; 16 is the largest value reached.not (x > 3 or y <= 2) ?or, but negating an or turns it into and; the last two options flip the comparisons wrongly (x = 3 or y = 2 give different results).a = [3, 1, 4, 1, 5, 9, 2, 6]
for i in range(1, len(a)):
a[i] = max(a[i], a[i - 1])
print(sum(a))f are made in total (including the first one) when f(16) is evaluated?def f(n):
if n <= 1:
return 1
return f(n // 2) + f(n // 2)work() takes constant time. As $n$ grows, how does the total number of calls to work() grow?for i in range(1, n + 1):
j = i
while j <= n:
work()
j += i##..#
#..##
..#..
##..#
#.###T1 09:00 to 09:40, T2 09:10 to 09:30, T3 09:25 to 10:05, T4 09:35 to 10:02, T5 09:45 to 10:15, T6 10:00 to 10:10.
What is the smallest number of platforms needed?
Section B: structured questions
Suggested time 55 minutes, about 18 minutes per question. Explain your reasoning: a correct method earns marks even if the final number is wrong.
13Cabling the school[9 marks]
A school wants to join its six buildings A to F with network cables so that every building can reach every other one, possibly through other buildings. The cables that can be laid and their costs (in thousands of pounds) are:
| Cable | A–B | A–C | B–C | B–D | C–D | C–E | D–E | D–F | E–F | B–F |
|---|---|---|---|---|---|---|---|---|---|---|
| Cost | 7 | 3 | 4 | 6 | 5 | 9 | 2 | 11 | 8 | 12 |
A cheapest network that joins every building is a minimum spanning tree. Kruskal's algorithm finds one: look at the cables from cheapest to dearest, and lay each cable unless its two buildings are already joined by cables laid earlier (then it would only make a loop).
(a) Use Kruskal's algorithm. List the cables in the order the algorithm looks at them, and say for each one whether it is laid or rejected, until the network is complete.
Answer: D–E laid, A–C laid, B–C laid, C–D laid, B–D rejected, A–B rejected, E–F laid (network complete)
Cables taken in increasing order of cost: D–E 2, A–C 3, B–C 4, C–D 5, B–D 6, A–B 7, E–F 8 [1].
D–E, A–C, B–C, C–D and E–F laid [1].
B–D and A–B rejected, each with the reason that its two buildings are already joined (B to D through C; A to B through C) [1].
The algorithm may stop after E–F, since 5 cables join 6 buildings; also listing C–E, D–F and B–F as rejected is fine. Common error: rejecting C–D because C and D "already have cables": what matters is whether they are already joined to each other.
(b) State the total cost of the network.
Answer: 22 (thousand pounds)
2 + 3 + 4 + 5 + 8 = 22 [1]. Follow through from a wrong list in (a) only if the cables listed form a network joining all six buildings.
(c) The head teacher insists that the cable A–B is laid (it runs along an existing duct). Find the cheapest network that includes A–B, and its cost.
Answer: A–B, D–E, A–C, C–D, E–F; cost 25
Method: lay A–B first and then run Kruskal as before (B–C is now rejected because A–B and A–C already join B to C); or add A–B to the tree from (a) and remove the dearest cable on the loop it makes, A–C–B, which is B–C [1].
Network A–B, D–E, A–C, C–D, E–F with cost 7 + 2 + 3 + 5 + 8 = 25 [1].
Common error: 29 from simply adding 7 to the answer to (b) without removing a cable (that network has a loop).
(d) Explain why the cheapest cable, D–E, must be part of every cheapest network, whatever the other costs are.
Answer: Exchange argument: adding D–E to a network without it makes a loop; removing a dearer cable from the loop gives a cheaper network
Take any network that joins all buildings but does not use D–E. Adding D–E to it creates a loop (D and E were already joined) [1].
The loop contains another cable, which costs more than 2 because all costs are different and D–E is the cheapest. Removing it keeps every building joined and lowers the cost, so the network without D–E was not the cheapest [1].
"Kruskal takes it first" on its own scores 0: it does not show that other methods could not do better without it.
(e) For a network with $n$ buildings and $m$ possible cables, what is the time complexity of Kruskal's algorithm if the cables are sorted by cost and a union-find (disjoint set) structure is used to test whether two buildings are already joined?
Answer: $O(m \log m)$
$O(m \log m)$, because sorting the cables takes the most time, and the union-find tests are almost constant time each [1]. Accept $O(m \log n)$. Do not accept $O(m)$ or $O(n^2)$ without a reason.
14Squeezing the message[9 marks]
A message of 100 letters uses only the letters A to F, this many times each:
| Letter | A | B | C | D | E | F |
|---|---|---|---|---|---|---|
| Count | 30 | 25 | 14 | 12 | 11 | 8 |
We want to give each letter a code made of 0s and 1s so that the whole message is as short as possible. Huffman's method does this. Start with each letter as a tree on its own, with its count as its weight. Repeatedly take the two trees with the smallest weights, and join them under a new root whose weight is the sum of the two. Stop when one tree is left. The code for a letter is read along the path from the root to that letter: 0 for each step to the left and 1 for each step to the right. In this question, when two trees are joined, the one with the smaller weight always goes on the left.
(a) Carry out Huffman's method. List the joins in order, giving the two weights joined and the new weight each time.
Answer: 8 + 11 = 19; 12 + 14 = 26; 19 + 25 = 44; 26 + 30 = 56; 44 + 56 = 100
First join F (8) and E (11) to make 19 [1].
Then D (12) and C (14) to make 26, then 19 and B (25) to make 44 [1].
Then 26 and A (30) to make 56, and finally 44 and 56 to make 100 [1].
Common error: joining 19 with 12 or 14 in the second step: after the first join the two smallest weights are 12 and 14, not 19 and 12. Joining the new tree straight away every time (building a long chain) loses the last two marks.
(b) Write down the code for each letter. Find the total number of bits in the coded message, and compare it with a code that uses the same number of bits for every letter.
Answer: A 11, B 01, C 101, D 100, E 001, F 000; 245 bits against 300, saving 55
Codes: A 11, B 01, C 101, D 100, E 001, F 000 [1]. (The root has 44 on the left and 56 on the right; 44 has the 19 tree on the left and B on the right, and so on.) Accept a different set of 0s and 1s if the left and right rule was ignored but the lengths are right: 2 bits for A and B, 3 bits for C, D, E and F.
Total 2 × (30 + 25) + 3 × (14 + 12 + 11 + 8) = 110 + 135 = 245 bits [1]. (Check: the sum of the new weights 19 + 26 + 44 + 56 + 100 is also 245.)
Six letters need 3 bits each in a fixed-length code (2 bits allow only 4 letters), so 300 bits; Huffman saves 55 bits [1].
(c) Using your codes from (b), decode 0111000001.
Answer: BAFE
01 11 000 001 is B A F E [1]. Follow through from the student's codes in (b) if they are a valid tree.
Decoding works one letter at a time with no gaps because no code is the start of another code: each letter is at a leaf of the tree.
(d) For an alphabet of $k$ letters, how many joins does Huffman's method make? Name a data structure that lets each join find the two smallest weights quickly, and give the time complexity of the whole method with it.
Answer: $k - 1$ joins; a min-heap (priority queue); $O(k \log k)$
$k - 1$ joins, because each join turns two trees into one, starting from $k$ trees and ending with 1 [1].
A min-heap (priority queue) gives the smallest weight in $O(\log k)$ time per removal or insertion, so the whole method is $O(k \log k)$ [1].
Accept a sorted list plus a second queue for the new trees (the new weights come out in increasing order), giving $O(k)$ after an $O(k \log k)$ sort. Scanning the whole list for the two smallest each time is $O(k^2)$ and does not earn the second mark.
15Searching a rotated list[8 marks]
A sorted list of different numbers has been rotated: some numbers were taken from the front and put, in order, at the back. For example, this list of $n = 9$ numbers, with positions 0 to 8:
| Position | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---|---|---|---|---|---|---|---|---|---|
| A | 23 | 31 | 38 | 45 | 52 | 4 | 9 | 12 | 17 |
Ordinary binary search for a value x is:
lo = 0
hi = n - 1
while lo <= hi:
mid = (lo + hi) // 2
if A[mid] == x: report mid and stop
if A[mid] < x: lo = mid + 1
else: hi = mid - 1
report "not found"(a) Trace ordinary binary search on the list above for x = 9. Give lo, hi and mid at each step, and the final result.
Answer: mid = 4 (52), then 1 (31), then 0 (23); reports not found
lo = 0, hi = 8, mid = 4, A[4] = 52 > 9 so hi = 3; lo = 0, hi = 3, mid = 1, A[1] = 31 > 9 so hi = 0; lo = 0, hi = 0, mid = 0, A[0] = 23 > 9 so hi = -1 [1].
The loop stops and reports "not found", although 9 is at position 6: binary search assumes the list is sorted, and it threw away the right half where 9 is [1].
(b) The smallest number is at the point where the list was rotated (position 5 in the example). Describe a method that finds its position in $O(\log n)$ time by comparing A[mid] with A[hi], and trace it on the example.
Answer: While lo < hi: if A[mid] > A[hi] then lo = mid + 1 else hi = mid; answer lo. Trace: mid 4, 6, 5; answer 5
A model answer:
lo = 0
hi = n - 1
while lo < hi:
mid = (lo + hi) // 2
if A[mid] > A[hi]: lo = mid + 1
else: hi = mid
report loIf A[mid] > A[hi], the drop from large to small lies after mid, so the smallest is to the right of mid [1].
Otherwise mid to hi is sorted, so the smallest is at mid or to its left; keep mid (hi = mid, not mid - 1) [1].
Trace: (lo, hi, mid) = (0, 8, 4): 52 > 17 so lo = 5; (5, 8, 6): 9 < 17 so hi = 6; (5, 6, 5): 4 < 9 so hi = 5; stop with lo = hi = 5 [1].
Accept an equally correct method comparing with A[0], as long as it handles a list that was not rotated at all. Half the range is removed each step, which gives $O(\log n)$.
(c) Explain how to use your answer to (b) to search for any value x in the rotated list in $O(\log n)$ time.
Answer: Find the rotation point k; positions 0 to k - 1 and k to n - 1 are each sorted; binary search the part that can contain x
With k the position of the smallest, the parts A[0..k-1] and A[k..n-1] are each sorted [1].
If x >= A[0] (and k > 0), binary search positions 0 to k - 1; otherwise binary search k to n - 1. Two $O(\log n)$ searches in total, still $O(\log n)$ [1]. Searching both parts is also accepted. For x = 9: 9 < 23, so search positions 5 to 8 and find it at 6.
(d) Now suppose the list may contain repeated numbers. Give two lists of the same length, both rotated sorted lists, that show why no method can always find the smallest number without looking at almost every position.
Answer: For example 1, 1, 1, 1, 0, 1, 1 and 1, 1, 0, 1, 1, 1, 1
Two lists that agree everywhere except where a single smaller number is hidden, for example 1, 1, 1, 1, 0, 1, 1 and 1, 1, 0, 1, 1, 1, 1 [1]. Every comparison of A[mid] with A[hi] finds them equal until the 0 itself is seen, so the 0 could be in any unseen position and the method may need to look at all of them: $O(n)$ in the worst case.
A statement that duplicates "break" binary search with no example scores 0.
TheLucidSTEM practice paper. Questions are original and written in the style of a first national round; this is not an official olympiad paper.