まず、初期状態で疲れている人が正しくない荷物を持っている場合は明らかに不可能です。実は、これ以外の場合は必ず可能です。

各人 \(i\) に対して、 \(i\) から \(p_i\) に辺を貼ったグラフを考えます。 \(p\) は順列なのでこれはサイクルの集合になりますが、サイクルの個数を \(C\) とおきます。

操作回数の下界を考えましょう。仮に疲れた人も操作に加われるとしても、必ず \(N-C\) 回以上の操作が必要なので最小値は必ず \(N-C\) 以上です。次のようにして実際 \(N-C\) 回による操作列が構成できます。

各サイクルごとに問題を独立に解きます。次の考察が重要です:

• 疲れていない二人 \(i,j\) で操作するとき、\(a_i \geq a_j\) なら \(i\) がこの操作によって疲れることはない。

このことから、サイクル内で最も軽い人間 \(i\) を選びその人に正しい荷物を渡すように操作すると、(この操作によって人 \(i\) 以外は疲れないため、)サイクルの頂点数が \(1\) 小さい問題に帰着できます。 サイクルの頂点数が \(1\) になれば終了なので、元のサイクルの頂点数を \(n\) として \(n-1\) 回の操作でサイクル内で条件が満たされます。

これを各サイクルごとに行うことで \(N-C\) 回で条件を達成することができます。

説明のためにサイクルごとに問題を分離しましたが、実際の実装では単に軽い人から順番に正しい荷物を与えていけば良いです。