Problem p03137 (python)

Fixed submission:
import math
import sys
from heapq import heappush, heappop


def solution(arr, moves):
    if len(arr) <= moves:
        return 0

    arr.sort()
    if moves == 1:
        return abs(arr[0] - arr[-1])

    heapq_max = []
    # place them then scan the array
    # right side of longest interval

    for i in range(0, len(arr) - 1):
        heappush(heapq_max, (-abs(arr[i] - arr[i + 1] ), i , i + 1))

    placed = [0]
    for _ in range(moves - 1):
        val = heappop(heapq_max)
        placed.append(val[2])

    placed.sort()
    counter = 0
    for i in range(len(placed) - 1):
        if (abs(placed[i] -  placed[i + 1]) > 1):
            counter += abs(arr[placed[i]] - arr[placed[i + 1] - 1])
    if placed[-1] != len(arr) - 1:
        counter += abs(arr[placed[-1]] - arr[-1])
    return counter

    # visited = {}
    # current_positions = {}
    #
    # for i in list(reversed(sorted(d, key=lambda x: x[1])))[:moves]:
    #     visited[i[0]] = True
    #     current_positions[i[0]] = True
    #
    # counter = 0
    # while len(visited) < len(arr):
    #     min_on_position = sys.maxsize
    #     minimum_element = None
    #     side = None
    #     for i in current_positions:
    #         if i - 1 not in visited and i > 0:
    #             if min_on_position > abs(arr[i - 1] - arr[i]):
    #                 min_on_position = abs(arr[i - 1] - arr[i])
    #                 minimum_element = i
    #                 side = i - 1
    #
    #         if i + 1 not in visited and i < len(arr) - 1:
    #             if min_on_position > abs(arr[i + 1] - arr[i]):
    #                 min_on_position = abs(arr[i + 1] - arr[i])
    #                 minimum_element = i
    #                 side = i + 1
    #
    #
    #     current_positions[side] = True
    #     visited[side] = True
    #     counter += abs(arr[minimum_element] - arr[side])
    #
    # return counter

for i,line in enumerate(sys.stdin):
    if i == 0:
       M, N = line.split(" ")
    if i == 1:
        A = [int(i) for i in line.split(" ")]
        print(solution(A, int(M)))

# line = "-10 -3 0 9 -100 2 17"
#
# lines = [int(i) for i in line.split(" ")]
# a = [10,12,1,2,14]
# b = [-100000]
# print(solution(lines, 3))
# print(solution(a, 2))
# print(solution(b, 1))

Buggy submission (verdict: Runtime Error):
import math
import sys


def solution(arr, moves):
    if len(arr) <= moves:
        return 0

    arr.sort()
    if moves == 1:
        return abs(arr[0] - arr[-1])

    diff = [None] * len(arr)
    diff[0] = abs(arr[0] - arr[1])
    diff[-1] = abs(arr[-2] - arr[-1])
    for i in range(1, len(arr) - 1):
        diff[i] = abs(arr[i] - arr[i - 1]) if  abs(arr[i] - arr[i - 1]) > abs(arr[i] - arr[i + 1]) else abs(arr[i] - arr[i + 1])
    d = enumerate(diff)

    visited = {}
    current_positions = {}

    for i in list(reversed(sorted(d, key=lambda x: x[1])))[:moves]:
        visited[i[0]] = True
        current_positions[i[0]] = True

    counter = 0
    while len(visited) < len(arr):
        min_on_position = sys.maxsize
        minimum_element = None
        side = None
        for i in current_positions:
            if i - 1 not in visited and i > 0:
                if min_on_position > abs(arr[i - 1] - arr[i]):
                    min_on_position = abs(arr[i - 1] - arr[i])
                    minimum_element = i
                    side = i - 1

            if i + 1 not in visited and i < len(arr) - 1:
                if min_on_position > abs(arr[i + 1] - arr[i]):
                    min_on_position = abs(arr[i + 1] - arr[i])
                    minimum_element = i
                    side = i + 1


        current_positions[side] = True
        visited[side] = True
        counter += abs(arr[minimum_element] - arr[side])

    return counter

for i,line in enumerate(sys.stdin):
    if i == 0:
        N, M = int(line.split(" "))
    if i == 1:
        A = [int(i) for i in line.split(" ")]
        solution(A, M)

# line = "-10 -3 0 9 -100 2 17"
#
# lines = [int(i) for i in line.split(" ")]
# print("before")
# a = [10,12,1,2,14]
# b = [-100000]
# print(solution(lines, 3))
# print(solution(a, 2))
# print(solution(b, 1))

Buggy submission (verdict: Runtime Error):
import math
import sys


def solution(arr, moves):
    if len(arr) <= moves:
        return 0

    arr.sort()
    diff = [None] * len(arr)
    diff[0] = abs(arr[0] - arr[1])
    diff[len(arr) - 1] = abs(arr[len(arr) - 2] - arr[len(arr) - 1])
    for i in range(1, len(arr) - 1):
        diff[i] = abs(arr[i] - arr[i - 1]) if  abs(arr[i] - arr[i - 1]) > abs(arr[i] - arr[i + 1]) else abs(arr[i] - arr[i + 1])
    d = enumerate(diff)
    visited = {}
    current_positions = {}
    for i in list(reversed(sorted(d, key=lambda x: x[1])))[:moves]:
        visited[i[0]] = True
        current_positions[i[0]] = True
    counter = 0
    while len(visited) < len(arr):
        min_on_position = sys.maxsize
        minimum_element = None
        side = None
        for i in current_positions:
            if i - 1 not in visited and i > 0:
                if min_on_position > abs(arr[i - 1] - arr[i]):
                    min_on_position = abs(arr[i - 1] - arr[i])
                    minimum_element = i
                    side = "Left"

            if i + 1 not in visited and i < len(arr) - 1:
                if min_on_position > abs(arr[i + 1] - arr[i]):
                    min_on_position = abs(arr[i + 1] - arr[i])
                    minimum_element = i
                    side = "Right"

        del current_positions[minimum_element]
        if side == "Left":
            current_positions[minimum_element - 1] = True
            visited[minimum_element - 1] = True
            counter += abs(arr[minimum_element] - arr[minimum_element - 1])
        else:
            current_positions[minimum_element + 1] = True
            visited[minimum_element + 1] = True
            counter += abs(arr[minimum_element] - arr[minimum_element + 1])

    return counter


for i,line in enumerate(sys.stdin):
    if i == 0:
        M, N = line.split(" ")
    if i == 1:
        A = [int(i) for i in line.split(" ")]
        print(solution(A, int(M)))