FixedPointReversals
SRM 765 · 2019-08-22 · by misof
Problem Statement
You are given the
The only way in which you can modify A is by reversing some segments of A. In each step you can specify indices i, j such that 0 <= i < j <= N, and reverse the segment A[i:j] = { A[i], ..., A[j-1] }.
There is one extra restriction: The operations must never change the value of the element at index fixed.
If there is no way to sort A, return {-1}.
Otherwise, find any solution with at most 75 reversals and return a
Notes
- You are not required to minimize the number of reversals.
- For the given constraints, whenever a solution exists, a solution with at most 75 reversals exists.
Constraints
- A will have between 1 and 50 elements, inclusive.
- Each element of A will be between 1 and 50, inclusive.
- fixed will be between 0 and length(A)-1, inclusiive.
{10, 20, 30, 40, 50}
2
Returns: { }
The array is already sorted.
{10, 20, 40, 30, 50}
2
Returns: {-1 }
There is no way to sort this array and satisfy the requirement that after each operation A[2] must remain 40.
{20, 10, 10, 10, 10, 10}
4
Returns: {0, 6 }
We can reverse the entire array. Note that after that operation A[4] is still equal to 10, so this is allowed.
{1, 50, 40, 30, 20, 10}
0
Returns: {1, 6 }
{20, 10, 30, 50, 40}
2
Returns: {0, 2, 3, 5 }
Submissions are judged against all 235 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class FixedPointReversals with a public method vector<int> sort(vector<int> A, int fixed) · 235 test cases · 2 s / 256 MB per case