def memoized_matrix_chain(p):
    n = p.length - 1
    m = Array([Array.indexed(1, n) for _ in between(1, n)])
    for i in between(1, n):
        for j in between(i, n):
            m[i, j] = math.inf
    return lookup_chain(p, m, 1, n)

def merge_(A, p, q, r):
    n1 = q - p + 1
    n2 = r - q
    L = Array.indexed(1, n1)
    R = Array.indexed(1, n2)
    for i in between(1, n1):
        L[i] = A[p + i - 1]
    for j in between(1, n2):
        R[j] = A[q + j]
    i = j = 1
    k = p
    while i <= n1 and j <= n2:
        if L[i] <= R[j]:
            A[k] = L[i]
            i = i + 1
        else:
            A[k] = R[j]
            j = j + 1
        k = k + 1
    while i <= n1:
        A[k] = L[i]
        i = i + 1
        k = k + 1
    while j <= n2:
        A[k] = R[j]
        j = j + 1
        k = k + 1

def young_sort(A):
    n = int(math.sqrt(A.length))
    Y = Matrix([[math.inf] * n] * n)
    for i in between(1, n ** 2):
        young_insert(Y, n, n, A[i])
    for i in between(1, n ** 2):
        A[i] = young_extract_min(Y, n, n, 1, 1)

def tasks_independent_bruteforce(deadlines):
    n = deadlines.length
    N = Array([len([d for d in deadlines if d <= t]) for t in between(1, n)])
    for t in between(1, n):
        if N[t] > t:
            return False
    return True

def memoized_lcs_length(X, Y):
    m = X.length
    n = Y.length
    c = Array([Array.indexed(0, n) for _ in between(0, m)], start=0)
    for i in between(0, m):
        for j in between(0, n):
            c[i, j] = math.inf
    return lookup_lcs(c, X, Y, m, n)

def knapsack_bruteforce(w, v, W):
    max_value = 0
    n = w.length
    for m in between(1, n):
        for item_ids in itertools.combinations(between(1, n), m):
            if items_total_weight(item_ids, w) <= W:
                max_value = max(max_value, items_total_value(item_ids, v))
    return max_value

def selection_sort(A):
    n = A.length
    for j in between(1, n - 1):
        min = j
        for i in between(j + 1, n):
            if A[i] < A[min]:
                min = i
        A[min], A[j] = A[j], A[min]

def activity_selector_bruteforce(s, f):
    n = s.length - 2
    max_size = 0
    for m in between(1, n):
        for activities_ids in itertools.combinations(between(1, n), m):
            if activities_compatible(activities_ids, s, f):
                max_size = max(max_size, m)
    return max_size

def bucket_sort(A):
    n = A.length
    B = Array([[] for _ in range(n)], start=0)
    for i in between(1, n):
        B[math.floor(n * A[i])].append(A[i])
    for i in between(0, n - 1):
        _insertion_sort_list(B[i])
    _concatenate_lists(B, A)

def get_shortest_bitonic_path_length_bruteforce(points):
    n = points.length
    min_length = math.inf
    for k in between(0, n - 2):
        for right_path in itertools.combinations(between(2, n - 1), k):
            left_path = [x for x in rbetween(n - 1, 2) if x not in right_path]
            path_length = get_path_length(points, [1] + list(right_path) + [n] + left_path + [1])
            min_length = min(min_length, path_length)
    return min_length

def polynomial_evaluate(a, x):
    y = 0.0
    n = a.length - 1
    for i in between(0, n):
        s = a[i]
        for j in between(1, i):
            s = s * x
        y = y + s
    return y

def refueling_bruteforce(stations, n):
    min_stops = math.inf
    m = stations.length
    for nstops in between(0, m):
        for stops in itertools.combinations(between(1, m), nstops):
            if stops_valid(stops, stations, n):
                min_stops = min(min_stops, nstops)
                break
    return min_stops

def binary_add(A, B):
    n = A.length
    C = Array.indexed(1, n + 1)
    for i in between(1, n + 1):
        C[i] = 0
    for i in between(1, n):
        sum = A[i] + B[i] + C[i]
        C[i] = sum % 2
        C[i + 1] = math.floor(sum / 2)
    return C

def max_overlapping_activities(s, f):
    n = s.length
    max_overlaps = 0
    for i in between(1, n):
        overlaps = 0
        for j in between(1, n):
            if s[j] <= s[i] < f[j]:
                overlaps += 1
        max_overlaps = max(max_overlaps, overlaps)
    return max_overlaps

def get_probabilities_for_optimal_bst():
    n = random.randint(1, 10)
    p, _ = get_random_array(min_size=n, max_size=n)
    q, _ = get_random_array(min_size=n + 1, max_size=n + 1)
    q.start = 0
    total = sum([x for x in p.elements + q.elements])
    for i in between(1, n):
        p[i] /= total
    for i in between(0, n):
        q[i] /= total
    return p, q

def make_change(n, d):
    c = Array.indexed(0, n)
    denom = Array.indexed(1, n)
    c[0] = 0
    for j in between(1, n):
        c[j] = math.inf
        for i in between(1, d.length):
            if j >= d[i] and 1 + c[j - d[i]] < c[j]:
                c[j] = 1 + c[j - d[i]]
                denom[j] = d[i]
    return c, denom

def counting_sort(A, B, k):
    C = Array.indexed(0, k)
    for i in between(0, k):
        C[i] = 0
    for j in between(1, A.length):
        C[A[j]] = C[A[j]] + 1
    for i in between(1, k):
        C[i] = C[i] + C[i - 1]
    for j in rbetween(A.length, 1):
        B[C[A[j]]] = A[j]
        C[A[j]] = C[A[j]] - 1

def matrix_multiply(A, B):
    if A.columns != B.rows:
        raise RuntimeError('incompatible dimensions')
    else:
        C = Matrix.of_dimensions(A.rows, B.columns)
        for i in between(1, A.rows):
            for j in between(1, B.columns):
                C[i, j] = 0
                for k in between(1, A.columns):
                    C[i, j] = C[i, j] + A[i, k] * B[k, j]
        return C

def josephus_simulate(n, m):
    L = List()
    singly_linked_list_insert(L, SNode(n))
    x = L.head
    for i in rbetween(n - 1, 1):
        singly_linked_list_insert(L, SNode(i))
    x.next = L.head
    for i in between(1, n):
        for j in between(1, m):
            x = x.next
        print(x.next.key)
        if L.head is x.next:
            L.head = x.next.next
        x.next = x.next.next

    def test_print_optimal_parens(self):
        n = random.randint(1, 10)
        s = Array([Array.indexed(1, n) for _ in between(1, n)])
        for i in between(1, n - 1):
            for j in between(i + 1, n):
                s[i, j] = random.randint(i, j - 1)
        captured_output = io.StringIO()

        with redirect_stdout(captured_output):
            print_optimal_parens(s, 1, n)

        actual_output = captured_output.getvalue().splitlines()[0]
        expected_output = get_optimal_parens_bruteforce(s, 1, n)
        assert_that(actual_output, is_(equal_to(expected_output)))