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;range(a, b, s)goes up (or down, if s is negative) in steps of s and stops before b.//is whole-number division (rounding down),%is the remainder,**is a power.&is bitwise AND: each bit of the result is 1 only if that bit is 1 in both numbers.- Strings and lists are indexed from 0:
w[0]is the first character. continueskips the rest of the loop body and goes on to the next value.
Section A: multiple choice
Suggested time 35 minutes. Two marks each, no penalty for wrong answers.
s = 0
for i in range(1, 8):
if i % 3 == 0:
continue
s += i
print(s)continue skips the rest of the body when i is 3 or 6, so those are not added. 1 + 2 + 4 + 5 + 7 = 19. 28 is the sum with nothing skipped; 9 is the sum of the skipped values only.w = "OLYMPIAD"
r = ""
for k in range(len(w) - 1, -1, -2):
r += w[k]
print(r)(A or B) and not (B and C)true?
work() takes constant time. As $n$ grows, how does the total number of calls to work() grow?i = n
while i > 0:
for j in range(i):
work()
i = i // 2count increased when n = 8?count = 0
for i in range(n):
for j in range(i + 1, n):
for k in range(j + 1, n):
count += 1h are made in total (including the first one) when h(10) is evaluated?def h(n):
if n == 0:
return 1
if n % 2 == 1:
return 2 * h(n - 1)
return h(n // 2) ** 2h(n // 2) ** 2 calls h only once and then squares the result. (The function returns $2^n$, so h(10) = 1024.)& is bitwise AND.)def f(x):
c = 0
while x > 0:
x = x & (x - 1)
c += 1
return c
print(f(200))x & (x - 1) clears the lowest 1 bit of x, so the loop counts the 1 bits. 200 = 11001000 in binary, which has three 1s. 8 is the number of binary digits, not the number of 1s.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.
13The longest rising run of scores[9 marks]
A player's scores in ten games were
3, 8, 2, 5, 9, 4, 6, 10, 1, 7
An increasing subsequence is a choice of some of the games, kept in their original order, whose scores strictly increase (for example 2, 5, 9). We want the longest one.
For each position $i$ (1 to 10), let $L[i]$ be the length of the longest increasing subsequence that ends at game $i$. The algorithm is:
for i = 1 to n:
L[i] = 1
for j = 1 to i - 1:
if a[j] < a[i]:
L[i] = max(L[i], L[j] + 1)
answer = the largest value in L(a) Copy and complete the table of $L[i]$ for all ten games.
Answer: L = 1, 2, 1, 2, 3, 2, 3, 4, 1, 4
Correct values: L = 1, 2, 1, 2, 3, 2, 3, 4, 1, 4 (for scores 3, 8, 2, 5, 9, 4, 6, 10, 1, 7).
All ten correct [3]. Eight or nine correct [2]. At least five correct [1].
Common errors: giving L = 3 for the score 9 is right, but L = 3 for the score 8 is not (only 3 is smaller and comes earlier); allowing equal scores; looking at games that come later.
(b) State the length of the longest increasing subsequence and write down one such subsequence.
Answer: Length 4, for example 3, 5, 6, 10
Length 4 [1].
Any valid subsequence of length 4 [1]. There are 11 of them, including 3, 8, 9, 10; 3, 5, 9, 10; 3, 5, 6, 10; 3, 5, 6, 7; 3, 4, 6, 7; 2, 5, 6, 10; 2, 4, 6, 7. Check it is in the original order and strictly increasing.
(c) How many times is the comparison a[j] < a[i] made for these 10 games? Give a formula for $n$ games and the time complexity of the algorithm.
Answer: 45; $n(n-1)/2$; $O(n^2)$
45 for $n = 10$ (0 + 1 + ... + 9) [1].
$n(n-1)/2$ comparisons, so $O(n^2)$ time [1]. Accept $\Theta(n^2)$ or quadratic. Do not accept $O(n)$ or $O(2^n)$.
(d) The table $L$ gives the length but not the subsequence. Explain what extra information the algorithm should store so that one longest subsequence can be printed at the end, and how it is printed.
Answer: Store prev[i], the j that gave L[i]; follow prev back from the best end and reverse
Store, for each i, the index prev[i] = the j that gave the best value of L[i] (or none if L[i] = 1) [1].
Start at a position where L is largest, follow prev back to the start, then print the scores in reverse order [1].
Accept instead: rebuild without extra storage by scanning backwards for an earlier j with a[j] < a[i] and L[j] = L[i] - 1. Simply "store the subsequence" with no method scores 0.
14The longest dry spell[9 marks]
A weather station records the rainfall on each of $n$ days as whole numbers of millimetres $R[1], R[2], \dots, R[n]$, all zero or more. A spell is a run of consecutive days. A spell is dry if its total rainfall is at most $K$. We want the length of the longest dry spell.
Example: $n = 9$, $K = 5$, rainfall 2, 1, 0, 3, 1, 1, 4, 0, 2.
(a) For the example, find the length of the longest dry spell and say which days it covers.
Answer: 4 days: days 2 to 5 (1, 0, 3, 1) or days 3 to 6 (0, 3, 1, 1)
Length 4 [1].
Days 2 to 5 (total 5) or days 3 to 6 (total 5); either one [1].
No spell of 5 days works: every 5-day spell totals at least 6.
(b) A simple method checks every spell. How many spells are there for $n$ days (give the number for $n = 9$)? What is the time complexity of this method if the total of each spell is found by adding up its days one by one?
Answer: $n(n+1)/2$ spells, 45 for $n = 9$; $O(n^3)$
$n(n+1)/2$ spells, which is 45 for $n = 9$ [1].
Adding up each spell takes up to $n$ steps, so $O(n^3)$ [1]. Accept $O(n^2)$ only if the student explains a running total (adding one day at a time as the end moves) or prefix sums.
(c) Design an algorithm that finds the answer in $O(n)$ time. Write it in pseudocode or clear numbered steps, and explain briefly why it takes $O(n)$ time.
Answer: Sliding window with two pointers: extend the right end, shrink the left end while the total exceeds K, record the best length
A model answer:
left = 1
total = 0
best = 0
for right = 1 to n:
total = total + R[right]
while total > K:
total = total - R[left]
left = left + 1
best = max(best, right - left + 1)
output bestKeeps a window (left to right) with a running total, adding the new day at the right [1].
Removes days from the left while the total is more than K [1].
Updates the best length after each step, correctly (right - left + 1) [1].
Explains $O(n)$: each of left and right only moves forward and moves at most $n$ times, so the total work is at most about $2n$ steps, even though there is a loop inside a loop [1].
Accept equivalent methods (for example prefix sums with a moving pointer). A method that restarts the left end for every right end is $O(n^2)$ and scores at most 1 of the first three marks.
(d) Suppose the numbers could be negative (say they record a change in reservoir level instead of rainfall). Give a short example that shows your method from (c) can then give the wrong answer.
Answer: For example R = 4, -3, 1 with K = 2: true answer 3, window method gives 2
Any valid counterexample with the true answer and the wrong output stated [1]. Example: R = 4, -3, 1 and K = 2. The whole spell totals 2, so the answer is 3, but the window drops the 4 as soon as it is read (total 4 > 2) and never gets it back, so it outputs 2.
Idea to look for: with negative values, a later day can bring the total back down, so throwing away the left end is no longer safe. A statement of this idea without an example scores 0.
15The cost of counting in binary[8 marks]
A counter is stored as a row of binary digits (bits) and starts at 0. The operation INCREMENT adds 1 to it, by the usual method: going from the right, change every 1 to 0 until you reach a 0, and change that 0 to 1. The cost of an operation is the number of bits it changes. For example, going from 0101 (5) to 0110 (6) changes 2 bits, so it costs 2.
(a) What is the cost of the increment from 7 to 8?
Answer: 4
0111 to 1000 changes four bits, cost 4 [1].
(b) The counter starts at 0 and is incremented 16 times, ending at 16. Find the total cost of the 16 increments.
Answer: 31
Method: count how often each bit changes, or list the costs 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 5 [1].
Total 31 [1]. (The last bit changes 16 times, the next 8, then 4, 2, 1: 16 + 8 + 4 + 2 + 1 = 31.)
Common error: 30 from forgetting the 16th increment (15 to 16 costs 5), or 32 from guessing $2 \times 16$.
(c) A single increment can cost as much as the number of bits. Show that $N$ increments starting from 0 cost less than $2N$ in total, so the average cost per increment is less than 2.
Answer: Bit $i$ changes $\lfloor N/2^i \rfloor$ times; the sum is below $N(1 + 1/2 + 1/4 + \dots) = 2N$
The lowest bit (bit 0) changes on every increment, bit 1 on every second increment, and in general bit $i$ changes once every $2^i$ increments [1].
So bit $i$ changes at most $N/2^i$ times (exactly $\lfloor N/2^i \rfloor$) [1].
Total at most $N + N/2 + N/4 + \dots \lt 2N$ (geometric series) [1].
Accept an equally clear argument: each increment changes exactly one 0 into a 1, and a 1 can only be changed back to 0 after it was made, so the number of 1-to-0 changes is at most $N$, giving a total of at most $2N$. An exact formula $2N$ minus the number of 1s in $N$ (31 for $N = 16$) with justification also earns full marks. Checking a few values only, with no general reason, scores at most 1.
(d) A DECREMENT operation (subtract 1) is now also allowed, with cost again the number of bits changed. Show that the average cost per operation is no longer bounded by a constant: describe a sequence of $m$ operations, for any $m$, whose total cost is about $mk$ for a counter of $k$ bits.
Answer: Go to $2^{k-1} - 1$, then alternate INCREMENT and DECREMENT; each costs $k$
Choose a value where an increment changes many bits, for example $2^{k-1} - 1 = 0111\dots1$, whose increment to $1000\dots0$ changes all $k$ bits [1].
Then alternate INCREMENT and DECREMENT: each one changes all $k$ bits back and forth, so $m$ operations cost about $mk$, and the average grows with $k$ [1].
Accept the same idea with any value of the form $2^j - 1$ and $j+1$ bits changing each time. Saying only "decrements can be expensive" 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.