MinimizeSortedness | Topcoder Archive

Problem Statement

Given a sequence S of distinct integers, let LIS(S) be the length of the longest increasing sequence that can be produced by erasing some elements of S.

For example, for S = {10,5,20,6,30} we have LIS(S) = 3 because we can produce the increasing subsequence {10,20,30} which has length 3. An increasing sequence S has LIS(S)=length(S), a decreasing sequence S has LIS(S)=1.

Similarly, let LDS(S) be the length of the longest decreasing subsequence of S.

The sortedness of a sequence S is defined as the maximum of LIS(S) and LDS(S).

You are given a int[] sequence containing a sequence of distinct integers. You are allowed to rearrange the elements of this sequence. Your task is to minimize the sortedness of the resulting sequence. Produce and return any such sequence.

Definition

Class:: MinimizeSortedness
Method:: permute
Parameters:: int[]
Returns:: int[]
Method signature:: int[] permute(int[] sequence)
(be sure your method is public)

Constraints

sequence will contain between 1 and 2,000 elements, inclusive.
Each element of sequence will be between 0 and 9,999, inclusive.
The elements of sequence will be distinct.

Examples

```
{42, 47}
```
```
Returns: {47, 42 }
```
Not much to optimize: both {42, 47} and {47, 42} have sortedness 2, so both of them are correct answers.
```
{10, 20, 30}
```
```
Returns: {20, 10, 30 }
```
Note that the input sequence has sortedness 3 but the sequence returned by our solution has sortedness 2. Hence, the sequence {10, 20, 30} is not a valid solution.

{4, 72, 14, 95, 32}

Returns: {32, 14, 95, 4, 72 }

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.