How to improve efficiency and time-complexity of AIO Cloud Cover solution

Question

Sorry for the noob question, but is there a less time expensive method to iterate through the input list, as upon submission I receive timeout errors. I tried changing the method of checking for the minimum answer by appending to a list and using min function, but as expected that didn't help at all.

Input:

6 3
3
6
4
2
5

Solution:

with open("cloudin.txt", "r") as input_file:
    n, covered = map(int, input_file.readline().split())
    ls = [None for i in range(100005)]
    for i in range(n-1):
        ls[i] = int(input_file.readline().strip())
ans = 1000000001
file = open("cloudout.txt", "w")
for i in range(n-covered):
    a = 0
    for j in range(covered):
        a += ls[i+j]
    if a < ans:
        ans = a
file.write(str(ans))

output:

11

https://orac2.info/problem/aio18cloud/

Note: Blue + White indicates timeout

Answer 1

The core logic of your code is contained in these lines:

ans = 1000000001
for i in range(n-covered):
    a = 0
    for j in range(covered):
        a += ls[i+j]
    if a < ans:
        ans = a

Let's break down what this code actually does. For each closed interval (i.e. including the endpoints) [left, right] from the list [0, covered-1], [1, covered], [2, covered+1], ..., [n-covered-1, n-2] (that is, all closed intervals containing exactly covered elements and that are subintervals of [0, n-2]), you are computing the range sum ls[left] + ls[left+1] + ... + ls[right]. Then you set ans to the minimum such range sum.

Currently, that nested loop takes O((n-covered)*covered)) steps, which is O(n^2) if covered is n/2, for example. You want a way to compute that range sum in constant time, eliminating the nested loop, to make the runtime O(n).

The easiest way to do this is with a prefix sum array. In Python, itertools.accumulate() is the standard/simplest way to generate those. To see how this helps:

Original Sum: ls[left] + ls[left+1] + ... + ls[right]

can be rewritten as the difference of prefix sums
   (ls[0] + ls[1] + ... + ls[right])
 - (ls[0] + ls[1] + ... + ls[left-1])

which is prefix_sum(0, right) - prefix_sum(0, left-1)
where are intervals are written in inclusive notation.

---

Pulling this into a separate range_sum() function, you can rewrite the original core logic block as:

prefix_sums = list(itertools.accumulate(ls, initial=0))

def range_sum(left: int, right: int) -> int:
    """Given indices left and right, returns the sum of values of
    ls in the inclusive interval [left, right].
    Equivalent to sum(ls[left : right+1])"""

    return prefix_sums[right+1] - prefix_sums[left]
    
ans = 1000000001
for i in range(n - covered):
    a = range_sum(left=i, right=i+covered-1)
    if a < ans:
        ans = a

The trickiest part of prefix sum arrays is just avoiding off-by-one errors in indexes. Notice that our prefix sum array of the length-n array ls has n+1 elements, since it starts with the empty initial prefix sum of 0, and so we add 1 to array accesses to prefix_sums compared to our formula.

Also, it's possible there may be an off-by-one error in your original code, as the value ls[n-1] is never accessed or used for anything after being set?