А. Задача Бендера.

Для начала поймем, что если мы прикрепляем прут к первому гвоздю, то остальные прутья мы сможем прикреплять только к третьему, пятому и т.д. Соответственно, если мы крепим прут ко второму гвоздю, то все остальные прутья мы можем крепить к четвертому, шестому и т.д. То есть либо мы крепим все прутья к гвоздям с четным номером, либо все к гвоздям с нечетным.

Если задача имеет решение, то нам надо выбрать к каким по четности гвоздям мы будем крепить прутья, а также поднабор из n / 2 прутьев, который и будет считаться ответом.

Если мы крепим j-ый прут к i-ому гвоздю, то len[j] = dist(i, i - 1) + dist(i, i + 1), где len[j] - длина j-ого прута, а dist(i, k) - расстояние между гвоздями с номерами i и k.

Ограничения задачи позволяли решать ее за O(nm).  Проходим внешним циклом по гвоздям, к которым будут крепиться пруты(сначала по гвоздям с четными номерами, потом по гвоздям с нечетными номерами), проходим внутренним циклом по прутьям и проверяем: можем ли мы прикрепить хотя бы один из оставшихся прутьев к текущему гвоздю. Если можем, то помечаем этот прут и далее его не рассматриваем, если нет, то проделываем то же самое для гвоздей с нечетными номерами, но при этом нужно снять все пометки с прутьев, сделанные при рассмотрении гвоздей с четными номерами. Если же и для нечетного случая мы не нашли ответ, то искомого поднабора не существует.

B. pSort.

Понятно, что мы можем поменять содержимое ячеек i и j, если |i - j| = d_i или |i - j| = d_j.

Переформулируем задачу: дана перестановка, нам надо ее отсортировать, используя заданные правила обменов, описанные выше.

Построим граф, вершинами в котором являются ячейки массива, а ребро существует между вершинами i и j, если возможен обмен между ними. Граф получаем неориентированный. То есть, если из вершины i в полученном графе достижима вершина j, то возможна такая серия обменов, что содержимое ячейки i поменяется с содержимым ячейки j.

Перестановку возможно отсортировать, если для всех i верно, что из вершины i достижима вершина p[i], где p - исходная перестановка.