Variable-Length Sequence Reversal

Ported from Frontier-CS algorithmic/problems/214.

Agentics Interface

Each run executes the submitted zip_project solution once. The run command receives the case input on standard input and must write the candidate answer to standard output. The solution must not use the network during setup, build, or run.

The trusted separated evaluator compiles and runs the source-derived Frontier-CS checker against stdout.txt. Public validation contains one tiny deterministic case. Official cases, reference answers, and scoring metadata are supplied only through the required private asset official-runs.

Scoring

The primary metric is score, the average normalized Frontier-CS checker score on a 0-100 scale. Outputs rejected by the checker receive zero for that case. Official result details are score-only; public validation includes per-case feedback from the checker.

Original Statement

Sequence Reversal (requese)

Problem Description: You need to sort a permutation of $1\sim n$ on a strange computer.

You can choose a number $x$, and then each time you can reverse a segment of length $x+1$ or a segment of length $x-1$.

Please restore the sequence to $1\sim n$ within $200\times n$ operations.

(Note from problem setter: The current optimal solution can achieve below 15000 operations. Please try to optimize your algorithm.)

Input Format: The input consists of $2$ lines:

The first line contains a single integer $n$.

The second line contains $n$ integers, representing the sequence $a$.

Output Format: The output consists of $m + 2$ lines.

The first two lines each contain $1$ integer: $x$ and $m$, where $m$ represents the number of operations.

The next $m$ lines each contain two integers, representing the left and right endpoints of the reversal interval.

This problem uses a special judge (SPJ). As long as the reversal operations are correct, you will receive points.

Example 1: Input: 2 2 1

Output: 1 1 1 2

Explanation:

• Reverse (1,2): sequence becomes 1,2

Example 2: Input: 5 5 2 3 4 1

Output: 4 2 1 5 2 4

Explanation:

• Reverse (1,5): sequence becomes 1,4,3,2,5
• Reverse (2,4): sequence becomes 1,2,3,4,5

Constraints:

• For $100%$ of the data: $1 \leq n, a_i \leq 10^3$
• The sequence $a$ is guaranteed to be a permutation of $1\sim n$

Scoring: Your score is calculated based on the number of operations $m$:

• If $m \leq 20n$, you receive full score (1.0).
• If $m > 200n$, you receive 0 score.
• Otherwise, Score = max(0.0, 1.0 - (m - 20n) / (200n - 20n)), linearly decreasing from 1.0 to 0.0.

Time limit: 2 seconds

Memory limit: 512 MB