Олимпиадная задачка на python

Рейтинг: -1Ответов: 1Опубликовано: 20.04.2023

Мой код возвращает очень близкие к ответам значения, но где-то есть прокол, не могу его найти.

def distances_sum(length: int, arr: list[int]) -> int:
    l = []
    res = 0
    for i in range(length - 1):
        for j in range(i + 1, length):
            if j == length - 1:
                l.append(arr[:i] + sorted(arr[i:]))
            else:
                l.append(arr[:i] + sorted(arr[i:j]) + arr[j:])
    for i in arr[:-1]:
        for j in arr[arr.index(i) + 1:]:
            res += max(abs(lst.index(i) - lst.index(j)) for lst in l)
    return res

Условие

*Задан массив [p1, p2, . . . , pn], содержащий n различных целых чисел от 1 до n. Можно выбрать один любой отрезок массива с l-й по r-ю позицию включительно (1 ⩽ l ⩽ r ⩽ n), то есть [pl , pl+1, . . . , pr], и отсортировать элементы массива на этом отрезке в порядке возрастания. Например, если n = 5, изначально числа стояли в порядке [5, 2, 4, 1, 3], и был выбран отрезок с l = 2 и r = 4, то после сортировки числа в массиве будут стоять в порядке [5, 1, 2, 4, 3]. Расстояние между числами в массиве равно разности номеров позиций, на которых они стоят. Обозначим d(a, b) наибольшее возможное расстояние, на котором могут оказаться числа a и b после сортировки чисел на одном отрезке. Например, в приведенном выше массиве d(1, 3) = 4: чтобы числа 1 и 3 оказались на расстоянии 4, можно выбрать отрезок с l = 1 и r = 4. Тогда массив изменится следующим образом [5, 2, 4, 1, 3] → [1, 2, 4, 5, 3]. Выбранный отрезок подчеркнут. Требуется вычислить сумму значений d(a, b) по всем парам чисел a и b (1 ⩽ a < b ⩽ n). Например, если n = 5, то необходимо вычислить сумму d(1, 2) + d(1, 3) + d(1, 4)

  • d(1, 5) + d(2, 3) + d(2, 4) + d(2, 5) + d(3, 4) + d(3, 5) + d(4, 5).*

Формат входных данных

В первой строке дано одно целое число n — количество элементов массива (2 ⩽ n ⩽ 3 000). Во второй строке даны n различных целых чисел p1, p2, . . . , pn — элементы массива (1 ⩽ pi ⩽ n).

Формат выходных данных

Выведите одно целое число — ответ на задачу.

python
Источник: Stack Overflow на русском

Ответы

▲ 2Принят

Если вывести подмассивы l в цикле, то можно заметить, что выводится всего 10 вариантов для массива-примера, и только один начинается с единицы. Это означает, что перебраны не все пары начала и конца. Вот так будут все 15:

for i in range(length):
    for j in range(i+1, length+1):
        if j == length:
            l.append(arr[:i] + sorted(arr[i:]))
        else:
            l.append(arr[:i] + sorted(arr[i:j]) + arr[j:])
        print(i,j-1, l[-1])   #контроль

Кроме того, кажется разумным сделать последний цикл попроще.

for i in range(1, length):
    for j in range(i+1, length+1):

P.S. сложность решения O(n^3*log(n)) выглядит великоватой, ну да вопрос был не в этом.