Python Optimization

#1

Hello Community,

I have some code that works perfectly but for some large cases, it is too slow(python so expected).
Is there any way to optimize the code for better runtime? This is for USACO 2023 OPEN BRONZE P1

N = int(input())
S = list(input())

positions = [i for i in range(N) if S[i] == "F"]
binaryValue = [0 for i in range(len(positions))]
ans = []
value = 0

def funcRepeatInsForBin():
    binaryValue.insert(0, 0)
    if len(binaryValue) != len(positions) and len(binaryValue) > len(binaryValue):
        funcRepeatInsForBin()
    else:
        pass

for h in range(len(S)):
    if S[h] == "B":
        S[h] = int(0)
    elif S[h] == "E":
        S[h] = int(1)
    elif S[h] == "F":
        S[h] = int(2)

for k in range(pow(2,len(positions))):
    binaryValue = list(bin(k))
    binaryValue = binaryValue[2:]
    if len(binaryValue) != len(positions) or len(binaryValue) > len(binaryValue):
        funcRepeatInsForBin()
    for g in range(len(positions)):
        if g >= 0 and g < len(binaryValue):
            S[positions[g]] = int(binaryValue[g])
        else:
            S[positions[g]] = int(0)
    value = 0
    for u in range(len(S)-1):
        if S[u] == S[u+1]:
            value += 1
        else:
            pass
    ans.append(value)
    ans = list(set(ans))

print(len(ans))
for t in range(len(ans)):
    print(ans[t])
#2

Big problem: it says “for k in range(pow(2, len(positions))”: Since len(positions) = N, that is 2 ** (10 ** 5)! Even worse, there are two for loops of time complexity O(N), making the total O(N * 2 ** N)! You probably have to completely change your code.

1 Like
#3

Is there anything I can do to make it run at least a bit faster?

#4

Maybe try using fast input: (add this to the start of your code)

import sys
input = sys.stdin.readline

#5

The algorithm will cause TLE no matter the language chosen. Attempting to reduce Python’s constant factor will not change the fact that for input cases 9-20 TLE would occur(due to Exponential time complexity).