Bundeswettbewerb Informatik preparation

Rules on residence and age are BWINF's, and BWINF decides any doubtful case. We quote them here as published on 3 November 2026; if a pupil's situation is unusual, the right step is an email to the Bundeswettbewerb office, not a guess on our part.

import random

def blocked_pairs_slow(heights):
    steps = 0
    count = 0
    for i in range(len(heights)):
        for j in range(i + 1, len(heights)):
            steps += 1
            if heights[i] > heights[j]:
                count += 1
    return count, steps

def blocked_pairs_fast(heights):
    steps = 0
    def sort_count(row):
        nonlocal steps
        if len(row) <= 1:
            return row, 0
        mid = len(row) // 2
        left, a = sort_count(row[:mid])
        right, b = sort_count(row[mid:])
        merged, count, i, j = [], a + b, 0, 0
        while i < len(left) and j < len(right):
            steps += 1
            if left[i] <= right[j]:
                merged.append(left[i]); i += 1
            else:
                merged.append(right[j]); j += 1
                count += len(left) - i
        merged += left[i:] + right[j:]
        return merged, count
    _, count = sort_count(heights)
    return count, steps

random.seed(2026)
for n in [1000, 2000, 4000]:
    row = [random.randint(120, 190) for _ in range(n)]
    slow = blocked_pairs_slow(row)
    fast = blocked_pairs_fast(row)
    print(n, "pupils | blocked pairs", slow[0], fast[0], "| steps", slow[1], "vs", fast[1])

Heights are random whole numbers from 120 to 190 cm, fixed by random.seed(2026) so that anyone running the code gets the same rows. The counts are our own output, run with Python 3 on 3 November 2026.

Both methods agree on every row, which is the first thing a careful entrant checks. Then look at how the work grows. Doubling the row from 2,000 to 4,000 pupils multiplies the every-pair method by four, from 1,999,000 to 7,998,000 comparisons, while the merge method only a little more than doubles, from 19,382 to 42,726. On a row of a million pupils, the first method would need about half a million million comparisons; the second, a few tens of millions. A Bundeswettbewerb write-up that states this growth, shows the measured counts and explains why the faster method is still correct is exactly the kind of documentation BWINF asks for.

1. Check by hand. Run both functions on the four heights in the small example and confirm you get 4.
2. Find the edge. What happens when two pupils have the same height? Read the code and say which line decides it.
3. Write the idea. In five sentences, explain why counting len(left) minus i is correct. That paragraph is your Lösungsidee.
4. Going further. Change the problem so that a pupil is blocked only by someone at least 10 cm taller. Which method adapts more easily, and why?

The Einheitenzeitgesetz puts Germany on UTC+1 in winter and UTC+2 in summer. Summer time ended on 25 October 2026 and resumes on 28 March 2027. India does not change its clocks (UTC+5:30), so the gap is four and a half hours until late March and three and a half after.

Rounds 1 and 2 run while school does, so one-to-one pupils often move their lesson nearer a deadline, and back again afterwards. The free first class is booked in your own clock.