INCRDEC - Editorial

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2

Tester: Trung Nguyen
Editorialist: Taranpreet Singh

DIFFICULTY

Easy

PREREQUISITES

None

PROBLEM

Given a sequence A of N integers. Reorder A into an increasing-decreasing sequence or determine if it is impossible to do so.

An increasing-decreasing sequence of integers is a sequence, which for some integer p (1 \leq p \leq N) have first p integers sorted in strictly increasing order and last N-p+1 elements sorted in strictly decreasing order.

QUICK EXPLANATION

  • It is possible to reorder if and only if each element appears at most twice, and the maximum element appears at most once.
  • To obtain a valid increasing-decreasing order, first, print all distinct elements in increasing order and then print the remaining integers in decreasing order.

EXPLANATION

Let’s focus on p-th element. On positions to its left as well as it’s right, all the elements are strictly smaller than this element. So, on p-th position, the maximum value must be fixed. But if the maximum value appears more than once, we cannot fit all occurrences of maximum into a valid increasing-decreasing sequence.

Hence, we need the maximum element to appear exactly once. (Think why maximum element cannot appear zero times :stuck_out_tongue: )

Now, having fixed the maximum element, we can add remaining values into either side of p-th element.

Since both left and right part is in strictly increasing/decreasing order, each distinct value may appear at most once in each part.

This constrains us to at most two occurrences of each distinct value. Hence, if an element appears more than twice, then also, it is impossible to reorder A into an increasing-decreasing sequence.

These impossible conditions give us the way to construct a valid sequence. Firstly, sort the given sequence A and print each distinct value present in A in sorted order. Then print the remaining elements in decreasing order.

Since each element appears at most twice and maximum element appears at most once, the generated sequence shall be a valid increasing-decreasing sequence.

Bonus:
Now, you are given position p in the input itself. You need to generate an increasing-decreasing sequence such that the maximum element appears at position p.

TIME COMPLEXITY

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

SOLUTIONS

Setter's Solution
#include <iostream>
#include <algorithm>
#include <string>
#include <assert.h>
using namespace std;
 
 
 
long long readInt(long long l,long long r,char endd){
	long long x=0;
	int cnt=0;
	int fi=-1;
	bool is_neg=false;
	while(true){
		char g=getchar();
		if(g=='-'){
			assert(fi==-1);
			is_neg=true;
			continue;
		}
		if('0'<=g && g<='9'){
			x*=10;
			x+=g-'0';
			if(cnt==0){
				fi=g-'0';
			}
			cnt++;
			assert(fi!=0 || cnt==1);
			assert(fi!=0 || is_neg==false);
		
			assert(!(cnt>19 || ( cnt==19 && fi>1) ));
		} else if(g==endd){
			assert(cnt>0);
			if(is_neg){
				x= -x;
			}
			assert(l<=x && x<=r);
			return x;
		} else {
			assert(false);
		}
	}
}
string readString(int l,int r,char endd){
	string ret="";
	int cnt=0;
	while(true){
		char g=getchar();
		assert(g!=-1);
		if(g==endd){
			break;
		}
		cnt++;
		ret+=g;
	}
	assert(l<=cnt && cnt<=r);
	return ret;
}
long long readIntSp(long long l,long long r){
	return readInt(l,r,' ');
}
long long readIntLn(long long l,long long r){
	return readInt(l,r,'\n');
}
string readStringLn(int l,int r){
	return readString(l,r,'\n');
}
string readStringSp(int l,int r){
	return readString(l,r,' ');
}


int T;
int n;
int rep[200200];


int main(){
	//freopen("00.txt","r",stdin);
	//freopen("00o.txt","w",stdout);
	T=readIntLn(1,100);
	while(T--){
		n=readIntLn(1,100000);
		int mx=0;
		bool ok=true;
		for(int i=0;i<n;i++){
			int x;
			if(i==n-1){
				x=readIntLn(1,200000);
			} else {
				x=readIntSp(1,200000);
			}
			rep[x]++;
			mx=max(mx,x);
			if(rep[x]> 2){
				ok=false;
			}
		}
		if(rep[mx] > 1){
			ok=false;
		}
		if(!ok){
			cout<<"NO"<<endl;
			for(int i=0;i<=200000;i++){
				rep[i]=0;
			}
			continue;
		}
		cout<<"YES"<<endl;
		for(int i=0;i<=200000;i++){
			if(rep[i]){
				cout<<i<<" ";
				rep[i]--;
			}
		}
		for(int i=200000;i>=0;i--){
			if(rep[i]){
				cout<<i<<" ";
				rep[i]--;
			}
		}
		cout<<endl;
	}
	assert(getchar()==-1);
}
Tester's Solution
#include <bits/stdc++.h>
using namespace std;
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
 
#define ms(s, n) memset(s, n, sizeof(s))
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define FORd(i, a, b) for (int i = (a) - 1; i >= (b); --i)
#define FORall(it, a) for (__typeof((a).begin()) it = (a).begin(); it != (a).end(); it++)
#define sz(a) int((a).size())
#define present(t, x) (t.find(x) != t.end())
#define all(a) (a).begin(), (a).end()
#define uni(a) (a).erase(unique(all(a)), (a).end())
#define pb push_back
#define pf push_front
#define mp make_pair
#define fi first
#define se second
#define prec(n) fixed<<setprecision(n)
#define bit(n, i) (((n) >> (i)) & 1)
#define bitcount(n) __builtin_popcountll(n)
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pi;
typedef vector<int> vi;
typedef vector<pi> vii;
const int MOD = (int) 1e9 + 7;
const int FFTMOD = 119 << 23 | 1;
const int INF = (int) 1e9 + 23111992;
const ll LINF = (ll) 1e18 + 23111992;
const ld PI = acos((ld) -1);
const ld EPS = 1e-9;
inline ll gcd(ll a, ll b) {ll r; while (b) {r = a % b; a = b; b = r;} return a;}
inline ll lcm(ll a, ll b) {return a / gcd(a, b) * b;}
inline ll fpow(ll n, ll k, int p = MOD) {ll r = 1; for (; k; k >>= 1) {if (k & 1) r = r * n % p; n = n * n % p;} return r;}
template<class T> inline int chkmin(T& a, const T& val) {return val < a ? a = val, 1 : 0;}
template<class T> inline int chkmax(T& a, const T& val) {return a < val ? a = val, 1 : 0;}
inline ull isqrt(ull k) {ull r = sqrt(k) + 1; while (r * r > k) r--; return r;}
inline ll icbrt(ll k) {ll r = cbrt(k) + 1; while (r * r * r > k) r--; return r;}
inline void addmod(int& a, int val, int p = MOD) {if ((a = (a + val)) >= p) a -= p;}
inline void submod(int& a, int val, int p = MOD) {if ((a = (a - val)) < 0) a += p;}
inline int mult(int a, int b, int p = MOD) {return (ll) a * b % p;}
inline int inv(int a, int p = MOD) {return fpow(a, p - 2, p);}
inline int sign(ld x) {return x < -EPS ? -1 : x > +EPS;}
inline int sign(ld x, ld y) {return sign(x - y);}
mt19937 mt(chrono::high_resolution_clock::now().time_since_epoch().count());
inline int mrand() {return abs((int) mt());}
inline int mrand(int k) {return abs((int) mt()) % k;}
#define db(x) cerr << "[" << #x << ": " << (x) << "] ";
#define endln cerr << "\n";

void chemthan() {
	int test; cin >> test;
	assert(1 <= test && test <= 1e2);
	int sumn = 0;
	while (test--) {
	    int n; cin >> n;
	    sumn += n;
	    assert(1 <= n && n <= 1e5);
	    assert(1 <= sumn && sumn <= 1e6);
	    vi a(n);
	    FOR(i, 0, n) cin >> a[i];
	    if (n == 1) {
	        cout << "YES\n";
	        cout << a[0] << "\n";
	        continue;
	    }
	    sort(all(a));
	    if (a[n - 2] == a[n - 1]) {
	        cout << "NO\n";
	        continue;
	    }
	    vi v1, v2;
	    FOR(i, 0, n - 1) {
	        if (!i || a[i] != a[i - 1]) {
	            v1.pb(a[i]);
	        }
	        else {
	            v2.pb(a[i]);
	        }
	    }
	    int found = 0;
	    FOR(i, 0, sz(v2) - 1) {
	        if (v2[i] == v2[i + 1]) {
	            found = 1;
	        }
	    }
	    reverse(all(v2));
	    if (found) {
	        cout << "NO\n";
	        continue;
	    }
	    cout << "YES\n";
	    FOR(i, 0, sz(v1)) cout << v1[i] << " ";
	    cout << a[n - 1] << " ";
	    FOR(i, 0, sz(v2)) cout << v2[i] << " ";
	    cout << "\n";
	}
}

int main(int argc, char* argv[]) {
	ios_base::sync_with_stdio(0), cin.tie(0);
	if (argc > 1) {
	    assert(freopen(argv[1], "r", stdin));
	}
	if (argc > 2) {
	    assert(freopen(argv[2], "wb", stdout));
	}
	chemthan();
	cerr << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";
	return 0;
}
Editorialist's Solution
import java.util.*;
import java.io.*;
class INCRDEC{
	//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);
	    boolean[] vis = new boolean[N];
	    int[] ans = new int[N];
	    int c = 0;
	    for(int i = 0; i< N; i++)if(i == 0 || A[i] != A[i-1]){
	        ans[c++] = A[i];
	        vis[i] = true;
	    }
	    boolean possible = true;
	    for(int i = N-1; i>= 0; i--){
	        if(vis[i])continue;
	        possible &= A[i] < ans[c-1];//It'll become false in case of duplicates
	        ans[c++] = A[i];
	    }
	    if(possible){
	        pn("YES");
	        for(int i:ans)p(i+" ");pn("");
	    }else pn("NO");
	}
	//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 INCRDEC().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:

2 Likes

Hi Guys Try this Video solution,
I have tried to explain visually how can we approach to answer :raised_hands::raised_hands:

5 Likes

#include<bits/stdc++.h>
using namespace std;
int main(){
int t;
cin>>t;
while(t–){
long long int s,n,b=0,j=0,m=1;
cin>>n;
long long int ar[n];
for(int i=0;i<n;i++)
cin>>ar[i];
sort(ar,ar+n);
if(ar[n-1]==ar[n-2]){
m=2;
}
for(int i=0;i<n-1;i++){
if(ar[i]!=ar[i+1])
b=1;
else{
b++;
}

	if(b>2){
		m=2;
		break;
	}
}
if(m==2)
cout<<"N0\n";
else{
	cout<<"YES\n";
	vector<long long int>v1,v2;
	for(int i=0;i<n-1;i++){
		if(ar[i]==ar[i+1]){
			v1.push_back(ar[i]);
			v2.push_back(ar[i+1]);
			i++;
		}
		else v1.push_back(ar[i]);
	}
	if(ar[n-1]!=ar[n-2])v1.push_back(ar[n-1]);
	for(int i=0;i<v1.size();i++)
	cout<<v1[i]<<" ";
	for(int i=v2.size();i>0;i--)
	cout<<v2[i-1]<<" ";
	cout<<endl;
}

}
return 0;

}

@admin
why this solution is getting wa

Kindly check mistake in my code . or tell any test case for which it gives WA.
https://www.codechef.com/viewsolution/34807952

https://www.codechef.com/viewsolution/34796274
My approach is bit different. It uses C++ maps.

2 Likes

Why java code was getting tle in subtask 2 but AC In subtask 1.
I used fast i/o.

1 Like

I am getting quite unexpectedly AC in subtask 2 and WA in subtask 1.
Can someone help me find error in my code?
I have stored frequency of each element in vector c and taken cases if largest element has frequency>1 then NO or if any intermediate element has >2 then NO,and finally in all other cases YES
https://www.codechef.com/viewsolution/34822544

1 Like

Hey, thank you for the explaination…
Here is my solution with a very similar approach to yours… will you please check where did i go wrong…
https://www.codechef.com/viewsolution/34825450

Also the output for your testcase is :
YES
1 3 4 9 12 13 4

The array goes on increasing until 13 and then goes strictly down.
Is this also a correct answer?
Any help would be highly appreciated.

https://www.codechef.com/viewsolution/34826057
can anyone please help me to remove the TLE

1 Like

All the cases seems to be correct and covered

But I am getting WA in Subtask 0 and AC in subtask 1

Why using more than 1 array give WA on sub- task 1 and AC on sub- task 2??

I think there is some discrepancy with using Java’s ArrayList and HashMap, couldn’t get my solution accepted with it, but the solution got accepted when applied the near same concept in Python3.

Can anyone pls tell me what is wrong with this code?? I feel that it is completely right logic wise but still I am unable to understand why do I get WA on submission.
Here is the link to my code: https://www.codechef.com/viewsolution/34824576

Same here, couldn’t pass subtask 2 because of tle

Same is the case with me.

Because after printing YES it will wait for the next input as instead of printing the sequence

Can anyone tell me what is wrong with this approach?
here is the link to my code :- https://www.codechef.com/viewsolution/34829128

I am explaining my logic here
I have taken two TreeSet and one with increasing and another decreasing and if the no. appeared first time then added it to first tree and then if occurred twice added it to second tree and if it is present in both tree then Obviosuly no will be the answer
and if last value of first tree is equal to first value of second tree (if not empty) then largest no has occured twice so answer is no… and finally printed them by joining both trees.
It is working for all the custom test case i feed
@taran_1407

My super duper easy to understand solution for this:

  1. Sort the sequence
  2. Pick all unique elements from left to right (this will be increasing).
  3. Pick all elements which are left in the sequence from right to left (this will be decreasing and if any element found violating this say “NO”.

Hint: I used a separated bool array to track which elements are added and which are left.

2 Likes
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
#define loop(i, a, b) for (int i = a; i < b; i++)

int main()
{
//#ifndef OJ
   // freopen("input.txt", "r", stdin);
// freopen("output.txt","w",stdout);
//#endif
    int t;
    cin >> t;
    while (t--)
    {
        int n;
        cin >> n;
        int arr[n];
        int ans[n];
        int count = 0;
        loop(i, 0, n) cin >> arr[i];
        sort(arr, arr + n);
        int toggle = 1;
        int x = 0, y = n - 1, index = -1;
        //convering the array in increasing and decreasing order
        loop(i, 0, n)
        {
            if (toggle)
                ans[x++] = arr[i];
            else
                ans[y--] = arr[i];
            toggle = toggle ^ 1;
        }
        loop(i, 0, n - 1)
        {
            if (ans[i] == ans[i + 1])
            {
                index = i;
                break;
            }
        }
        if (index == -1)
        {
            cout << "YES\n";
            loop(i, 0, n) cout << ans[i] << " ";
            cout << endl;
        }
        else
        {
            bool b = true;
            for (int i = index; i >= 1; i--)
            {
                if (ans[i] <= ans[i - 1])
                    b = false;
            }
            loop(i, index + 1, n - 1)
            {
                if (ans[i] <= ans[i + 1])
                    b = false;
            }
            if (b == false)
            {
                cout << "NO\n";
            }
            else
            {
                cout << "YES\n";
                loop(i, 0, n) cout << ans[i] << " ";
                cout << endl;
            }
        }
    }
}

can anyone please tell me where is my code getting wrong