Разбор задачи «Древние руины»

Идея задачи

У нас есть n археологов и n артефактов. Изначально артефакт с номером i находится у археолога i. Каждый день археолог i передаёт тот артефакт, который сейчас у него в руках, археологу p[i].

Массив p является перестановкой. Это очень важно: каждый археолог получает ровно один артефакт и отдаёт ровно один артефакт. Значит, процесс передачи можно рассматривать как движение по перестановке.

Нужно для каждого археолога определить, через сколько дней он впервые снова получит свой собственный артефакт.

Главное наблюдение

Любая перестановка раскладывается на непересекающиеся циклы.

Например, если

• 1 -> 2
• 2 -> 4
• 4 -> 1

то вершины 1, 2, 4 образуют цикл длины 3.

Если археолог находится в цикле длины L, то его артефакт каждый день сдвигается на одну позицию по этому циклу. Тогда ровно через L дней артефакт вернётся к владельцу.

Значит, ответ для каждого археолога — это длина цикла, в котором он находится.

Как решать

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

Для каждой позиции i:

1. ставим cur = i;
2. переходим в p[cur];
3. считаем количество шагов;
4. когда снова пришли в i, это количество шагов и есть ответ.

Такой способ прост и полностью подходит для easy-версии.

Пример

Пусть дана перестановка:

2 3 4 5 1

Это означает:

• 1 -> 2
• 2 -> 3
• 3 -> 4
• 4 -> 5
• 5 -> 1

Здесь все вершины образуют один цикл длины 5.

Поэтому ответ будет:

5 5 5 5 5

Почему это правильно

Рассмотрим любого археолога i.

Так как p — перестановка, последовательность переходов

i, p[i], p[p[i]], ...

не может «потеряться» или попасть в тупик. Рано или поздно мы обязательно вернёмся в уже посещённую вершину. Поскольку у каждой вершины ровно один исход и один вход, для стартовой вершины i это будет именно цикл, содержащий i.

Пусть длина этого цикла равна L.

Тогда:

• за 1 день артефакт сдвигается на одну позицию по циклу;
• за 2 дня — ещё на одну;
• ...
• за L дней он делает полный оборот и возвращается к владельцу.

Раньше чем через L дней это невозможно, потому что внутри цикла все промежуточные позиции различны.

Следовательно, искомый ответ для археолога i действительно равен длине его цикла.

Оценка сложности

Пусть n — число археологов.

Для каждого i мы можем пройти по его циклу заново. В худшем случае это даёт:

• по времени: O(n^2);
• по памяти: O(n) или O(1) помимо массива ответа.

Для easy-версии этого достаточно.

Реализация на C++

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;

    while (t--) {
        int n;
        cin >> n;

        vector<int> p(n);
        for (int i = 0; i < n; ++i) {
            cin >> p[i];
            --p[i];
        }

        vector<int> ans(n);

        for (int i = 0; i < n; ++i) {
            int cur = i;
            int cnt = 0;

            do {
                cur = p[cur];
                ++cnt;
            } while (cur != i);

            ans[i] = cnt;
        }

        for (int i = 0; i < n; ++i) {
            if (i > 0) cout << ' ';
            cout << ans[i];
        }
        cout << '\n';
    }

    return 0;
}

Реализация на Python

import sys

input = sys.stdin.readline

t = int(input())

for _ in range(t):
    n = int(input())
    p = list(map(int, input().split()))
    p = [x - 1 for x in p]

    ans = [0] * n

    for i in range(n):
        cur = i
        cnt = 0

        while True:
            cur = p[cur]
            cnt += 1
            if cur == i:
                break

        ans[i] = cnt

    print(*ans)

На что обратить внимание

1. Индексация

Во входных данных археологи нумеруются с 1, а в программах на C++ и Python удобнее работать с нумерацией с 0.

Поэтому после чтения обычно делаем:

• в C++: --p[i]
• в Python: p = [x - 1 for x in p]

2. Почему можно не использовать массив посещения

Мы стартуем из вершины i и идём по перестановке до первого возвращения в i.

Так как это именно перестановка, мы гарантированно движемся по циклу. Поэтому отдельный массив visited в таком решении не нужен.

3. Что является ответом

Ответ — не номер вершины и не количество уникальных переходов «вообще», а именно число дней до первого возвращения собственного артефакта. Это и есть длина цикла.

Вывод

Задача сводится к одному ключевому факту: перестановка состоит из циклов. После этого всё становится просто:

• находим цикл для каждой вершины;
• считаем его длину;
• выводим эту длину как ответ.

Это хорошая базовая задача на понимание перестановок и их циклической структуры.