Hill Sequence solution codechef

Hill Sequence solution codechef

A sequence A1,A2,,ANA1,A2,…,AN of length NN is called good if any one of the following hold:

  • The sequence is strictly increasing, or
  • The sequence is strictly decreasing, or
  • There exists an index i(1<i<N)i(1<i<N) such that:
    • Aj<Aj+1Aj<Aj+1, for each 1j<i1≤j<i
    • Aj>Aj+1Aj>Aj+1, for each ij<Ni≤j<N

For example, the sequences [3,5,9][3,5,9][2,1][2,1][5,7,4,1] [5,7,4,1] are good, while [6,7,7][6,7,7][5,2,3][5,2,3] are not.

You are given an array AA consisting of NN integers. Find a good sequence by rearranging the elements of the array AA or report that this is impossible. If there are multiple good sequences, print the lexicographically largest one.

If two sequences AA and BB have the same length NN, we say that AA is lexicographically larger than BB if there exists an index ii(1iN)(1≤i≤N) such that A1=B1,A2=B2,,Ai1=Bi1A1=B1,A2=B2,…,Ai−1=Bi−1 and Ai>BiAi>Bi.

Hill Sequence solution codechef

  • The first line of input contains a single integer TT, denoting the number of test cases. The description of TT test cases follows.
  • The first line of each test case contains an integer NN, denoting the length of the array.
  • The second line contains NN space-separated integers A1,A2,,ANA1,A2,…,AN, denoting the given array.

Output Format

For each test case, if it is not possible to rearrange the given array into a good sequence, print 1−1. Otherwise, print a single line containing NN space-separated integers – the lexicographically largest good sequence that can be made.

Hill Sequence solution codechef

  • 1T1031≤T≤103
  • 1N1051≤N≤105
  • 1Ai1091≤Ai≤109
  • Sum of NN over all test cases does not exceed 51055⋅105


  • Subtask 1 (100 points): Original constraints

Hill Sequence solution codechef

2 3 5
1 1 1
5 7 2 1 2
1 2 3 2 2

Sample Output 1

5 3 2
2 7 5 2 1


Test case 11: The rearrangements of AA which are good sequences are: [5,3,2][5,3,2][3,5,2][3,5,2][2,3,5][2,3,5][2,5,3][2,5,3]. Among these, [5,3,2][5,3,2] is the lexicographically largest.

Test case 22: There is no way to obtain a good sequence by rearranging the elements of the array A=[1,1,1]A=[1,1,1].

Leave a Comment