codility_sulphur_2014.py

def check(A, B, C, index):
    totals = [0 for _ in xrange(index)]

    for i in xrange(index - 1, -1, -1):
        totals[i] += B[i]
        if C[i] != -1:
            totals[C[i]] += totals[i]

    return all([totals[i] <= A[i] for i in xrange(index)])


def solution(A, B, C):
    n = len(A)
    if n == 0:
        return 0
    low, high = 0, n

    while high - low > 1:
        mid = (low + high) / 2
        if check(A, B, C, mid):
            low = mid
        else:
            high = mid

    if check(A, B, C, high):
        return high
    else:
        return low