Shortest Common Non-Subsequence
Time limit5sMemory limit512 MB
Given two binary strings of length up to 4000, find the shortest binary string that is a subsequence of neither, breaking ties by lexicographic order.
- Level
Hard8 of 10
- Topics
- Dynamic programming, Greedy, String, Brute force
- Solved
- No attempts yet
Problem
A subsequence of a sequence P is a sequence obtained from P by picking some or no elements of P while preserving their order. For example, “ICPC” is a subsequence of “MICROPROCESSOR”.
A common subsequence of two sequences is a sequence that is a subsequence of both. The well-known longest common subsequence problem asks for the longest of the common subsequences of two given sequences.
This problem goes the other way and considers the shortest common non-subsequence problem: given two sequences consisting of 0 and 1, find the shortest sequence, also consisting of 0 and 1, that is a subsequence of neither of the two sequences.
Input
The input consists of a single test case with two lines. Both lines are sequences consisting only of 0 and 1. Their lengths are between 1 and 4000, inclusive.
Output
Output in one line the shortest common non-subsequence of the two given sequences. If there are two or more such sequences, output the lexicographically smallest one. A sequence P is lexicographically smaller than another sequence Q of the same length if there exists k such that P1 = Q1, ..., Pk−1 = Qk−1, and Pk < Qk, where Si is the i-th character of a sequence S.