HILLSEQ - Editorial

PROBLEM LINK:

Contest Division 1
Contest Division 2
Contest Division 3
Practice

Setter: Soumyadeep Pal
Tester: Manan Grover
Editorialist: Taranpreet Singh

DIFFICULTY

Easy

PREREQUISITES

Observations

PROBLEM

A sequence A_1, A_2, \dots, A_N 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 \lt i \lt N) such that:
    • A_j \lt A_{j+1}, for each 1 \le j \lt i
    • A_j \gt A_{j+1}, for each i \le j \lt N

Given an array A of length N. Find the lexicographically largest good rearrangement of the array, or determine that it is not possible to obtain a good rearrangement of the given array A.

QUICK EXPLANATION

  • If the maximum element appears more than once, it is not possible to obtain a good rearrangement.
  • If any value other than maximum appears more than twice, it is not possible to obtain a good sequence.
  • Otherwise, if an element appears twice, it must appear once before the maximum element and once after the maximum element.
  • If an element appears only once, we can place it either before or after the maximum element. In order to get a lexicographically larger sequence, we place it after the maximum element.

EXPLANATION

The maximum element

Let us focus on the third condition of the good array. We can see that no element before i-th element is \geq A_i and no element after i-th element is \geq A_i. Hence, the i-th element is the maximum element of the array.

Additionally, the maximum value must appear only once, at i-th position, so if the maximum element is appearing more than once in the given array A, we can immediately prove that no good rearrangement exists.

We can prove it the same way in the first condition that the maximum element must only be the last element in the array.

Dividing the sequence into two parts

Let’s say the position of the maximum element is p. The sequence A_{1, p} is strictly increasing, and sequence A_{p, N} is strictly decreasing, where A_{l, r} denote the subarray from l-th element to r-th element of the array A.

Hence, due to strict inequalities, any value v can appear at most once in A_{1,p} and at most once in A_{p, N}. Hence, if any value has more than 2 occurrences, we cannot obtain a good sequence.

Otherwise, for each element v, if there are two occurrences of v, then we can place one occurrence of v in A_{1, p} and one occurrence in A_{p, N}. If v appears exactly once, we can place it either A_{1, p} or A_{p, N}.

Getting the lexicographically largest sequence

For any element v appearing twice, we have no choice, but to place it once in both A_{1, p} and once in A_{p, N}. A_{1, p} would be sorted in ascending order, while A_{p, N} would be sorted in descending order, so the position of v in both sequences would be determined automatically. We cannot influence it.

For an element v appearing only once, we have a choice. We can place it either in A_{1, p} or A_{p, N}.

To obtain a lexicographically larger sequence, it is optimal to place v in A_{p, N}.

Proof

Let’s assume the positions of the rest of the elements are already decided, and only once the occurrence of v is to be inserted, and v is not the maximum element. The maximum element appears at position p.

Let’s say, if inserting v in A_{1, p}, its position would be q. Since A_{1, p} is strictly increasing, we can say that v \lt A_q before insertion. Hence, by inserting v in A_{1, p}, the q-th element changes from A_q to v, which is lexicographically smaller.

For example, consider sequence [2, 4, 5, 4, 2] and we need to insert 3. p = 3 here. If we insert 3 in A_{1, 3}, it would become [2,3,4,5,4,2]. If inserted in A_{p, N}, the sequence becomes [2,4,5,4,3,2]. We obtain lexicographically larger sequence in second case.

Hence, we can first add to sequence all the elements appearing twice in increasing order, then the maximum element, and then all the remaining elements in decreasing order.

If facing an issue with implementation, feel free to refer to my commented solution.

TIME COMPLEXITY

The time complexity is O(N*log(N)) per test case due to sorting.

SOLUTIONS

Setter's Solution
#include<bits/stdc++.h>
using namespace std;


void solve() {
  int n; cin >> n;
  map<int, int> m;
  int mx = 0;
  for (int i = 0; i < n; i++) {
    int x; cin >> x;
    m[x]++;
    mx = max(mx, x);
  }
  for (auto u : m) {
    if (u.first == mx && u.second > 1) {
      cout << "-1\n";
      return;
    } else if (u.first < mx && u.second > 2) {
      cout << "-1\n";
      return;
    }
  }
  vector<int> ans(n);
  int l = 0, r = n - 1;
  for (auto u : m) {
    if (u.second == 1) {
      ans[l++] = u.first;
    } else {
      ans[r--] = u.first;
      ans[l++] = u.first;
    }
  }
  for (int i = 0; i < n; i++) {
    cout << ans[i] << ' ';
  }
  cout << '\n';
}

signed main() {
  ios_base :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
  int t;
  cin >> t;
  while (t--) solve();
  return 0;
}
Tester's Solution
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define asc(i,a,n) for(I i=a;i<n;i++)
#define dsc(i,a,n) for(I i=n-1;i>=a;i--)
#define forw(it,x) for(A it=(x).begin();it!=(x).end();it++)
#define bacw(it,x) for(A it=(x).rbegin();it!=(x).rend();it++)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define lb(x) lower_bound(x)
#define ub(x) upper_bound(x)
#define fbo(x) find_by_order(x)
#define ook(x) order_of_key(x)
#define all(x) (x).begin(),(x).end()
#define sz(x) (I)((x).size())
#define clr(x) (x).clear()
#define U unsigned
#define I long long int
#define S string
#define C char
#define D long double
#define A auto
#define B bool
#define CM(x) complex<x>
#define V(x) vector<x>
#define P(x,y) pair<x,y>
#define OS(x) set<x>
#define US(x) unordered_set<x>
#define OMS(x) multiset<x>
#define UMS(x) unordered_multiset<x>
#define OM(x,y) map<x,y>
#define UM(x,y) unordered_map<x,y>
#define OMM(x,y) multimap<x,y>
#define UMM(x,y) unordered_multimap<x,y>
#define L(x) list<x>
#define Q(x) queue<x>
#define PBS(x) tree<x,null_type,less<I>,rb_tree_tag,tree_order_statistics_node_update>
#define PBM(x,y) tree<x,y,less<I>,rb_tree_tag,tree_order_statistics_node_update>
#define pi (D)acos(-1)
#define md 1000000007
#define rnd randGen(rng)
int main(){
  mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
  uniform_int_distribution<I> randGen;
  ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
  #ifndef ONLINE_JUDGE
  freopen("input.txt", "r", stdin);
  freopen("output.txt", "w", stdout);
  #endif
  I t;
  cin>>t;
  while(t--){
    I n;
    cin>>n;
    I a[n];
    I mx=0;
    OM(I,I) mpp;
    B f=false;
    asc(i,0,n){
      cin>>a[i];
      mx=max(mx,a[i]);
      mpp[a[i]]++;
      if(mpp[a[i]]>2){
        f=true;;
      }
    }
    if(f){
      cout<<-1<<"\n";
    }else{
      if(mpp[mx]==2){
        cout<<-1<<"\n";
      }else{
        V(I) x,y;
        forw(it,mpp){
          if((*it).se==2){
            x.pb((*it).fi);
          }
          y.pb((*it).fi);
        }
        sort(all(x));
        sort(all(y));
        asc(i,0,sz(x)){
          cout<<x[i]<<" ";
        }
        dsc(i,0,sz(y)){
          cout<<y[i]<<" ";
        }
        cout<<"\n";
      }
    }
  }
  return 0;
}
Editorialist's Solution
import java.util.*;
import java.io.*;
class HILLSEQ{
    //SOLUTION BEGIN
    void pre() throws Exception{}
    void solve(int TC) throws Exception{
        int N = ni();
        int[] A = new int[N];
        for(int i = 0; i< N; i++)A[i] = ni();
        Arrays.sort(A);
        for(int i = 2; i< N; i++)if(A[i] == A[i-2]){
            //A[i] appears more than twice
            pn(-1);
            return;
        }
        if(N > 1 && A[N-1] == A[N-2]){
            //Maximum appears more than once
            pn(-1);
            return;
        }
        int[] list = new int[N];
        int c = 0;
        //Adding elements in list, which have two occurrences in increasing order
        for(int i = 0; i+1< N; i++)if(A[i] == A[i+1])list[c++] = A[i];
        //Adding all distinct elements in decreasing order
        for(int i = N-1; i>= 0; i--)if(i+1 == N || A[i] != A[i+1])list[c++] = A[i];
        for(int i = 0; i< N; i++)p(list[i]+" ");pn("");
    }
    //SOLUTION END
    void hold(boolean b)throws Exception{if(!b)throw new Exception("Hold right there, Sparky!");}
    static boolean multipleTC = true;
    FastReader in;PrintWriter out;
    void run() throws Exception{
        in = new FastReader();
        out = new PrintWriter(System.out);
        //Solution Credits: Taranpreet Singh
        int T = (multipleTC)?ni():1;
        pre();for(int t = 1; t<= T; t++)solve(t);
        out.flush();
        out.close();
    }
    public static void main(String[] args) throws Exception{
        new HILLSEQ().run();
    }
    int bit(long n){return (n==0)?0:(1+bit(n&(n-1)));}
    void p(Object o){out.print(o);}
    void pn(Object o){out.println(o);}
    void pni(Object o){out.println(o);out.flush();}
    String n()throws Exception{return in.next();}
    String nln()throws Exception{return in.nextLine();}
    int ni()throws Exception{return Integer.parseInt(in.next());}
    long nl()throws Exception{return Long.parseLong(in.next());}
    double nd()throws Exception{return Double.parseDouble(in.next());}

    class FastReader{
        BufferedReader br;
        StringTokenizer st;
        public FastReader(){
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        public FastReader(String s) throws Exception{
            br = new BufferedReader(new FileReader(s));
        }

        String next() throws Exception{
            while (st == null || !st.hasMoreElements()){
                try{
                    st = new StringTokenizer(br.readLine());
                }catch (IOException  e){
                    throw new Exception(e.toString());
                }
            }
            return st.nextToken();
        }

        String nextLine() throws Exception{
            String str = "";
            try{   
                str = br.readLine();
            }catch (IOException e){
                throw new Exception(e.toString());
            }  
            return str;
        }
    }
}

Feel free to share your approach. Suggestions are welcomed as always. :slight_smile:

1 Like

i am unable to understand why my code is showing wrong answer during submission, please clear my doubt

#include "bits/stdc++.h"
 
using namespace std;
 
// GCC Optimizations
#pragma GCC optimize("Ofast")
#pragma GCC target("fma,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#pragma GCC optimize("unroll-loops")
 
// Constants
constexpr long long SZ = 1e5 + 7;
constexpr long long inf = 1e18;
constexpr long long mod = 1e9 + 7;
constexpr long long MOD = 998244353;
 
// Debug Zone
//
 
// Macros
#define int long long int
#define Endl '\n'
#define pb push_back
#define fi first
#define se second
#define all(X) (X).begin(), (X).end()
#define allr(X) (X).rbegin(), (X).rend()
#define sz(X) (int)X.size()
#define setbits(X) __builtin_popcountll(X)
#define fix(X) fixed << setprecision(X)
#define mem0(X) memset((X), 0, sizeof((X)))
#define mem1(X) memset((X), -1, sizeof((X)))
 
// Typedefs
// <!-- typedef long long int; -->
typedef long double ld;
 
// Cpr
int tc_cnt = 1;
#define ons()               cout << "Case #" << tc_cnt ++ << ": ";
 
// Custom hash map
struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }
 
    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};
 
template<typename T1, typename T2>
using safe_map = unordered_map<T1, T2, custom_hash>;
 
// Helper
void go() {
}
 
int gcd(int a, int b) {
    if (b == 0) return a;
    return gcd(b, a % b);
}
 
int lcm(int a, int b) {
    return (a / gcd(a, b)) * b;
}

void solve()
{
    int n;
    
    unordered_map<int,int> Map;
    cin>>n;

    if(n==1)
    {
        int num;
        cin>>num;

        cout<<num;
        return;
    }
    int nums[n];
    int mx=INT_MIN;
    for(int i=0;i<n;i++)
    {
        cin>>nums[i];
        mx=max(mx,nums[i]);
        Map[nums[i]]++;
        if(Map[nums[i]]>2)
        {
            cout<<-1;
            return;
        }
    }

    if(Map[mx]>1)
    {
        cout<<-1;
        return;
    }

    vector<int> ans,ans2;

    for(auto i:Map)
    {
        if(i.second>1)
        {
            ans.push_back(i.first);
            i.second--;
        }

        if(i.second==1)
        {
            ans2.push_back(i.first);
            i.second--;
        }
    }

    sort(ans.begin(),ans.end());
    sort(ans2.begin(),ans2.end(),greater<>());

    for(auto i:ans)
    {
        cout<<i<<" ";
    }

    for(auto i:ans2)
        cout<<i<<" ";

}

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int t;
    cin>>t;

    while(t--)
    {
        solve();
        cout<<"\n";
    }

    return 0;
}

You are checking if(Map[nums[i]]>2) inside the same for loop in which you are reading the input. If this condition is true, then you won’t be able to process all the N numbers, and the remaining numbers will interfere with next input. I have corrected your solution Solution: 53877213 | CodeChef

2 Likes

SETTER’s solution is wrong
plz update the correct one

thanx bro, damn i could have scored this question

Hi! Can you tell me why my solution is wrong? I have followed every detail still the answer is not being accepted.
https://www.codechef.com/viewsolution/54009472

Hi! Can you tell me why my solution is wrong? I have followed every detail still the answer is not being accepted. Some corner cases?
https://www.codechef.com/viewsolution/54009472

Help in my code too.
https://www.codechef.com/viewsolution/53555215

Your code fails on

Test Case 1
6
5 5 7 7 7 11

Now can you tell where it fails? I have checked all conditions, still.
https://www.codechef.com/viewsolution/54009472