Unit 1: Beat the Clock

A contest gives your program a time limit

You send in a program. A machine runs it on secret data and gives it about one second. Correct but slow scores exactly the same as wrong.

So every problem here has two answers: the one that works, and the one that works in time.

Python

total = 0
for i in range(1, 1001):
    total += i
print(total)

print(1000 * 1001 // 2)

It prints

500500
500500

Same answer, a thousand times fewer steps

The loop added a thousand numbers. The formula did one multiply and one divide.

For a thousand nobody notices. Watch what happens when the number gets big: the formula answers instantly for a number the loop could not finish counting to in your lifetime.

Python

def slow(n):
    total = 0
    for i in range(1, n + 1):
        total += i
    return total

def fast(n):
    return n * (n + 1) // 2

print(slow(100000))
print(fast(100000))
print(fast(1000000000000))

It prints

5000050000
5000050000
500000000000500000000000

Count steps, not seconds

Seconds measure the computer. Steps measure the plan, and the plan is the part you choose.

So count how many times the innermost line runs. A loop inside a loop runs its inside line n times for each of n rounds — and that multiplies.

Python

def steps(n):
    count = 0
    for i in range(n):
        for j in range(n):
            count += 1
    return count

for n in [10, 100, 500]:
    print(n, steps(n))

It prints

10 100
100 10000
500 250000

The number to keep in your head

A rough rule that has never let anyone down: a computer manages roughly 100 million simple steps in a second.

So before writing anything, work out how many steps your plan takes. If the answer has more than nine digits, it is the wrong plan — and no amount of tidying the code will save it.

Nobody counts the exact steps

Two loops of n is 2n steps, and a tidier version might be n + 3. Nobody cares: for big n both are "about n", and doubling the machine beats both.

What matters is the shape — what happens to the time when the input doubles. That shape is written with a big O.

The five shapes you will meet

O(1) — same time whatever the size. The formula in lesson 1.

O(log n) — halve the problem each round.

O(n) — look at everything once.

O(n log n) — sorting, and almost everything built on sorting.

O(n * n) — every pair. Fine for 5000 things, hopeless for a million.

Halving is the cheapest thing there is

Keep halving a thousand and you reach 1 in nine steps. Keep halving a billion and you reach 1 in thirty.

That is O(log n), and it is why the next few units keep looking for something to cut in half.

Python

n = 1000
steps = 0
while n > 1:
    n //= 2
    steps += 1
print(steps)

It prints

9

Reading the shape off the code

Loops side by side add — and adding a smaller shape to a bigger one changes nothing, so O(n + n) is just O(n).

Loops inside each other multiply. That is the whole rule.

Python

import math

for n in [10, 100, 1000, 1000000]:
    print(n, math.floor(math.log2(n)), n * n)

It prints

10 3 100
100 6 10000
1000 9 1000000
1000000 19 1000000000000

Every problem tells you how big it gets

Near the bottom of a contest problem, under the story, is a line like 1 <= n <= 200000.

That line is not paperwork. It is the setter telling you which plans are allowed, and reading it first saves writing the wrong program.

The table worth memorising

n up to 10 — anything, even trying every order.

n up to 20 — you may try every subset.

n up to 500 — three nested loops.

n up to 5000 — two nested loops.

n up to 1000000 — sorting, or one pass, and nothing slower.

Why 20 is the subset line

Each of n things is either in your chosen group or out of it, so there are 2 * 2 * 2 * ... groups — two to the power of n.

At 20 that is a million: fine. At 40 it is a million million: not fine. Trying every order instead of every subset runs out far sooner.

Python

import math

print(2 ** 20)
print(2 ** 40)
print(math.factorial(10))
print(math.factorial(20))

It prints

1048576
1099511627776
3628800
2432902008176640000

The best run of numbers

A list of numbers, some negative. Pick a run of neighbours — as long or as short as you like — with the biggest total.

Here the winner starts at the 2 and ends at the second 2, and adds up to 10. The trick is finding that without trying every run.

Python

numbers = [-1, 2, 4, -3, 5, 2, -5, 2]

print(numbers[1:6])
print(sum(numbers[1:6]))

It prints

[2, 4, -3, 5, 2]
10

Speed one: try every run

Start somewhere, keep adding neighbours, remember the best total seen. Two loops, so O(n * n) — for eight numbers that is 36 additions.

For 100000 numbers it is five billion. That is the wrong plan, and it is worth watching the count to feel why.

Python

numbers = [-1, 2, 4, -3, 5, 2, -5, 2]

best = numbers[0]
steps = 0
for i in range(len(numbers)):
    total = 0
    for j in range(i, len(numbers)):
        total += numbers[j]
        steps += 1
        if total > best:
            best = total

print(best, steps)

It prints

10 36

Speed two: one question per number

Walk along once, holding the best run that ends here. At each new number there are only two choices: glue it onto the run behind it, or start again from this number.

Whichever is bigger wins. That is one pass — O(n) — and it is called Kadane's algorithm.

Python

numbers = [-1, 2, 4, -3, 5, 2, -5, 2]

best = numbers[0]
here = numbers[0]
for x in numbers[1:]:
    here = max(x, here + x)
    if here > best:
        best = here

print(best)

It prints

10

Why "start again" is the whole idea

If the run behind you adds up to something negative, dragging it along can only make your total smaller. Drop it.

That single decision is what turns five billion steps into a hundred thousand — and the fast program is shorter than the slow one.