Hill Sequence HILLSEQ Solution Codechef

Hill Sequence HILLSEQ Solution

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 1≤j<i1≤j<i
    • Aj>Aj+1Aj>Aj+1, for each i≤j<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, (1≤i≤N)(1≤i≤N) such that A1=B1,A2=B2,…,Ai−1=Bi−1A1=B1,A2=B2,…,Ai−1=Bi−1 and Ai>BiAi>Bi.

Input Format

  • 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.

Constraints

  • 1≤T≤1031≤T≤103
  • 1≤N≤1051≤N≤105
  • 1≤Ai≤1091≤Ai≤109
  • Sum of NN over all test cases does not exceed 5⋅1055⋅105

Subtasks

  • Subtask 1 (100 points): Original constraints

Sample Input 1 

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

Sample Output 1 

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

Explanation

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].

Hill Sequence HILLSEQ Solution is updated. Click Below

SOLUTION

Program C++: Hill Sequence HILLSEQ Solution in C++

Note: Solution Credit to Innovative Idea

#include<iostream>
#include<map>

using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int t;
    cin >> t;
    while(t--)
    {
        int n;
        bool flag = true;
        map<long long int, long long int> lexo;
        cin >> n;
        for(int i = 0; i<n; i++)
        {
            int temp;
            cin >> temp;
            lexo[temp]++;
        }
        
        for(auto x: lexo)
        {
            auto j = lexo.rbegin();
            if(j->second ==2)
            {
                cout << "-1\n";
                flag = false;
                break;
            }
            else if(x.second > 2)
            {
                cout << "-1\n";
                flag = false;
                break;
            }
        }
        
        if(flag == true)
        {
           for(auto x: lexo)
        {
            if(x.second==2) cout << x.first << " ";
        }
        for(auto k = lexo.rbegin(); k!=lexo.rend(); k++)
        {
            cout << k->first << " ";
        }  
        cout << endl;
        }
      
    }
}

Program Python: Hill Sequence HILLSEQ Solution in Python

t=int(input())
for _ in range(t):
    n=int(input())
    a=list(map(int,input().split()))
    q,w,d,x,y=[],[],{},0,0
    for i in a:
        if i in d:
            d[i]+=1
            q.append(i)
        else:
            d[i]=1
            w.append(i)
        x=max(x,i)
    for k,v in d.items():
        if v>2:
            y=v
            break
    if d[x]>1 or y>2:
        print(-1)
    else:
        q.sort()
        w.sort(reverse=True)
        ans=q+w
        print(*ans)
        

November Long Challenge 2021 Solution

Codechef Long Challenges Solution

October Long Challenge 2021 Solution

September Long Challenge 2021 Solution

2 thoughts on “Hill Sequence HILLSEQ Solution Codechef”

Leave a Comment