Edge Locked Permutation Repair
Preview mode. Log in to edit, run, submit, and save progress.
Edge Locked Permutation Repair
A warehouse robot audits a permutation of packages numbered 1 through n. The sorter reports a repair cost based on how far the edge anchors are from a sorted order. A permutation that is already sorted costs 0. If at least one correct edge anchor is already in place, meaning 1 is at the left edge or n is at the right edge, the cost is 1. If the two edge anchors are completely reversed, meaning n is at the left edge and 1 is at the right edge, the cost is 3. Every other unsorted permutation costs 2. For each audit, report the repair cost. Input Format: The first line contains t, the number of test cases. Each test case contains n followed by a permutation of 1 through n. Output Format: For each test case, print the repair cost.
Examples
1 4 1 2 3 4
0
Explanation: The packages are already in sorted order, so the audit cost is 0.
Approach hint
Start with the simplest clear approach, explain the trade-off, then move toward the cleaner answer.
Common mistake
Skipping assumptions, edge cases, or trade-offs can make an otherwise good answer feel incomplete.