Parenthesis Sequence Transformation

Ported from Frontier-CS algorithmic/problems/205.

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 Transformation

Problem Description: You are given two valid parenthesis sequences s1 and s2, both of length 2n. Your goal is to transform s1 into s2 using the minimum number of operations.

Available Operations:

• Op 1: Transform p(((A)B)C)q into p((A)B)(C)q
• Op 2: Transform p((A)(B)C)q into p((A)B)(C)q
• Op 3: Transform p(A)((B)C)q into p((A)B)(C)q
• Op 4: Transform p(A)(B)(C)q into p((A)B)(C)q

Where A, B, C are valid parenthesis sequences (possibly empty), and p, q are arbitrary sequences.

Special Operations (Each can be used at most 2 times per case):

• Op 5: Insert a pair of empty parentheses "()" at any position (max 2 times).
• Op 6: Remove a pair of empty parentheses "()" from any position (max 2 times).

Input Format:

• First line: an integer n (1 <= n <= 100,000)
• Second line: a string s1 of length 2n
• Third line: a string s2 of length 2n

Output Format:

• First line: an integer Q (the number of operations, must not exceed 3n)
• Next Q lines: each line contains two integers op and x
  • op: operation number (1-6)
  • x: position where the operation is applied

Position definition:

• For operations 1-4: x is the starting position of the leftmost '(' in the pattern
• For operations 5-6: x is the position to insert/remove "()"
• All positions are 0-indexed

Example: Input: 3 (())() ((()))

Output: 3 5 6 4 0 6 6

Explanation: Initial: (())() After Op 5 at position 6: (())()() After Op 4 at position 0: ((()))() After Op 6 at position 6: ((()))

Scoring: This problem is graded based on the number of operations Q:

• If Q <= 1.9n, you receive full score (1.0).
• If Q >= 3n, you receive 0 score.
• Otherwise, Score = (3n - Q) / (1.1n), clamped to [0, 1]

Constraints:

• 1 <= n <= 100,000
• Total operations must not exceed 3n.
• Op 5 can be used at most 2 times.
• Op 6 can be used at most 2 times.
• Both s1 and s2 are valid parenthesis sequences.