Skip to content
TheChatArchiveThe Chat Archive
o4-mini-2025-04-16· OpenAIHugging Face LMArena Human Preference 140K

Дана перестановка p из n целых чисел. Необходимо вычислить, какое минимальное количество…

From a Chatbot Arena battleThe same person sent this prompt to two anonymous models at once. Compare it with chatgpt-4o-latest-20250326’s answer.
  1. User

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

    Будем говорить, что элементы перестановки упорядочены хорошо, если найдется такое число x от 1 до n, что перестановка имеет вид x , x + 1 , … , n , 1 , 2 , … , x − 1.

    Транспозиция -- это обмен соседних элементов перестановки p местами.

    Требуется реализация на python.

  2. Assistant

    Ниже приводится решение за O(n log n) по времени и O(n) по памяти.

    Идея:

    1. Посчитаем сначала inv₁ — число инверсий в исходной перестановке p (это минимальное число соседних обменов, чтобы превратить её в [1,2,…,n]).

    2. Заметим, что если мы «сдвигаем» целевую упорядоченную перестановку с начала x на начало x+1 (то есть меняем ориентир циклического сдвига), то число инверсий меняется по формуле

      inv_{x+1} = inv_x + (n − pos[x]) − (pos[x] − 1)
      или короче
      inv_{x+1} = inv_x + (n + 1 − 2·pos[x]),

      где pos[x] — позиция числа x в исходной p (1-based).

    3. Перебираем x=1…n (с учётом цикличности), поддерживая текущее inv_x и минимальное из них.

    Код:

    import sys
    sys.setrecursionlimit(10**7)
    
    class Fenwick:
        # 1-based Fenwick (BIT) для подсчёта числа элементов <= i
        def __init__(self, n):
            self.n = n
            self.fw = [0]*(n+1)
        def add(self, i, v=1):
            while i <= self.n:
                self.fw[i] += v
                i += i & -i
        def sum(self, i):
            s = 0
            while i > 0:
                s += self.fw[i]
                i -= i & -i
            return s
        def range_sum(self, l, r):
            return self.sum(r) - self.sum(l-1)
    
    def min_adj_transpositions_to_cyclic(p):
        n = len(p)
        # 1) посчитать inv1 = число инверсий в p
        fw = Fenwick(n)
        inv = 0
        for i, v in enumerate(p, start=1):
            # сколько уже встреченных элементов > v
            inv += fw.range_sum(v+1, n)
            fw.add(v, 1)
        # 2) запомним позиции
        pos = [0]*(n+1)
        for i, v in enumerate(p, start=1):
            pos[v] = i
        # 3) по формуле прокрутим все сдвиги x=1..n
        best = inv
        cur = inv
        # от x=1 к x=2, от x=2 к x=3, …, от x=n к x=1 (но последний переход нам не нужен)
        for x in range(1, n):
            k = pos[x]
            cur += (n + 1 - 2*k)
            if cur < best:
                best = cur
        return best
    
    if __name__ == "__main__":
        import sys
        data = list(map(int, sys.stdin.read().split()))
        n = data[0]
        p = data[1:]
        print(min_adj_transpositions_to_cyclic(p))
    

    Пояснения:

    • Мы храним inv = inv₁ — число инверсий для ориентира x=1 (т.е. «обычная» сортировка в [1,2,…,n]).
    • Затем для каждого x=1…n−1 обновляем
      inv_{x+1} = inv_x + (n + 1 − 2·pos[x])
      где pos[x] — индекс x в исходном p.
    • Минимум по всем этих inv_x и есть ответ: минимальное число соседних обменов, чтобы получить какой-либо циклический сдвиг [x, x+1, …, n, 1, …, x−1].

    Общая сложность:

    • O(n log n) на подсчёт начальных инверсий через Fenwick-дерево.
    • O(n) на проход по x=1…n.

Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.