FixedPointReversals | Topcoder Archive

Problem Statement

You are given the int[] A with N elements. Your task is to sort it into the usual non-decreasing order.

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 int[] of the form { i1, j1, i2, j2, ... } that describes the sequence of reversals you wish to perform.

Definition

Class:: FixedPointReversals
Method:: sort
Parameters:: int[], int
Returns:: int[]
Method signature:: int[] sort(int[] A, int fixed)
(be sure your method is public)

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.

Examples

```
{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}

Returns: {1, 6 }

{20, 10, 30, 50, 40}

Returns: {0, 2, 3, 5 }

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.