Wataru

if i == middle - 1 or i >= 5 and len(list) <= 4:
            return -1

Вот эта часть вызвает вопросы. Отладочный код остался?

Проблема в вашем коде, что он виснет, если числа в массиве вообще нет. Условие должно быть не про равенство, а про то, что у вас отрезок пуст (или длины 1) - надо сравнивать first и last.

Обычно middle не поддерживают между итерациями цикла, а просто считают внутри. Между итерациями переходят только first и last.

А так, да, бинпоиск - это весьма простой алгоритм.

Для такой вот работы идеально подходят связные списки. Там можно менять объект не портя никакие итераторы. Проблема только в том, что связные списки в питоне не реализованы на уровне языка. Поищите реализацию, наверняка есть удобный модуль со списками.

Еще можноиспользовать обычный list, только вы итерируйтесь циклом while и используйте индексы:

i = 0
while i < len(arr):
  x = arr[i]
  j = i+1
  while j < len(arr):
    if ShouldDelete(arr[j], arr[i]):
      del a[j]

Это будет в n раз медленнее, к сожалению. Можно наверно слайсами сделать быстрее:

arr[i+1:] = y for y in arr[i+1:] if not ShouldDelete(x, arr[i])

Я не питонист и возможно ошибку допустил. И мне этот код не кажктся очень понятным, но возможно это истиный путь для питона.

А так, в общем случае, идет двойная итерация с пометками элементов на удаление.

Какого-то названия этот прием не имеет, ибо это костыль для конкретных реализаций контейнеров.

Формула включения-исключения. Берете все графы, где хотя бы одна вершина соединена со всеми (их n*2^(n-2)*(n-1)), вычитаете все графы, где хотя бы две вершины соеденины со всеми (2 раза, ведь они 2 раза подсчитались), прибавляете графы, где хотя бы 3 вершины соеденины со всеми (3 раза)... И т.д.

Графов, где хотя бы k вершин имеют степень n-1 - C(n, k)*2^{(n-k-1)(n-k)/2}: тут можно выбрать k вершин и для каждого ребра из оставшихся n-k вершин есть 2 варианта - оно или есть, или нет.

Это будет за O(n log n) решение, если пердподсчитать все факториалы и обратные к им по модулю в задаче. Ну, или O(n^2), если считать сочетания через треугольник паскаля.

Ражеванное объяснение:

Сложно подсчитать количество графов где ровно 1 вершина такая полная. Но легко подсчитать те, где k или более таких. Мы их такие зафиксируем и нарисуем от них все ребра. А все оставшиеся ребра в графе могут быть любыми. Во-первых, можно выбрать эти k вершин - поэтому у нас есть множитель C[n,k]. Оставшиеся, незафиксированные ребра идут между любыми двумя оставшимся n-k вершин. Их (n-k)(n-k-1)/2. И каждое может быть или проведено или нет.

Поэтому всего таких графов, с не менее k вершин: F(k)=C[n,k]*2^{(n-k)(n-k-1)/2}.

Теперь, как подсчитать графы ровно с 1 вершиной? Можно взять F(1). Но мы насчитали много лишнего, Графы с 2мя такими вершинами мы в F(1) подсчитали 2 раза. Поэтому вычтем 2F(2). Теперь графы ровно с 3 вершинами мы подсчитали 3 раза в F(1) и 3 раза в каждом F(2). Поэтому пока мы их насчитали 3-2*3 = -3 раза. Поэтому прибавим 3F(3). И далее, получится, что графы ровно с 4-мя вершинами мы подсчитали 4 раза (4-2*6+3*4). И т.д.

Посмотрите на ограничения в задаче. Введите вашей программе максимальный тест: 15 монеток и сумму примерно в 1000000000. Ваша программа попробует съесть дюжину гигабайт памяти и упадет.

У вас решениe за O(n^3), ибо у вас там 2 вложенных цикла до n, а внутри еще и постоянно вызываются min/max, которые проходятся по всему массиву.

Ограничения же в задаче n<10^5. С такими ограничениями максимум O(n log n) решение уложится в 3 секунды.

Подумайте, как его можно изменить, чтобы работало сильно быстрее? Подсказка: сначала вы берете 1 минимальный элемент, потом 2 самых маленьких, потом 3, и т.д. На второй итерации вам уже как бы не надо искать минимум- вы его уже знаете. Вас интересуют только оставшиеся числа. На третьей итерации у вас уже 2 числа раньше найдены. Надо как-то переиспользовать предыдущие вычисления.

Что можно сделать с входным массивом, чтобы можно было получать несколько самых маленьких элементов быстро? Помните, что вам надо уложиться в O(n log n).

У вас все равно полный перебор, можно через itertools.combinations перебирать сочетания из заданного количества имеющихся чисел, считать их сумму и, если совпало, выводить. Там всего один цикл, буквально 4 строчки будет решение.

Но это может работать даже медленнее на некоторых входных данных чем проверка в конце вашего рекурсивного перебора, ибо тут нет ранних отсечений: вы будете перебирать заведомо большие искомой суммы.

Более хитрые и быстрые варианты: динамическое программирование типа задачи о рюкзаке, где вы считаете количество способов набрать такую-то сумму стольки-то слагаемыми из стольки-то первых чисел. А потом используя это в рекурсивном переборе можно отрубать его тупиковые ветви: если ДП говорит, что там 0 наборов, то можно туда не идти в рекурсии. Или, если вам не сами наборы, а из количество нужно, то даже рекурсивного перебора не надо. Но это работает, только если target не очень большое.

Второй более быстрый вариант: получить хоть бы и вашим перебором все варианты собрать все суммы среди первых n/2 чисел и отдельно среди оставшихся. Их надо распихать по разным массивам, в зависимости от количества слагаемых. Отсортировать по сумме. Потом перебрать, сколько чисел берем из первой половины, тогда понятно, сколько берем из второй. А потом двумя указателями, идущими навстречу в этих двух упорядоченных массивах можно за один проход найти все способы скомбинировать пару чисел из двух массивов, дающую искомую сумму.

Например, вот так:

def GenerateAll(source, rep):
  for comb in itertools.combinations(range(len(source)), len(source)-len(rep)):
    s = list()
    prev = 0
    for (i, j) in enumerate(comb):
      s.append(source[j]);
    yield "".join(s)

Обратите внимание, перебираем не сочетания из удаляемых позиций, а из 22 оставляемых (кстати, у вас числа не бьются, 48+22 = 60 != 64). Тут порядок в ответе будет обратный (первая строка будет "xxxxxx...xxxx12..." а не "12..xxx..xx". Если нужен тот же порядок, то будет чуть сложнее:

def GenerateAll(source, rep):
  for comb in itertools.combinations(range(len(source)), len(rep)):
    s = list()
    prev = 0
    last = 0
    for (i, j) in enumerate(comb):
      while (last < j):
          s.append(source[last]);
          last += 1
      last += 1
    while (last < len(source)):
          s.append(source[last]);
          last += 1
    yield "".join(s)

Это не самое питонистое решение, возможно в какой-то библиотеке уже есть готовая функция, которая вырезает из строки символы по индексам.

Надо, чтобы "четность" перестановки совпадала с четностью финального поля (1).
Занумеруйте все 16 позиций слева направо сверху вниз.
чтобы подсчитать четность, рассматривайте каждую пару заполненных позиций (15\*14/2=105 пар) - если числа идут не в том порядке (большее число на позиции с меньшим номером) - то прибавьте 1 к ответу. В конце возьмите ответ по модулю 2. Это и будет четность перестановки.

Чтобы получить поле, которое можно собрать, сгенерируйте любую перестановку (случайно перемешайте 15 чисел), а потом посчитайте ee четность. Если четность плохая, то поменйте местами любые 2 соседних элемента (выберите случайно, или меняйте первые 2 всегда - на вероятности всех возможных полей это не влияет).

Edit: Но вы это почти все итак знатете, ибо функция is_solvable в вашем коде как раз инверсии уже считает.
Значит, Но вы знаете, что плохое поле от хорошего отличается лишь четностью, значит, если поле плохое - меняйте местами 2 соседних по порядку элемента. Например верхний левый со вторым в верхней строке.

Это все ссылки. Вершина хранит ссылки на ребра, ребра хранят ссылки на вершины. Поэтому эта вложенность не страшна. Она - головная боль сборщика мусора (так называется часть менеджера памяти, которая освобождает ненужную больше память).

Я бы действительно не вводил сущность ребро. И просто в вершинах хранил список соседних вершин (оно еще называется список смежности). Так экономнее, быстрее и проще.

В вашем подходе, чтобы получить соседнюю вершину надо взять ребро и посмотреть, какая их двух вершин не та изначальная. Или можно хранить только ориентированные ребра и все неориентированные придется раздваивать.