On the last coding contest, there was the following problem: https://codeforces.com/contest/1916/problem/C

To solve it, I needed to run through the given array once and print the resulting array. I decided to use the For loop, at each step of which I was appending an element to the resultant list and after it I was printing the list out.

That solution exceeded the time limit, so I decided to abstain from using Append, and was populating the pre-created list instead.

That solution also exceeded the time limit, so I decided to avoid the Print part as it also has O(n) complexity, and was printing the result of each step within the For loop. However, even that did not suffice to fit into the time limit.

So, my question is “is it Python that is too slow (I did hear some people saying that Python is not a good choice for competitive programing) or I could have optimized something further to speed up my code?”

Here is the initial code I used where I was updating the list at each step of For loop and printing the resultant list once the For loop is complete:

    t = int(input())
    for _ in range(t):
        n = int(input())
        v = list(map(int, input().split()))
        if n == 1:
            print(v[0])
        elif n == 2:
            print(v[0], int((v[1] + v[0])/2) * 2)
        else:
            w = [0 for l in range(n)]
            w[0] = v[0]
            w[1] = int((v[1] + v[0])/2) * 2
            c = 0
            if v[0] % 2:
                c += 1
            if v[1] % 2:
                c += 1
            b = 0
            for k in range(2, n):
                if v[k] % 2:
                    c += 1
                b = int(c // 3)
                if c % 3 == 1:
                    b += 1
                w[k] = (sum(v[:k + 1]) - b)
            print(*w)

And here is the code, where I was printing the result of each step within the For loop, hence the time complexity of this code is a pure O(n), since I only go through the given list once:

    t = int(input())
    for _ in range(t):
        n = int(input())
        v = list(map(int, input().split()))
        if n == 1:
            print(v[0])
        elif n == 2:
            print(v[0], int((v[1] + v[0])/2) * 2)
        else:
            w = [0 for x in range(n)]
            w[0] = v[0]
            print(w[0], end=" ")
            w[1] = int((v[1] + v[0])/2) * 2
            print(w[1], end=" ")
            c = 0
            if v[0] % 2:
                c += 1
            if v[1] % 2:
                c += 1
            b = 0
            for k in range(2, n):
                if v[k] % 2:
                    c += 1
                b = int(c // 3)
                if c % 3 == 1:
                    b += 1
                w[k] = (sum(v[:k + 1]) - b)
                if k == n - 1:
                    print(w[k])
                else:
                    print(w[k], end=" ")

any suggestions are highly appreciated. It feels like the problem is not in the algorithm itself, but the data structures I used. However, it’s just my hunch.