Problem p02736 (python)

Fixed submission:
N = int(input())
a = input()

def is_combination_odd(n, r):
    _n = n
    _r = r
    is_odd = True
    while _n > 0 and _r > 0:
        if _n % 0b10 < _r % 0b10:
            is_odd = False
            break
        _n >>= 1
        _r >>= 1
    #print('n: %d, r: %d, is_odd: %d' % (n, r, is_odd))
    return is_odd
    
def is_ans_odd(num_str: str) -> bool:
    is_odd = False
    for i, c in enumerate(num_str):
        is_c_odd = int(c) % 2
        is_odd ^= is_combination_odd(len(num_str)-1, i) & is_c_odd
    return is_odd

def main():
    ans = -1
    table = str.maketrans({'1': '0', '2': '1', '3': '2'})
    a012 = a.translate(table)
    if is_ans_odd(a012):
        ans = 1
    else:
        if '1' in a012:
            ans = 0
        else:
            table = str.maketrans({'2': '1'})
            a01 = a012.translate(table)
            if is_ans_odd(a01):
                ans = 2
            else:
                ans = 0

    print(ans)

if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
class MemorizedFactorial:
    def __init__(self, n_max: int, *mv: (int)):
        # Check usage
        if len(mv) > 1:
            raise ValueError(f'Usage {self.__class__.__name__}(n_max[, m])')

        # Check arg value
        if n_max < 0:
            raise ValueError(f'Required n_max >= 0, n_max: {n_max}')
        m = None
        if len(mv) == 1:
            m = mv[0]
            if m < 0:
                raise ValueError(f'Require m >= 0, m: {m}')

        # List of n! mod m
        factv = [1] * (n_max+1)
        for i in range(2, n_max+1):
            if m:
                factv[i] = factv[i-1] * i % m
            else:
                factv[i] = factv[i-1] * i

        self._n_max = n_max
        self._m = m
        self._factv = factv

    # Return n! or n! mod m
    def factorial(self, n: int) -> int:
        if n > self._n_max:
            raise ValueError(f'n is larger than n_max, n: {n}, n_max: {self._n_max}')

        return self._factv[n]

import fractions

# WARN: Require mod number m is prime number
class MemorizedCombination:
    def __init__(self, n_max: int, *mv: (int)):
        # Check usage
        if len(mv) > 1:
            raise ValueError(f'Usage {self.__class__.__name__}(n_max[, m])')

        # Check arg value
        if n_max < 0:
            raise ValueError(f'Required n_max >= 0, n_max: {n_max}')
        m = None
        if len(mv) == 1:
            m = mv[0]
            # Condition of Fermat's little theorem
            if not (m > n_max and fractions.gcd(m, n_max) == 1):
                raise ValueError(f'Require m >= n_max and coprime, m: {m}, n_max: {n_max}')

        mem_fact = None
        mod_inv_factv = None
        if m:
            mem_fact = MemorizedFactorial(n_max, m)
            # List of inverse r! mod m
            mod_inv_factv = [1] * (n_max+1)
            mod_inv_factv[n_max] = pow(mem_fact.factorial(n_max), m-2, m)
            for i in range(n_max-1, 1, -1):
                mod_inv_factv[i] = mod_inv_factv[i+1] * (i+1) % m
        else:
            mem_fact = MemorizedFactorial(n_max)

        self._n_max = n_max
        self._m = m
        self._mem_fact = mem_fact
        self._mod_inv_factv = mod_inv_factv

    # Return nCr or nCr mod m
    def combination(self, n: int, r: int) -> int:
        # Check arg value
        if not (0 <= n and n <= self._n_max):
            raise Exception(f'Required 0 <= n <= n_max, n: {n}, n_max: {self._n_max}')
        if not (0 <= r and r <= n):
            raise Exception(f'Required 0 <= r <= n, r: {r}, n: {n}')

        m = self._m
        mem_fact = self._mem_fact
        mod_inv_factv = self._mod_inv_factv
        comb = None
        if m:
            comb = mem_fact.factorial(n) * mod_inv_factv[r] * mod_inv_factv[n-r] % m
        else:
            comb = mem_fact.factorial(n) // mem_fact.factorial(n-r) // mem_fact.factorial(r)

        return comb

N = int(input())
a = input()

memfact = MemorizedFactorial(N)
#memcomb = MemorizedCombination(N)

def is_ans_odd(num_str: str) -> bool:
    co_mod2 = 0
    for i, c in enumerate(num_str):
        x = int(c)
        co = memfact.factorial(len(num_str)-1) // memfact.factorial(len(num_str)-1-i) // memfact.factorial(i)
        #co = memcomb.combination(len(num_str)-1, i)
        co_mod2 += x*co
        co_mod2 %= 2

    is_odd = True
    if co_mod2 == 0:
        is_odd = False

    return is_odd

def main():
    ans = -1
    table = str.maketrans({'1': '0', '2': '1', '3': '2'})
    a012 = a.translate(table)
    if is_ans_odd(a012):
        ans = 1
    else:
        if '1' in a012:
            ans = 0
        else:
            table = str.maketrans({'2': '1'})
            a01 = a012.translate(table)
            if is_ans_odd(a01):
                ans = 2
            else:
                ans = 0

    print(ans)

if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
class MemorizedFactorial:
    def __init__(self, n_max: int, *mv: (int)):
        # Check usage
        if len(mv) > 1:
            raise ValueError(f'Usage {self.__class__.__name__}(n_max[, m])')

        # Check arg value
        if n_max < 0:
            raise ValueError(f'Required n_max >= 0, n_max: {n_max}')
        m = None
        if len(mv) == 1:
            m = mv[0]
            if m < 0:
                raise ValueError(f'Require m >= 0, m: {m}')

        # List of n! mod m
        factv = [1] * (n_max+1)
        for i in range(2, n_max+1):
            if m:
                factv[i] = factv[i-1] * i % m
            else:
                factv[i] = factv[i-1] * i

        self._n_max = n_max
        self._m = m
        self._factv = factv

    # Return n! or n! mod m
    def factorial(self, n: int) -> int:
        if n > self._n_max:
            raise ValueError(f'n is larger than n_max, n: {n}, n_max: {self._n_max}')

        return self._factv[n]

import fractions

# WARN: Require mod number m is prime number
class MemorizedCombination:
    def __init__(self, n_max: int, *mv: (int)):
        # Check usage
        if len(mv) > 1:
            raise ValueError(f'Usage {self.__class__.__name__}(n_max[, m])')

        # Check arg value
        if n_max < 0:
            raise ValueError(f'Required n_max >= 0, n_max: {n_max}')
        m = None
        if len(mv) == 1:
            m = mv[0]
            # Condition of Fermat's little theorem
            if not (m > n_max and fractions.gcd(m, n_max) == 1):
                raise ValueError(f'Require m >= n_max and coprime, m: {m}, n_max: {n_max}')

        mem_fact = None
        mod_inv_factv = None
        if m:
            mem_fact = MemorizedFactorial(n_max, m)
            # List of inverse r! mod m
            mod_inv_factv = [1] * (n_max+1)
            mod_inv_factv[n_max] = pow(mem_fact.factorial(n_max), m-2, m)
            for i in range(n_max-1, 1, -1):
                mod_inv_factv[i] = mod_inv_factv[i+1] * (i+1) % m
        else:
            mem_fact = MemorizedFactorial(n_max)

        self._n_max = n_max
        self._m = m
        self._mem_fact = mem_fact
        self._mod_inv_factv = mod_inv_factv

    # Return nCr or nCr mod m
    def combination(self, n: int, r: int) -> int:
        # Check arg value
        if not (0 <= n and n <= self._n_max):
            raise Exception(f'Required 0 <= n <= n_max, n: {n}, n_max: {self._n_max}')
        if not (0 <= r and r <= n):
            raise Exception(f'Required 0 <= r <= n, r: {r}, n: {n}')

        m = self._m
        mem_fact = self._mem_fact
        mod_inv_factv = self._mod_inv_factv
        comb = None
        if m:
            comb = mem_fact.factorial(n) * mod_inv_factv[r] * mod_inv_factv[n-r] % m
        else:
            comb = mem_fact.factorial(n) // mem_fact.factorial(n-r) // mem_fact.factorial(r)

        return comb

N = int(input())
a = input()

memcomb = MemorizedCombination(N)

def is_ans_odd(num_str: str) -> bool:
    co_mod2 = 0
    for i, c in enumerate(num_str):
        x = int(c)
        co = memcomb.combination(len(num_str)-1, i)
        co_mod2 += x*co
        co_mod2 %= 2

    is_odd = True
    if co_mod2 == 0:
        is_odd = False

    return is_odd

def main():
    ans = -1
    table = str.maketrans({'1': '0', '2': '1', '3': '2'})
    a012 = a.translate(table)
    if is_ans_odd(a012):
        ans = 1
    else:
        if '1' in a012:
            ans = 0
        else:
            table = str.maketrans({'2': '1'})
            a01 = a012.translate(table)
            if is_ans_odd(a01):
                ans = 2
            else:
                ans = 0

    print(ans)

if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
class MemorizedFactorial:
    def __init__(self, n_max: int, *mv: (int)):
        # Check usage
        if len(mv) > 1:
            raise ValueError(f'Usage {self.__class__.__name__}(n_max[, m])')

        # Check arg value
        if n_max < 0:
            raise ValueError(f'Required n_max >= 0, n_max: {n_max}')
        m = None
        if len(mv) == 1:
            m = mv[0]
            if m < 0:
                raise ValueError(f'Require m >= 0, m: {m}')

        # List of n! mod m
        factv = [1] * (n_max+1)
        for i in range(2, n_max+1):
            if m:
                factv[i] = factv[i-1] * i % m
            else:
                factv[i] = factv[i-1] * i

        self._n_max = n_max
        self._m = m
        self._factv = factv

    # Return n! or n! mod m
    def factorial(self, n: int) -> int:
        if n > self._n_max:
            raise ValueError(f'n is larger than n_max, n: {n}, n_max: {self._n_max}')

        return self._factv[n]

# WARN: Require mod number m is prime number
class MemorizedCombination:
    def __init__(self, n_max: int, *mv: (int)):
        # Check usage
        if len(mv) > 1:
            raise ValueError(f'Usage {self.__class__.__name__}(n_max[, m])')

        # Check arg value
        if n_max < 0:
            raise ValueError(f'Required n_max >= 0, n_max: {n_max}')
        m = None
        if len(mv) == 1:
            m = mv[0]
            if m < 2:
                raise ValueError(f'Require m >= 2, m: {m}')

        mem_fact = None
        mod_inv_factv = None
        if m:
            mem_fact = MemorizedFactorial(n_max, m)
            # List of inverse r! mod m
            mod_inv_factv = [1] * (n_max+1)
            mod_inv_factv[n_max] = pow(mem_fact.factorial(n_max), m-2, m)
            for i in range(n_max-1, 1, -1):
                mod_inv_factv[i] = mod_inv_factv[i+1] * (i+1) % m
        else:
            mem_fact = MemorizedFactorial(n_max)

        self._n_max = n_max
        self._m = m
        self._mem_fact = mem_fact
        self._mod_inv_factv = mod_inv_factv

    # Return nCr or nCr mod m
    def combination(self, n: int, r: int) -> int:
        # Check arg value
        if not (0 <= n and n <= self._n_max):
            raise Exception(f'Required 0 <= n <= n_max, n: {n}, n_max: {self._n_max}')
        if not (0 <= r and r <= n):
            raise Exception(f'Required 0 <= r <= n, r: {r}, n: {n}')

        m = self._m
        mem_fact = self._mem_fact
        mod_inv_factv = self._mod_inv_factv
        comb = None
        if m:
            comb = mem_fact.factorial(n) * mod_inv_factv[r] * mod_inv_factv[n-r] % m
        else:
            comb = mem_fact.factorial(n) // mem_fact.factorial(n-r) // mem_fact.factorial(r)

        return comb

N = int(input())
a = input()

memcomb = MemorizedCombination(N)

def is_ans_odd(num_str: str) -> bool:
    co_mod2 = 0
    for i, c in enumerate(num_str):
        x = int(c)
        co = memcomb.combination(len(num_str)-1, i)
        co_mod2 += x*co
        co_mod2 %= 2

    is_odd = True
    if co_mod2 == 0:
        is_odd = False

    return is_odd

def main():
    ans = -1
    table = str.maketrans({'1': '0', '2': '1', '3': '2'})
    a012 = a.translate(table)
    if is_ans_odd(a012):
        ans = 1
    else:
        if '1' in a012:
            ans = 0
        else:
            table = str.maketrans({'2': '1'})
            a01 = a012.translate(table)
            if is_ans_odd(a01):
                ans = 2
            else:
                ans = 0

    print(ans)

if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
class MemorizedFactorial:
    def __init__(self, n_max: int, *mv: (int)):
        # Check usage
        if len(mv) > 1:
            raise ValueError(f'Usage {self.__class__.__name__}(n_max[, m])')

        # Check arg value
        if n_max < 0:
            raise ValueError(f'Required n_max >= 0, n_max: {n_max}')
        m = None
        if len(mv) == 1:
            m = mv[0]
            if m < 0:
                raise ValueError(f'Require m >= 0, m: {m}')

        # List of n! mod m
        factv = [1] * (n_max+1)
        for i in range(2, n_max+1):
            if m:
                factv[i] = factv[i-1] * i % m
            else:
                factv[i] = factv[i-1] * i

        self._n_max = n_max
        self._m = m
        self._factv = factv

    # Return n! or n! mod m
    def factorial(self, n: int) -> int:
        if n > self._n_max:
            raise ValueError(f'n is larger than n_max, n: {n}, n_max: {self._n_max}')

        return self._factv[n]

# WARN: Require mod number m is prime number
class MemorizedCombination:
    def __init__(self, n_max: int, *mv: (int)):
        # Check usage
        if len(mv) > 1:
            raise ValueError(f'Usage {self.__class__.__name__}(n_max[, m])')

        # Check arg value
        if n_max < 0:
            raise ValueError(f'Required n_max >= 0, n_max: {n_max}')
        m = None
        if len(mv) == 1:
            m = mv[0]
            if m < 2:
                raise ValueError(f'Require m >= 2, m: {m}')

        mem_fact = None
        mod_inv_factv = None
        if m:
            mem_fact = MemorizedFactorial(n_max, m)
            # List of inverse r! mod m
            mod_inv_factv = [1] * (n_max+1)
            mod_inv_factv[n_max] = pow(mem_fact.factorial(n_max), m-2, m)
            for i in range(n_max-1, 1, -1):
                mod_inv_factv[i] = mod_inv_factv[i+1] * (i+1) % m
        else:
            mem_fact = MemorizedFactorial(n_max)

        self._n_max = n_max
        self._m = m
        self._mem_fact = mem_fact
        self._mod_inv_factv = mod_inv_factv

    # Return nCr or nCr mod m
    def combination(self, n: int, r: int) -> int:
        # Check arg value
        if not (0 <= n and n <= self._n_max):
            raise Exception(f'Required 0 <= n <= n_max, n: {n}, n_max: {self._n_max}')
        if not (0 <= r and r <= n):
            raise Exception(f'Required 0 <= r <= n, r: {r}, n: {n}')

        m = self._m
        mem_fact = self._mem_fact
        mod_inv_factv = self._mod_inv_factv
        comb = None
        if m:
            comb = mem_fact.factorial(n) * mod_inv_factv[r] * mod_inv_factv[n-r] % m
        else:
            comb = mem_fact.factorial(n) // mem_fact.factorial(n-r) // mem_fact.factorial(r)

        return comb

N = int(input())
a = input()

memcomb = MemorizedCombination(N)

def is_ans_odd(num_str: str) -> bool:
    co_mod2 = 0
    for i, c in enumerate(num_str):
        x = int(c)
        co = memcomb.combination(len(num_str)-1, i)
        co_mod2 += x*co
        co_mod2 %= 2

    is_odd = True
    if co_mod2 == 0:
        is_odd = False

    return is_odd

def main():
    ans = -1
    table = str.maketrans({'1': '0', '2': '1', '3': '2'})
    a012 = a.translate(table)
    if is_ans_odd(a012):
        ans = 1
    else:
        if '1' in a012:
            ans = 0
        else:
            table = str.maketrans({'2': '1'})
            a01 = a012.translate(table)
            if is_ans_odd(a01):
                ans = 2
            else:
                ans = 0

    print(ans)

if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
import math
N = int(input())
a = input()

u = int(math.sqrt(N))
u2 = int(math.sqrt(u))
dic = {}
dic2 = {}

def calc(s: str) -> int:
    dp = [[0] * len(s) for i in range(len(s))]
    for i in range(len(s)):
        for j in range(len(s)-i):
            if i == 0:
                dp[i][j] = int(s[j])
            else:
                dp[i][j] = abs(dp[i-1][j] - dp[i-1][j+1])
    return dp[len(s)-1][0]

preva = a
for i in range(1, N//u):
    preva_list = []
    for j in range(N - (u-1)):
        s = preva[j:j+u]
        ans = 0

        if s in dic:
            ans = dic[s]
        else:
            #ans = calc(s)
            #dic[s] = ans

            #print('s: ', s)
            preva2 = s
            for i2 in range(1, u//u2):
                preva2_list = []
                for j2 in range(len(s) - (u2-1)):
                    s2 = preva2[j2:j2+u2]
                    ans2 = 0
                    if s2 in dic2:
                        ans2 = dic2[s2]
                    else:
                        ans2 = calc(s2)
                        dic2[s2] = ans2
                    preva2_list.append(str(ans2))
                    #print('s2: ', s2)
                    #print('ans2: ', ans2)
                preva2 = ''.join(preva2_list)
            ans = calc(preva2)
            dic[s] = ans
            #print('ans: ', ans)

        preva_list.append(str(ans))
    preva = ''.join(preva_list)

ans = calc(preva)
print(ans)