Longest Common Subsequence

Ported from Frontier-CS algorithmic/problems/188.

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

LCS Challenge (Approximation)

Context

You are given two large strings, S1 and S2, consisting of uppercase English letters and/or digits. Let |S1| = N and |S2| = M. You must construct a string Z that is a common subsequence of both S1 and S2.

A string Z is a valid subsequence of S if Z can be obtained from S by deleting zero or more characters without changing the relative order of the remaining characters. (e.g., "ACE" is a subsequence of "ABCDE").

This is a heuristic optimization problem. You are NOT required to find the theoretically longest common subsequence (LCS). Due to the massive constraints (N, M <= 30,000,000), exact algorithms like O(NM) Dynamic Programming will exceed Time/Memory limits. Instead, you should try to maximize the length of your common subsequence Z (denoted as |Z|).

Let: L* = The length of the true optimal LCS (hidden). L = The length of the common subsequence found by your solution (|Z|).

The score is defined as: Score = (L / L*) * 100

Thus:

• Score = 100.0 means you found an optimal LCS.
• Smaller L yields a smaller score.
• Invalid solutions (where Z is not a subsequence of S1 or S2) receive score = 0.

The value L* is known to the judge but not to the contestant.

Input Format

The input consists of two lines.

The first line contains the string S1. The second line contains the string S2.

The strings contain only uppercase English characters ('A'-'Z') and digits ('0'-'9').

Constraints on length: 1 <= |S1|, |S2| <= 30,000,000

Output Format

Output exactly one line containing the string Z.

Requirements:

• Z must be a valid subsequence of S1.
• Z must be a valid subsequence of S2.

Scoring

Let: L = Length of the output string Z. L* = Optimal LCS length (hidden).

Validity Check: The judge will verify if Z is a subsequence of S1 AND S2 using a greedy linear scan. If the solution is invalid (e.g., characters in Z do not appear in valid relative order in S1 or S2): Score = 0

Otherwise: Score = (L / L*) * 100

Higher score is better.

Example

Input: ABC1D2EFG A1C2EZZZ

Output: AC2E

Explanation: S1 = "ABC1D2EFG" S2 = "A1C2EZZZ" User output Z = "AC2E".

1. Checking validity in S1:

   • 'A' at index 0
   • 'C' at index 2
   • '2' at index 5
   • 'E' at index 6 Indices are increasing (0 < 2 < 5 < 6), so it is valid for S1.

2. Checking validity in S2:

   • 'A' at index 0
   • 'C' at index 2
   • '2' at index 3
   • 'E' at index 4 Indices are increasing (0 < 2 < 3 < 4), so it is valid for S2.

Length L = 4. Assuming the optimal LCS L* = 4, the Score = 4 / 4 * 100 = 100.0.

Constraints

• 1 <= N, M <= 10,000,000 (1e7)
• Character Set: [A-Z, 0-9]
• Time Limit: 2.0s
• Memory Limit: 512MB