Hill Sequence HILLSEQ Solution Codechef

Hill Sequence HILLSEQ Solution

A sequence A1,A2,…,AN of length N 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
  • Aj < Aj +1, for each 1<=j<i
  • Aj > Aj +1, for each i<=j<N

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

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

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

Input Format

• The first line of input contains a single integer T, denoting the number of test cases. The description of T test cases follows.
• The first line of each test case contains an integer N, denoting the length of the array.
• The second line contains N space-separated integers A1,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. Otherwise, print a single line containing N space-separated integers the lexicographically largest good sequence that can be made.

Constraints

• 1≤T≤10³
• 1≤N≤10⁵
• 1≤Ai≤10⁹
• Sum of N over all test cases does not exceed 5⋅10⁵

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 1: The rearrangements of A which are good sequences are: [5,3,2], [3,5,2], [2,3,5], [2,5,3] Among these, [5,3,2] is the lexicographically largest.

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

SOLUTION

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

#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

• Which Fuel is Cheaper CHEAPFUEL Solution
• Convex Hulk CONHULK Solution
• Functional Array FUNARR Solution
• Flip or Compress FLIPCOMP Solution
• Maximise the bridges MAXBRIDGE Solution
• Wildcard Replacement WLDRPL Solution
• Xor Equation XOREQN Solution
• Hill Sequence HILLSEQ Solution
• Weird Palindrome Making MAKEPAL Solution
• Equal Coins EQUALCOIN Solution Codechef