Practice: Climbs Along a Cycling Route

A log of metres climbed in each kilometre: the longest stretch climbing at most 50 metres, then the three kilometres that climb the most.

Choosing between a fixed and a variable window comes down to whether the question fixes the run's length or a rule on its contents. A cyclist logged the metres climbed in each kilometre of a 10 kilometre route: 12 0 25 8 0 14 30 6 3 9. Find the longest stretch of consecutive kilometres that climbs at most 50 metres in all, and the three consecutive kilometres that climb the most. Then say why a variable window is safe on this log.

Show both answers and a solution

The first question fixes a rule, at most 50 metres, and leaves the length open, so it takes a variable window: the longest stretch is 5 kilometres, 12 0 25 8 0, the first window to reach that length. The window is safe because climbs are never negative, so dropping a kilometre can never raise the total.

A variable window over the climbs with a limit of 50 metres

Inputclimbs 12 0 25 8 0 14 30 6 3 9, at most 50

Km 1
1. 12startend
2. 0
3. 25
4. 8
5. 0
6. 14
7. 30
8. 6
9. 3
10. 9
took 12: sum 12, best 1
Km 2
1. 12start
2. 0end
3. 25
4. 8
5. 0
6. 14
7. 30
8. 6
9. 3
10. 9
took 0: sum 12, best 2
Km 3
1. 12start
2. 0
3. 25end
4. 8
5. 0
6. 14
7. 30
8. 6
9. 3
10. 9
took 25: sum 37, best 3
Km 4
1. 12start
2. 0
3. 25
4. 8end
5. 0
6. 14
7. 30
8. 6
9. 3
10. 9
took 8: sum 45, best 4
Km 5
1. 12start
2. 0
3. 25
4. 8
5. 0end
6. 14
7. 30
8. 6
9. 3
10. 9
took 0: sum 45, best 5
Km 6
1. 12
2. 0start
3. 25
4. 8
5. 0
6. 14end
7. 30
8. 6
9. 3
10. 9
took 14, dropped 12: sum 47, best 5
Km 7
1. 12
2. 0
3. 25
4. 8
5. 0start
6. 14
7. 30end
8. 6
9. 3
10. 9
took 30, dropped 0, 25 and 8: sum 44, best 5
Km 8
1. 12
2. 0
3. 25
4. 8
5. 0start
6. 14
7. 30
8. 6end
9. 3
10. 9
took 6: sum 50, best 5
Km 9
1. 12
2. 0
3. 25
4. 8
5. 0
6. 14
7. 30start
8. 6
9. 3end
10. 9
took 3, dropped 0 and 14: sum 39, best 5
Km 10
1. 12
2. 0
3. 25
4. 8
5. 0
6. 14
7. 30start
8. 6
9. 3
10. 9end
took 9: sum 48, best 5

ResultThe longest stretch climbing at most 50 metres is 5 kilometres.

The second question fixes the length at three, so it takes a fixed window: add the kilometre entering, subtract the one leaving. The busiest three kilometres are 14 30 6, climbing 50 metres.

A window of 3 kilometres over the climbs

Inputclimbs 12 0 25 8 0 14 30 6 3 9, window 3

Km 1 to 3
1. 12start
2. 0
3. 25end
4. 8
5. 0
6. 14
7. 30
8. 6
9. 3
10. 9
first window built: sum 37, best 37
Km 2 to 4
1. 12
2. 0start
3. 25
4. 8end
5. 0
6. 14
7. 30
8. 6
9. 3
10. 9
added 8, removed 12: sum 33, best 37
Km 3 to 5
1. 12
2. 0
3. 25start
4. 8
5. 0end
6. 14
7. 30
8. 6
9. 3
10. 9
added 0, removed 0: sum 33, best 37
Km 4 to 6
1. 12
2. 0
3. 25
4. 8start
5. 0
6. 14end
7. 30
8. 6
9. 3
10. 9
added 14, removed 25: sum 22, best 37
Km 5 to 7
1. 12
2. 0
3. 25
4. 8
5. 0start
6. 14
7. 30end
8. 6
9. 3
10. 9
added 30, removed 8: sum 44, best 44
Km 6 to 8
1. 12
2. 0
3. 25
4. 8
5. 0
6. 14start
7. 30
8. 6end
9. 3
10. 9
added 6, removed 0: sum 50, best 50
Km 7 to 9
1. 12
2. 0
3. 25
4. 8
5. 0
6. 14
7. 30start
8. 6
9. 3end
10. 9
added 3, removed 14: sum 39, best 50
Km 8 to 10
1. 12
2. 0
3. 25
4. 8
5. 0
6. 14
7. 30
8. 6start
9. 3
10. 9end
added 9, removed 30: sum 18, best 50

ResultThe busiest three kilometres are 14 30 6, climbing 50 metres.

The listing runs both windows on the log.

cycling_climbs.pypy

def longest_within(climbs: list[int], limit: int) -> tuple[int, int]:
    start = total = best = best_start = 0
    for end in range(len(climbs)):
        total += climbs[end]
        while total > limit:
            total -= climbs[start]
            start += 1
        if end - start + 1 > best:
            best, best_start = end - start + 1, start
    return best, best_start


def busiest(climbs: list[int], k: int) -> tuple[int, int]:
    total = sum(climbs[:k])
    best, best_start = total, 0
    for end in range(k, len(climbs)):
        total += climbs[end] - climbs[end - k]
        if total > best:
            best, best_start = total, end - k + 1
    return best, best_start


climbs = [12, 0, 25, 8, 0, 14, 30, 6, 3, 9]
length, first = longest_within(climbs, 50)
print(f"longest stretch climbing at most 50 m: {length} km,", *climbs[first:first + length])
total, first = busiest(climbs, 3)
print("busiest three km:", *climbs[first:first + 3], "=", total)

OutputRan with python:3.14.8-slim-trixie (Python 3.14.8)

longest stretch climbing at most 50 m: 5 km, 12 0 25 8 0
busiest three km: 14 30 6 = 50

Both passes are O(n) time and O(1) extra space for n kilometres. A log that recorded descents as negative climbs would make the variable window unsafe, while the fixed window would still be right.

Sliding Window

← → move through sections and cards