Overview

Starting from station \(1\) and moving to station \(N\), at each station you move to the designated next station in order, and the task is to count the total number of stations visited.

Analysis

Since there is only one station \(P_i\) that can be reached from each station \(i\), the route from station \(1\) is a single fixed path. There are no branches or choices, so you simply keep moving to the next station as instructed.

For example, consider the case where \(N = 5\) and \(P = [3, 4, 2, 5]\):

• Station \(1\) → \(P_1 = 3\) → Station \(3\)
• Station \(3\) → \(P_3 = 2\) → Station \(2\)
• Station \(2\) → \(P_2 = 4\) → Station \(4\)
• Station \(4\) → \(P_4 = 5\) → Station \(5\) (Arrived!)

The stations visited are \(1, 3, 2, 4, 5\), totaling \(5\) stations.

This problem can be solved with a straightforward simulation (actually tracing the movements). It is guaranteed that station \(N\) is reachable from station \(1\), and there is a constraint that \(P_i \neq i\) (no self-loops), so station \(N\) is always reached in a finite number of steps. Also, since at most \(N\) stations are visited, \(O(N)\) is more than sufficient.

Algorithm

1. Initialize the current station current to \(1\) (the starting station) and the visit count count to \(1\).
2. While current is not \(N\), repeat the following:
   • Update current to \(P_{\text{current}}\) (the next station).
   • Increment count by \(1\).
3. After the loop ends, output count.

This is essentially the same operation as “traversing a linked list.” Each station holds a pointer (\(P_i\)) to the next station, and you simply follow them in sequence.

Complexity

• Time complexity: \(O(N)\) (since at most \(N\) stations are visited)
• Space complexity: \(O(N)\) (to store the array \(P\))

Implementation Notes

• Since the array \(P\) is stored in \(0\)-indexed format, to get the next station for station \(i\) (\(1\)-indexed), you need to access P[i - 1].

• Station \(N\) is the final destination and \(P_N\) does not exist, so the input consists of \(N - 1\) values. To avoid out-of-bounds array access, make sure to control the loop with the condition current != N.

  Source Code

N = int(input())
P = list(map(int, input().split()))

current = 1
count = 1
while current != N:
    current = P[current - 1]
    count += 1
print(count)

This editorial was generated by claude4.6opus-thinking.