TopCoder problem "TheSequencesLevelTwo" used in TCHS10 Round 1 (Division I Level Two)



Problem Statement

    

When John and Brus were high school students, they liked to investigate integer sequences. Once, John wrote down a sequence containing distinct positive integers. Brus wanted to reorder the elements of the sequence in such a way that the following condition held for all j, where 0 < j < n-1, and n is the number of elements in the sequence: The (j-1)-th and the (j+1)-th elements of the sequence are either both less than the j-th element or both greater than the j-th element. In other words, except for the first and last elements, the two immediate neighbors of each element must be either both greater than or both less than that element.

You are given a int[] sequence containing John's original sequence. Return the sequence after Brus reordered it. If there are several possible answers, return the one that comes first lexicographically. Sequence A comes before sequence B lexicographically if A contains a smaller value at the first index where they differ.

 

Definition

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

Notes

-There will always be at least one way for Brus to achieve his goal.
 

Constraints

-sequence will contain between 1 and 50 elements, inclusive.
-Each element of sequence will be between 1 and 1,000,000,000, inclusive.
-All elements in sequence will be distinct.
 

Examples

0)
    
{1, 5, 10}
Returns: {1, 10, 5 }
There are four possible ways for Brus to reorder the elements - {1, 10, 5}, {5, 1, 10}, {5, 10, 1} and {10, 1, 5}. He will choose the first of them.
1)
    
{47}
Returns: {47 }
This sequence contains only a single element, so it already satisfies Brus's goal.
2)
    
{7, 2, 5, 4}
Returns: {2, 5, 4, 7 }
This sequence already meets Brus's requirements, but he can reorder the elements to get another sequence that comes earlier lexicographically.
3)
    
{51, 49, 97, 9, 10, 89, 90, 41, 58}
Returns: {9, 41, 10, 51, 49, 89, 58, 97, 90 }

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=10818

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=14224&pm=10818

Writer:

Vasyl[alphacom]

Testers:

PabloGilberto , ivan_metelsky , StevieT

Problem categories:

Greedy, Sorting