ReconstructPermutation
SRM 811 · 2021-08-19 · by misof
Problem Statement
We once had a permutation of the numbers from 0 to N-1, inclusive.
Then, someone erased some of its elements (possibly none or all of them). The order of the remaining elements was preserved.
You are given the sequence that remained in the
Reconstruct and return the original permutation. If there are multiple options, return the lexicographically smallest one among them.
Notes
- Given two distinct permutations of order N, the one that has a smaller value at the first index at which they differ is lexicographically smaller.
Constraints
- N will be between 1 and 500, inclusive.
- Each element of partial will be between 0 and N-1, inclusive.
- All elements of partial will be mutually distinct.
8
{1, 3, 5, 7}
Returns: {0, 1, 2, 3, 4, 5, 6, 7 }
The given partial permutation can be obtained from the lexicographically smallest of all permutations, so that is the answer.
5
{3, 1, 4, 0, 2}
Returns: {3, 1, 4, 0, 2 }
Nothing is missing, the input permutation is also the correct output.
5
{0, 3, 1}
Returns: {0, 2, 3, 1, 4 }
There are 20 different permutations from which the given partial permutation could have been obtained. The other 19 are all lexicographically greater than the one shown as correct return value.
8
{}
Returns: {0, 1, 2, 3, 4, 5, 6, 7 }
7
{5,3,1,0}
Returns: {2, 4, 5, 3, 1, 0, 6 }
Submissions are judged against all 86 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class ReconstructPermutation with a public method vector<int> reconstruct(int N, vector<int> partial) · 86 test cases · 2 s / 256 MB per case