Problem p03291 (python)

Fixed submission:
import sys

S = input()

DEVIDER = 10**9 + 7


def add(a, b):
    return (a + b) % DEVIDER

def mul(a, b):
    return (a % DEVIDER) * (b % DEVIDER) % DEVIDER

cache = [[0 for _ in range(4)] for _ in range(len(S) + 1)]
cache[0][0] = 1


def check(s, j):
    if j == 0 and s == 'A':
        return True
    if j == 1 and s == 'B':
        return True
    if j == 2 and s == 'C':
        return True
    return False


for i in range(len(S)):
    for j in range(4):
        if S[i] == '?':
            cache[i + 1][j] += 3 * cache[i][j]
        else:
            cache[i + 1][j] += cache[i][j]
        if j > 0:
            if check(S[i], j-1) or S[i] == '?':
                cache[i+1][j] += cache[i][j - 1]
        cache[i+1][j] %= DEVIDER

print(cache[len(S)][3])

Buggy submission (verdict: Runtime Error):
import sys

S = input()

DEVIDER = 10**9 + 7


def add(a, b):
    return (a + b) % DEVIDER

def mul(a, b):
    return (a % DEVIDER) * (b % DEVIDER) % DEVIDER

cache = [[None for _ in range(4)] for _ in range(len(S) + 1)]


def check(s, j):
    if j == 0 and s == 'A':
        return True
    if j == 1 and s == 'B':
        return True
    if j == 2 and s == 'C':
        return True
    return False

def dp(i, j):
    if not cache[i][j] == None:
        return cache[i][j]

    if i == len(S) and j == 3:
        # end of task
        return 1
    elif i == len(S) and j < 3:
        # fail
        return 0
    elif i < len(S) and j == 3:
        # next
        if S[i] == "?":
            cache[i][j] = (3 * (dp(i + 1, 3) % DEVIDER)) % DEVIDER
            return cache[i][j]
        else:
            cache[i][j] = dp(i + 1, 3)
            return cache[i][j]
    else:
        # i < len(S) and j < 3
        if S[i] == "?":
            pre = (3 * (dp(i + 1, j) % DEVIDER)) % DEVIDER
            lat = dp(i + 1, j + 1)
            cache[i][j] = (pre + lat) % DEVIDER
            return cache[i][j]
        if check(S[i], j):
            cache[i][j] = (dp(i + 1, j) + dp( i + 1, j + 1)) % DEVIDER
            return cache[i][j]
        cache[i][j] = dp(i + 1, j)
        return cache[i][j]


ret = dp(0, 0)
print(ret)

Buggy submission (verdict: Runtime Error):
import sys
from functools import lru_cache

S = input()

DEVIDER = 10**9 + 7


def add(a, b):
    return (a + b) % DEVIDER

def mul(a, b):
    return (a % DEVIDER) * (b % DEVIDER) % DEVIDER


@lru_cache(maxsize=32)
def check(s, j):
    if j == 0 and s == 'A':
        return True
    if j == 1 and s == 'B':
        return True
    if j == 2 and s == 'C':
        return True
    return False

@lru_cache(maxsize=None)
def dp(i, j):
    if i == len(S) and j == 3:
        # end of task
        return 1
    elif i == len(S) and j < 3:
        # fail
        return 0
    elif i < len(S) and j == 3:
        # next
        if S[i] == "?":
            return (3 * (dp(i + 1, 3) % DEVIDER)) % DEVIDER
        else:
            return dp(i + 1, 3)
    else:
        # i < len(S) and j < 3
        if S[i] == "?":
            pre = (3 * (dp(i + 1, j) % DEVIDER)) % DEVIDER
            lat = dp(i + 1, j + 1)
            return (pre + lat) % DEVIDER
        if check(S[i], j):
            return (dp(i + 1, j) + dp( i + 1, j + 1)) % DEVIDER
        return dp(i + 1, j)


ret = dp(0, 0)
print(ret)

Buggy submission (verdict: Runtime Error):
import sys
from functools import lru_cache

S = input()

DEVIDER = 10**9 + 7


def add(a, b):
    return (a + b) % DEVIDER

def mul(a, b):
    return (a % DEVIDER) * (b % DEVIDER) % DEVIDER

cache_size = len(S) * 4

@lru_cache(maxsize=32)
def check(s, j):
    if j == 0 and s == 'A':
        return True
    if j == 1 and s == 'B':
        return True
    if j == 2 and s == 'C':
        return True
    return False

@lru_cache(maxsize=cache_size)
def dp(i, j):
    if i == len(S) and j == 3:
        # end of task
        return 1
    elif i == len(S) and j < 3:
        # fail
        return 0
    elif i < len(S) and j == 3:
        # next
        if S[i] == "?":
            return (3 * (dp(i + 1, 3) % DEVIDER)) % DEVIDER
        else:
            return dp(i + 1, 3)
    else:
        # i < len(S) and j < 3
        if S[i] == "?":
            pre = (3 * (dp(i + 1, j) % DEVIDER)) % DEVIDER
            lat = dp(i + 1, j + 1)
            return (pre + lat) % DEVIDER
        if check(S[i], j):
            return (dp(i + 1, j) + dp( i + 1, j + 1)) % DEVIDER
        return dp(i + 1, j)


ret = dp(0, 0)
print(ret)

Buggy submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(100000)
from functools import lru_cache

S = input()

DEVIDER = 10**9 + 7


def add(a, b):
    return (a + b) % DEVIDER

def mul(a, b):
    return (a % DEVIDER) * (b % DEVIDER) % DEVIDER

cache_size = len(S) * 4

@lru_cache(maxsize=32)
def check(s, j):
    if j == 0 and s == 'A':
        return True
    if j == 1 and s == 'B':
        return True
    if j == 2 and s == 'C':
        return True
    return False

@lru_cache(maxsize=cache_size)
def dp(i, j):
    if i == len(S) and j == 3:
        # end of task
        return 1
    elif i == len(S) and j < 3:
        # fail
        return 0
    elif i < len(S) and j == 3:
        # next
        if S[i] == "?":
            return mul(3,  dp(i + 1, 3))
        else:
            return dp(i + 1, 3)
    else:
        # i < len(S) and j < 3
        if S[i] == "?":
            return add(mul(3, dp(i + 1, j)),  dp(i + 1, j + 1))
        if check(S[i], j):
            return add(dp(i + 1, j), dp( i + 1, j + 1))
        return dp(i + 1, j)


ret = dp(0, 0)
print(ret)

Buggy submission (verdict: Runtime Error):
from functools import lru_cache

S = input()

DEVIDER = 10**9 + 7


def add(a, b):
    return (a + b) % DEVIDER

def mul(a, b):
    return (a % DEVIDER) * (b % DEVIDER) % DEVIDER

cache_size = len(S) * 4

@lru_cache(maxsize=32)
def check(s, j):
    if j == 0 and s == 'A':
        return True
    if j == 1 and s == 'B':
        return True
    if j == 2 and s == 'C':
        return True
    return False

@lru_cache(maxsize=cache_size)
def dp(i, j):
    if i == len(S) and j == 3:
        # end of task
        return 1
    elif i == len(S) and j < 3 :
        # fail
        return 0
    elif i < len(S) and j == 3:
        # next
        if S[i] == "?":
            return mul(3,  dp(i + 1, 3))
        else:
            return dp(i + 1, 3)
    else:
        # i < len(S) and j < 3
        if S[i] == "?":
            return add(mul(3, dp(i + 1, j)),  dp(i + 1, j + 1))
        if check(S[i], j):
            return add(dp(i + 1, j), dp( i + 1, j + 1))
        return dp(i + 1, j)


ret = dp(0, 0)
print(ret)

Buggy submission (verdict: Runtime Error):
from functools import lru_cache

S = input()

DEVIDER = 10**9 + 7


def add(a, b):
    return (a + b) % DEVIDER

def mul(a, b):
    return (a % DEVIDER) * (b % DEVIDER) % DEVIDER

@lru_cache(maxsize=32)
def check(s, j):
    if j == 0 and s == 'A':
        return True
    if j == 1 and s == 'B':
        return True
    if j == 2 and s == 'C':
        return True
    return False


@lru_cache()
def dp(i, j):
    if i == len(S) and j == 3:
        # end of task
        return 1
    elif i == len(S) and j < 3 :
        # fail
        return 0
    elif i < len(S) and j == 3:
        # next
        if S[i] == "?":
            return mul(3,  dp(i + 1, 3))
        else:
            return dp(i + 1, 3)
    else:
        # i < len(S) and j < 3
        if S[i] == "?":
            return add(mul(3, dp(i + 1, j)),  dp(i + 1, j + 1))
        if check(S[i], j):
            return add(dp(i + 1, j), dp( i + 1, j + 1))
        return dp(i + 1, j)


ret = dp(0, 0)
print(ret)

Buggy submission (verdict: Runtime Error):
S = input()

DEVIDER = 10**9 + 7


def add(a, b):
    return (a + b) % DEVIDER

def mul(a, b):
    return (a % DEVIDER) * (b % DEVIDER) % DEVIDER

def check(s, j):
    if j == 0 and s == 'A':
        return True
    if j == 1 and s == 'B':
        return True
    if j == 2 and s == 'C':
        return True
    return False


def dp(i, j):
    if i == len(S) and j == 3:
        # end of task
        return 1
    elif i == len(S) and j < 3 :
        # fail
        return 0
    elif i < len(S) and j == 3:
        # next
        if S[i] == "?":
            return mul(3,  dp(i + 1, 3))
        else:
            return dp(i + 1, 3)
    else:
        # i < len(S) and j < 3
        if S[i] == "?":
            return add(mul(3, dp(i + 1, j)),  dp(i + 1, j + 1))
        if check(S[i], j):
            return add(dp(i + 1, j), dp( i + 1, j + 1))
        return dp(i + 1, j)


ret = dp(0, 0)
print(ret)