py4kidsSearch
Exit slides Esc

Unit 3 — Fast Enough?

Slide 1 of 23

  1. A contest gives you the input SIZE before you write a line of code. "Fast enough?" means: will my plan finish inside the time limit at that size? This unit counts operations, compares growth rates, and reads constraints to CHOOSE an algorithm — then ships a fast stdin solver. Each idea is a short executable demo with a Notice.

    • Count the basic steps a plan takes as the input grows.

    • Tell the growth families O(n), O(n squared) and O(log n) apart.

    • Read the constraints and estimate whether a plan fits a budget of about 100,000,000 steps.

    • Replace a slow pair check with a one-pass dictionary solution.

  3. Lesson 1 — Is My Plan Fast Enough?

    Before writing a solution, count the work it does, see how that work grows with N, and check it against the contest's limits.

  4. Count the Operations

    The work a program does grows with the input. Count the basic steps for a single loop versus a nested loop over the same list.

  5. values = [8, 3, 6, 1, 9]
single_loop_checks = 0
for value in values:
    single_loop_checks = single_loop_checks + 1

print("N:", len(values))
print("Single-loop checks:", single_loop_checks)
assert single_loop_checks == 5

    Output

    N: 5
Single-loop checks: 5

    One loop over N items does N steps — O(n).

  6. values = [8, 3, 6, 1, 9]
nested_loop_checks = 0
for first in values:
    for second in values:
        nested_loop_checks = nested_loop_checks + 1

print("N:", len(values))
print("Nested-loop checks:", nested_loop_checks)
assert nested_loop_checks == 25

    Output

    N: 5
Nested-loop checks: 25

    A loop inside a loop does N×N steps — O(n squared). Five items already cost 25.

  7. Three Growth Families

    Picture how O(n) and O(n squared) grow as N gets bigger (using multiplication, not powers).

  8. for n in [10, 100, 1000]:
    linear_work = n
    square_work = n * n
    print("N =", n, "O(n) picture =", linear_work, "O(n squared) picture =", square_work)

    Output

    N = 10 O(n) picture = 10 O(n squared) picture = 100
N = 100 O(n) picture = 100 O(n squared) picture = 10000
N = 1000 O(n) picture = 1000 O(n squared) picture = 1000000

    At N=1000, O(n) is 1000 but O(n squared) is 1,000,000 — a thousand times more work.

  9. Read the Constraints Before Choosing

    Contests cap N. Estimate the cost ARITHMETICALLY (a multiplication, not a real loop) to see which plan fits a ~100,000,000-step budget.

  10. small_n = 100
large_n = 100000
print("Small O(n squared) estimate:", small_n * small_n)
print("Large O(n squared) estimate:", large_n * large_n)
print("Large O(n) estimate:", large_n)
assert small_n * small_n == 10000
assert large_n * large_n == 10000000000

    Output

    Small O(n squared) estimate: 10000
Large O(n squared) estimate: 10000000000
Large O(n) estimate: 100000

    O(n squared) at N=100 is tiny (10,000) but at N=100,000 it is 10,000,000,000 — far over budget. The estimate is instant: no loop actually runs that many times.

  11. Halve a Number Range

    When each step throws away half the possibilities, the count grows like O(log n) — very slow growth.

  12. secret = 73
low = 1
high = 100
guesses = 0

while low <= high:
    guess = (low + high) // 2
    guesses = guesses + 1
    print("Guess", guesses, "tries", guess, "inside", low, "through", high)
    if guess == secret:
        break
    elif guess < secret:
        low = guess + 1
    else:
        high = guess - 1

print("Found it in", guesses, "guesses")
assert guess == 73
assert guesses == 6

    Output

    Guess 1 tries 50 inside 1 through 100
Guess 2 tries 75 inside 51 through 100
Guess 3 tries 62 inside 51 through 74
Guess 4 tries 68 inside 63 through 74
Guess 5 tries 71 inside 69 through 74
Guess 6 tries 73 inside 72 through 74
Found it in 6 guesses

  13. 1–100 is found in 6 guesses because each guess halves the range.

  14. One Problem, Two Approaches

    Two-sum: is there a pair adding to the target? The SLOW way checks every pair (O(n squared)). Run it on a small literal input and count the checks.

  15. data = '6 20\n2 4 6 8 10 12'
tokens = data.split()
n = int(tokens[0])
target = int(tokens[1])
numbers = []
for position in range(n):
    numbers.append(int(tokens[position + 2]))

checks = 0
found = False
for first_position in range(n):
    for second_position in range(first_position + 1, n):
        checks = checks + 1
        if numbers[first_position] + numbers[second_position] == target:
            found = True

answer = "NO"
if found:
    answer = "YES"
print(answer + "\nPair checks: " + str(checks))

    Output

    YES
Pair checks: 15

  16. 6 numbers cost 15 pair checks. At N=100,000 that is about 5 billion — too slow. (Complexity is a judgement we make; it is not auto-checked by the tests.)

  17. The FAST way remembers partners already seen in a dictionary and checks each number once (O(n)).

    Put it together: the fast two-sum program reads N, the target, then the N numbers from stdin, and prints the answer plus how many partner checks it made.

  18. Try it
    import sys

data = sys.stdin.read()
tokens = data.split()
n = int(tokens[0])
target = int(tokens[1])
seen = {}
checks = 0
found = False

for position in range(n):
    number = int(tokens[position + 2])
    needed = target - number
    checks = checks + 1
    if needed in seen:
        found = True
    seen[number] = True

answer = "NO"
if found:
    answer = "YES"
print(answer + "\nPartner checks: " + str(checks))

  19. Run the full solver from this unit folder:

    python assets/l1.py < assets/l1/1.in

  20. One pass with a seen dictionary — each number does ONE partner check (6 here, versus 15 for the slow pair scan).

    Complexity: O(n) — linear, versus the slow O(n squared) pair scan. At N=100,000 the fast solver does 100,000 checks, not 5 billion.

  21. A Contest Checklist

    Before coding: (1) read the constraints; (2) estimate your plan's steps (N, N×N, N×log N); (3) compare to a ~100,000,000 budget; (4) if it is over, look for a faster idea (sorting, a dictionary, binary search). Fast enough beats clever.

    • One loop over N items is O(n); a loop inside a loop is O(n squared).

    • At N = 100,000, an O(n squared) plan costs about 10,000,000,000 steps, far over budget.

    • Halving a range each step takes only O(log n) steps, so 1 to 100 needs just a few guesses.

    • A seen dictionary finds a pair with a given sum in one pass instead of checking every pair.

    • Check the constraints before coding: fast enough beats clever.

  23. You can now estimate whether a plan is fast enough before you write it.