Shortest Non-subsequence
Time limit2sMemory limit128 MB
Given a sequence of values from 1 to k, find the minimum length of a sequence over that alphabet that cannot be found as a subsequence of it.
- Level
Medium6 of 10
- Topics
- Greedy, String matching, Implementation
- Solved
- No attempts yet
Problem
A subsequence is a sequence made by choosing some elements from another sequence while keeping their original order. For example, from S = [1, 5, 3, 2, 5, 1, 3, 4, 4, 2, 5, 1, 2, 3], choosing the 1st, 5th, 7th, and 10th elements gives the subsequence p = [1, 5, 3, 2].
Given a sequence S, find the minimum possible length of a sequence that cannot be made as a subsequence of S. Every element of that sequence must be an integer between 1 and k, inclusive.
Input
The first line contains two integers n and k. n is the length of the sequence S, and k is the range of values that may appear in the sequence.
1 <= n <= 100000, 1 <= k <= 10000
Each of the next n lines contains one element of S in order. Every element is an integer between 1 and k, inclusive.
Output
Print the shortest length of a sequence that is not a subsequence of S.
Hint
Every sequence of length 1 or 2 using integers from 1 to 5 appears as a subsequence of the given S. However, among sequences of length 3, [2, 2, 4] is not a subsequence of S.