Problem p03309 (python)

Fixed submission:
N = int(input())
A = [int(i) for i in input().split()]
def calc_sadness(points, b):
    return sum([abs(y - (b + x)) for x, y in points])

points = [(i+1, y) for i, y in enumerate(A)]

# y = x + b
# b = y - x
b_list = [y - x for x, y in points]
b_list.sort(reverse=True)

max_b = b_list[0]
min_b = b_list[-1]

best_ind = len(b_list)//2

minimum = calc_sadness(points, b_list[best_ind])

print(minimum)

Buggy submission (verdict: Runtime Error):
N = int(input())
A = [int(i) for i in input().split()]

def calc_sadness(points, b):
    return sum([abs(y - (b + x)) for x, y in points])

# y = x + b
# b = y - x
b_list = [y - x for x, y in points]
b_list.sort(reverse=True)


max_b = b_list[0]
min_b = b_list[-1]


def search(max_b, min_b):

    eval_max = eval_sadness(points, max_b)
    eval_min = eval_sadness(points, min_b)
    
    if max_b == min_b + 1:     # neighbors
        return min(eval_max, eval_min)
    
    mid_b = (max_b + min_b) // 2
    eval_mid = eval_sadness(points, mid_b)

    minimum = min(eval_max, eval_mid, eval_min)
    #print(eval_mid)

    if minimum == eval_max:
        return eval_max
    elif minimum == eval_min:
        return eval_min
    else:
        return min(search(max_b, mid_b), search(mid_b, min_b))

if max_b == min_b:
    print(calc_sadness(points, min_b))
else:
    print(search(max_b, min_b))

Buggy submission (verdict: Runtime Error):
def calc_sadness(points, b):
    return sum([abs(y - (b + x)) for x, y in points])

N = int(input())
A = [int(i) for i in input().split()]

points = [(i+1, y) for i, y in enumerate(A)]

b_list = [y - x for x, y in points]
b_list.sort(reverse=True)

sad_list = [(b, calc_sadness(points, b)) for b in b_list]
sad_list.sort(key=lambda x:x[1])

peak_sads = sorted(sad_list[:2], key=lambda x:x[0])

min_sad = 10000000000
for b in range(peak_sads[0][0], peak_sads[1][0]+1):
    sadness = calc_sadness(points, b)
    if sadness < min_sad:
        min_sad = sadness

print(min_sad)

Buggy submission (verdict: Runtime Error):
def calc_sadness(points, b):
    return sum([abs(y - (b + x)) for x, y in points])

N = int(input())
A = [int(i) for i in input().split()]

points = [(i+1, y) for i, y in enumerate(A)]

b_list = [y - x for x, y in points]
b_list.sort(reverse=True)

sad_list = [(b, calc_sadness(points, b)) for b in b_list]
sad_list.sort(key=lambda x:x[1])

peak_sads = sorted(sad_list[:2], key=lambda x:x[0])
    
sadness_list = [calc_sadness(points, b) for b in range(peak_sads[0][0], peak_sads[1][0]+1)]

print(min(sadness_list))

Buggy submission (verdict: Runtime Error):
def calc_sadness(points, b):
    return sum([abs(y - (b + x)) for x, y in points])

N = int(input())
A = [int(i) for i in input().split()]

points = [(i+1, y) for i, y in enumerate(A)]

b_list = [y - x for x, y in points]
b_list.sort(reverse=True)

sad_list = [(b, calc_sadness(points, b)) for b in b_list]
sad_list.sort(key=lambda x:x[1])

peak_sads = sorted(sad_list[:2], key=lambda x:x[0])

sadness_list = []
for b in range(peak_sads[0][0], peak_sads[1][0]+1):
    sadness_list.append(calc_sadness(points, b))

print(min(sadness_list))

Buggy submission (verdict: Runtime Error):
def calc_sadness(points, b):
    return sum([abs(y - (b + x)) for x, y in points])

N = int(input())
A = [int(i) for i in input().split()]

points = [(i+1, y) for i, y in enumerate(A)]

b_list = [y - x for x, y in points]
b_list.sort(reverse=True)

sad_list = [(b, calc_sadness(points, b)) for b in b_list]
sad_list.sort(key=lambda x:x[1])

peak_sads = sorted(sad_list[:2], key=lambda x:x[0])

sadness_list = []
for b in range(peak_sads[0][0], peak_sads[1][0]+1):
    sadness_list.append(calc_sadness(points, b))

print(min(sadness_list))