CF 1249B2 - Books Exchange (hard version)
We are given a system where each child initially holds a unique book, and every day each book is passed to another fixed child according to a permutation. After one day, every book moves once; after two days, it moves again under the same rule, and so on.
CF 1249B2 - Books Exchange (hard version)
Rating: 1300
Tags: dfs and similar, dsu, math
Solve time: 4m 6s
Verified: no
Solution
Problem Understanding
We are given a system where each child initially holds a unique book, and every day each book is passed to another fixed child according to a permutation. After one day, every book moves once; after two days, it moves again under the same rule, and so on.
For each child, we are not tracking the child, but the book that originally belonged to them. The question asks: starting from day 0, after how many days does that specific book return to its original owner for the first time.
The key viewpoint is to treat the permutation as a directed graph where each node has exactly one outgoing edge. Each node points to exactly one other node, and since it is a permutation, every node also has exactly one incoming edge. This structure decomposes entirely into disjoint cycles.
The constraints matter because the total number of nodes across all queries is up to 2 · 10^5. Any solution that simulates day by day movement would require potentially O(n^2) in the worst case, which is far beyond the limit. We need something linear per query, ideally O(n), since each node must be processed at least once.
A naive pitfall is simulating the movement for each child independently. For example, in a cycle of length 10^5, tracking one book step by step already costs 10^5, and doing this for all nodes multiplies work unnecessarily.
Another subtle issue is misunderstanding direction. The book movement follows the permutation forward, but we are asked when the original book returns to its origin, which corresponds to completing a full cycle in the permutation graph.
Approaches
A brute-force idea is to simulate time step by step for each starting node. For a fixed node i, we repeatedly apply the permutation to see where its book goes, until it returns to i. In the worst case, this takes O(n) steps per node, and doing it for all nodes leads to O(n^2). With n up to 2 · 10^5, this becomes infeasible.
The key observation is that the permutation decomposes into disjoint cycles. Once we enter a cycle, every node in that cycle shares the same return time: the length of the cycle. This is because applying the permutation repeatedly rotates positions inside the cycle, and the first time a node returns to itself is after exactly one full rotation.
So the problem reduces to finding all cycles in a directed graph where each node has outdegree 1, and assigning each node the length of its cycle.
This can be done by marking nodes as unvisited and performing a traversal along the permutation until we either hit a visited node or close a cycle. Every node encountered in a cycle gets assigned the same value.
| Approach | Time Complexity | Space Complexity | Verdict |
|---|---|---|---|
| Brute Force (per node simulation) | O(n^2) | O(n) | Too slow |
| Cycle decomposition | O(n) | O(n) | Accepted |
Algorithm Walkthrough
- Maintain a visited array initialized to false for all nodes. This prevents reprocessing nodes that already belong to a discovered cycle.
- Iterate through each node i from 1 to n. If it is already visited, skip it because it belongs to a previously processed cycle.
- Start following the permutation from i, storing the path in a temporary list. Continue moving from current node x to p[x] until reaching a visited node or returning to a node in the current path.
- If we detect a previously unvisited cycle inside the current path, determine its length by measuring the segment from the first occurrence of that node to the end of the path. This segment corresponds exactly to one cycle.
- Assign the cycle length to every node in that cycle segment.
- Mark all nodes in the cycle as visited, and continue with the next unvisited node.
The reason this is efficient is that each node is appended to a path exactly once and assigned exactly once.
Why it works
Each connected component of the permutation graph is a simple directed cycle. Starting from any node and repeatedly applying the permutation eventually returns to the starting node after exactly the cycle length. Since every node in a cycle is symmetric under rotation, the return time is identical for all nodes in that cycle. The algorithm explicitly reconstructs these cycles and assigns their length consistently, so no node can receive an incorrect value.
Python Solution
import sys
input = sys.stdin.readline
def solve():
q = int(input())
for _ in range(q):
n = int(input())
p = [0] + list(map(int, input().split()))
visited = [False] * (n + 1)
ans = [0] * (n + 1)
for i in range(1, n + 1):
if visited[i]:
continue
path = []
cur = i
while not visited[cur]:
visited[cur] = True
path.append(cur)
cur = p[cur]
cycle_start_index = 0
for idx, node in enumerate(path):
if node == cur:
cycle_start_index = idx
break
cycle_nodes = path[cycle_start_index:]
cycle_len = len(cycle_nodes)
for node in cycle_nodes:
ans[node] = cycle_len
print(*ans[1:])
if __name__ == "__main__":
solve()
The implementation follows cycle discovery by walking along unvisited nodes. Each node is added to a path once, and when we detect that we have returned to an already processed node, we identify the cycle portion inside the path. The cycle length is then assigned to all nodes in that cycle.
A subtle point is that marking nodes visited immediately when entering them is safe because every node has exactly one outgoing edge. Even if we later encounter a cycle boundary, the path still contains all nodes in correct order, allowing us to slice out the cycle segment.
Worked Examples
We trace the third sample query: p = [4, 6, 2, 1, 5, 3].
| Step | Current node | Path | Visited set |
|---|---|---|---|
| 1 | 1 | [1] | {1} |
| 2 | 1→4 | [1,4] | {1,4} |
| 3 | 4→1 | stop | {1,4} |
Cycle detected is [1,4], length 2, so ans[1]=2, ans[4]=2.
Next unvisited node is 2.
| Step | Current node | Path | Visited set |
|---|---|---|---|
| 1 | 2 | [2] | {1,2,4} |
| 2 | 2→6 | [2,6] | {1,2,4,6} |
| 3 | 6→3 | [2,6,3] | {1,2,3,4,6} |
| 4 | 3→2 | stop | all above |
Cycle is [2,6,3], length 3, assigned to each.
Next unvisited node is 5.
| Step | Current node | Path | Visited set |
|---|---|---|---|
| 1 | 5 | [5] | all + 5 |
| 2 | 5→5 | stop |
Cycle [5] has length 1.
This confirms that each cycle is handled independently and all nodes in a cycle receive identical values.
Complexity Analysis
| Measure | Complexity | Explanation |
|---|---|---|
| Time | O(n) per query | each node is visited once and processed once inside a cycle |
| Space | O(n) | arrays for visited, answer, and temporary path |
The total n across queries is 2 · 10^5, so linear processing per query ensures the solution runs comfortably within limits.
Test Cases
import sys, io
def run(inp: str) -> str:
sys.stdin = io.StringIO(inp)
from math import isclose
input = sys.stdin.readline
def solve():
q = int(input())
for _ in range(q):
n = int(input())
p = [0] + list(map(int, input().split()))
visited = [False] * (n + 1)
ans = [0] * (n + 1)
for i in range(1, n + 1):
if visited[i]:
continue
path = []
cur = i
while not visited[cur]:
visited[cur] = True
path.append(cur)
cur = p[cur]
idx = path.index(cur)
cyc = path[idx:]
for v in cyc:
ans[v] = len(cyc)
print(*ans[1:])
solve()
return sys.stdout.getvalue().strip()
# provided samples
assert run("""6
5
1 2 3 4 5
3
2 3 1
6
4 6 2 1 5 3
1
1
4
3 4 1 2
5
5 1 2 4 3
""") == "1 1 1 1 1\n3 3 3\n2 3 3 2 1 3\n1\n2 2 2 2\n4 4 4 1 4"
# custom cases
assert run("""1
2
2 1
""") == "2 2"
assert run("""1
4
1 2 3 4
""") == "1 1 1 1"
assert run("""1
3
2 3 1
""") == "3 3 3"
assert run("""1
5
2 3 4 5 1
""") == "5 5 5 5 5"
| Test input | Expected output | What it validates |
|---|---|---|
| 2-cycle swap | 2 2 | smallest non-trivial cycle |
| identity permutation | 1 1 1 1 | self-loops |
| 3-cycle | 3 3 3 | uniform cycle handling |
| single long cycle | 5 5 5 5 5 | full coverage cycle |
Edge Cases
A single-element cycle like p[i] = i is handled naturally because the traversal stops immediately after visiting the node once, producing a cycle length of 1. The algorithm assigns 1 to that node, matching the fact that the book is already at its owner after one day.
A full permutation cycle, where all nodes form one loop, is handled by collecting the entire path until the starting node is reached again. The cycle extraction step correctly slices the full path into a single segment, ensuring every node receives the same length equal to n.
Mixed cycle sizes pose no difficulty because visited marking ensures each cycle is discovered exactly once. The slicing step guarantees that nodes belonging to previously completed cycles are never reconsidered, preventing duplication or incorrect overlap.