INTARR - Editorial

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: inov_360
Testers: IceKnight1093, tabr
Editorialist: IceKnight1093

DIFFICULTY:

2145

PREREQUISITES:

Sorting

PROBLEM:

Given an array A, rearrange it so that every sorted subarray has length \leq 2.

EXPLANATION:

If N \leq 2, any rearrangement works so let’s assume N \geq 3.

Notice that if A_i = A_{i+1} for some i, then at least one of the subarrays [A_{i-1}, A_i, A_{i+1}] and [A_{i}, A_{i+1}, A_{i+2}] will exist, and be sorted.

So, if we are to rearrange it, the final array cannot have adjacent equal elements.
Let’s use this information to analyze what a valid final array can look like.

Suppose we fix the element A_1. Then, A_2 \neq A_1; let’s assume A_2 \gt A_1 for now. Note that:

  • [A_1, A_2, A_3] shouldn’t be sorted, so A_3 \lt A_2 must hold.
  • [A_2, A_3, A_4] shouldn’t be sorted, so A_4 \gt A_3 must hold.
  • [A_3, A_4, A_5] shouldn’t be sorted, so A_5 \lt A_4 must hold.
    \vdots

Notice that this essentially makes A have a ‘zig-zag’ pattern, i.e,

A_1 \lt A_2 \gt A_3 \lt A_4 \gt A_5 \lt \ldots

If A_2 \lt A_1 we get a similar zig-zag pattern, but with the peaks and valleys flipped; either way it’s a zig-zag.

Now, let’s try to put A into the pattern A_1 \lt A_2 \gt A_3 \lt A_4 \gt A_5 \lt \ldots
Our aim when doing this is to ensure that we never place equal elements next to each other. So, ideally, A_i and A_{i+1} are ‘far apart’ for every i.

The optimal way to do this is as follows:

  • Let S denote the sorted array of A, so S_1 \leq S_2 \leq \ldots \leq S_N
  • Set A_1 = S_1, A_3 = S_2, \ldots
    • More generally, set A_{2k-1} = S_k
  • The above process used elements S_1, S_2, \ldots, S_M, where M = \left\lceil \frac{N}{2} \right\rceil
  • To fill the even positions, we do something similar. Set A_2 = S_{M+1}, A_4 = S_{M+2}, \ldots
    • That is, set S_{2k} = S_{M+k}

Note that this process makes A_i and A_{i+1} be about N/2 positions apart (in sorted order) for every i, which is the best we can hope far.

This gives us a candidate zig-zag array A. Now check if it is valid (by looking at all size-3 subarrays), and if it is, print it.

If it isn’t valid, use a similar process to create a zig-zag array based on the pattern A_1 \gt A_2 \lt A_3 \gt A_4 \lt A_5 \gt \ldots
Notice that one easy way to do this is to simply repeat the above process on the reverse of S.

Once again, check if the obtained array is valid and print it if it is.

If both checks above fail, the answer is -1: every zig-zag rearrangement will include some pair of adjacent equal elements.

Proof

This is surprisingly a bit non-trivial to prove, and needs some case analysis.

Let’s construct the array A_1 \lt A_2 \gt A_3 \lt \ldots using the process as described above.
Suppose there are adjacent equal elements. Let i be the smallest index such that A_i = A_{i+1}.

The order in which we placed elements specifically tells us the following:

  • i = 2k for some k \geq 1
  • A_{2} = A_{4} = \ldots = A_{2k} = A_{2k+1} = A_{2k+3} = \ldots

Let this element be x. The above tells us that x appears at least \left\lceil \frac{N}{2} \right\rceil times in A.
If it appears \gt \left\lceil \frac{N}{2} \right\rceil times, the pigeonhole principle tells us that there will always be some adjacent equal elements, so the answer will always be -1.

Now, suppose x appears exactly \left\lceil \frac{N}{2} \right\rceil times. There are now two cases to consider, based on the parity of N.

  • When N is odd, the only possible situation when a valid zig-zag array exists is when x is either the smallest or the largest element of A: these two cases correspond to the two constructions we had above.
  • When N is even, a valid zig-zag array always exists because we can place elements in the form x _ x _ x _ ... x _ _ x _ x ... _ x, and choosing the spot where we flip from x _ to _ x can be done based on how many elements are \lt x.
    • Once again, depending on whether x is the smallest element or not, you can see this corresponds to one of the constructions above.

This completes the proof.

TIME COMPLEXITY:

\mathcal{O}(N\log N) per testcase.

CODE:

Setter's code (C++)
#include<bits/stdc++.h>
using namespace std;

#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
using namespace __gnu_pbds; 

#define ll long long
#define db double
#define el "\n"
#define ld long double
#define rep(i,n) for(int i=0;i<n;i++)
#define rev(i,n) for(int i=n;i>=0;i--)
#define rep_a(i,a,n) for(int i=a;i<n;i++)
#define all(ds) ds.begin(), ds.end()
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
typedef vector< long long > vi;
typedef pair<long long, long long> ii;
typedef priority_queue <ll> pq;
#define o_set tree<ll, null_type,less<ll>, rb_tree_tag,tree_order_statistics_node_update> 

const ll mod = 1000000007;
const ll INF = (ll)1e18;
const ll MAXN = 1000006;

ll po(ll x, ll n){ 
    ll ans=1;
    while(n>0){ if(n&1) ans=(ans*x)%mod; x=(x*x)%mod; n/=2;}
    return ans;
}

bool fun(vector<ll> &a){
    int n = a.size();
    int c[n];

    int j = (n+1)/2;
    
    c[0] = a[0];
    int k = 1;
    for(int i = 1; i<(n+1)/2; i++){
        c[k++] = a[j++];
        c[k++] = a[i];
    }
    if(k<n) c[k] = a[j];
    int ok = 1;

    for(int i=1; i+1<n; i++){
        ok &= ( !(c[i-1] <= c[i] && c[i] <= c[i+1])
                        && !(c[i-1] >= c[i] && c[i] >= c[i+1]));
    }

    if(ok){
        rep(i,n) cout<<c[i]<<" ";
        cout<<el;
        return true;
    }
    
    j = n/2;
    k = 0;
    for(int i = 0; j < n; i++){
    	c[k++] = a[j++];
    	if(i<n/2) c[k++] = a[i];
    }

    ok = 1;
    for(int i=1; i+1<n; i++){
        ok &= ( !(c[i-1] <= c[i] && c[i] <= c[i+1])
                        && !(c[i-1] >= c[i] && c[i] >= c[i+1]));
    }

     if(ok){
        rep(i,n) cout<<c[i]<<" ";
        cout<<el;
        return true;
    }
    return ok;
}


int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r" , stdin);
    freopen("output.txt", "w" , stdout);
    #endif
    int T=1;
    cin >> T;
    while(T--){
        int n;
        cin>>n;

        vector<ll> a(n);
        rep(i,n) cin>>a[i];

        sort(all(a));
       
        bool z = fun(a);
        if(!z){

                cout<<-1<<el;
        }

    
    }
    cerr << "Time : " << 1000 * ((double)clock()) / (double)CLOCKS_PER_SEC << "ms\n";
    return 0;
}
Editorialist's code (Python)
def check(ar):
	n = len(ar)
	for i in range(n-2):
		if ar[i] >= ar[i+1] >= ar[i+2]: return 0
		if ar[i] <= ar[i+1] <= ar[i+2]: return 0
	return 1
for _ in range(int(input())):
	n = int(input())
	a = sorted(list(map(int, input().split())))
	b, c = [0]*n, [0]*n
	b[0::2], b[1::2] = a[:(n+1)//2], a[(n+1)//2:]
	c[0::2], c[1::2] = a[n//2:], a[:n//2]
	if check(b): print(*b)
	elif check(c): print(*c)
	else: print(-1)
1 Like

This will return -1 for any array:

  • of odd length N >= 5
  • with exactly (N + 1) / 2 equal numbers (this number being neither the smallest nor the largest of the array)
  • no constraint on the other (N - 1) / 2 numbers

though inserting the other numbers between the equal numbers is a valid answer.

For example, with the following input:

1
5
1 3 3 3 5

both the Setter’s code and the Editorialist code return -1, however 3 1 3 5 3 is a valid answer.

Unfortunately, 1 3 5 is an increasing subarray.

2 Likes

Can someone figure out why my code fails for 1 test case? I am following the exact same zigzag pattern but enable to figure out why it fails.

Submission link: CodeChef: Practical coding for everyone

1 Like

As mentioned above, 1 3 5 is an increasing subarray in the example you provided.

Additionally, it isn’t hard to prove that the answer is always -1 in the case you mentioned (odd length, one element appears (N + 1) / 2 times, and it’s neither the smallest nor largest element).
If x is the element appearing (N + 1) / 2 times, the array must of course look like x _ x _ x _ ... x _ x.
When you place everything else, two adjacent empty slots will definitely contain one element larger than x and another one smaller than x, creating a sorted subarray.

Can anyone explain this line who author come to conclusion of this

" When N is odd, the only possible situation when a valid zig-zag array exists is when xx is either the smallest or the largest element of AA: these two cases correspond to the two constructions we had above "

Try writing it out and/or working out a few examples, you’ll see it’s rather obvious.

N is odd and x occurs \left\lceil \frac{N}{2} \right\rceil times; and we don’t want two occurrences of x to be next to each other.
Because of this, the only way you can possibly place the x's is x _ x _ x _ ... x _ x, i.e, alternating.

If every element is \gt x, you can place them in the gaps (in any order) and you’ll have a valid zig-zag array.
If every element is \lt x, you can again place them in the gaps and you’ll have a valid zig-zag array.
In every other case it’s impossible, the proof of which is in my previous comment.

1 Like

@iceknight1093
@admin
This solution is accepted even for wrong answer .
82023470

Eg
1
5
1 2 3 3 3
output : -1
expected : 3 1 3 2 3

Correct me if i am wrong .

EDIT : I have even found few other solution which gives wrong output but is still accepted . This is not at all fair .
check out this : CodeChef: Practical coding for everyone
eg
1
5
1 2 2 2 3
output : 2 1 2 2 3
expected : -1

1 Like
bool check(vector<ll int>vec)
{
    bool res=true;
    bool inc=vec[0]<vec[1];
    inc=!inc;
    for(int i=0;i<vec.size()-1;i++)
    {
        if(vec[i]==vec[i+1])
        {
            return false;
        }
        else if(vec[i+1]>vec[i] && inc)
        {
            return false;
        }
        else if(vec[i+1]>vec[i] && !inc)
        {
           inc=true;
        }
        else if(vec[i+1]<vec[i] && inc)
        {
            inc=false;
        }
        else if(vec[i+1]<vec[i] && !inc)
        {
            return false;
        }
    }
    return true;
}
//Code starts here
ll int mod=998244353;
int main()
{
    #ifndef ONLINE_JUDGE
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    #endif
   // fast;
    start_execution
    int tt=1;
    cin>>tt;
    while(tt--)
    {
        ll int n;
        cin>>n;
        vector<ll int>vec(n);
        vector<ll int>ans(n);
        read(vec);
        sorta(vec);
        if(n==1 || n==2)
        {
            debug(vec);
            continue;
        }
        ll int c=0;
        for(int i=0;i<n;i++)
        {
            ans[c]=vec[i];

            c=c+2;
            if(c>=n)
            {
                c=1;
            }
        }
        //debug(ans);
        if(check(ans))
        {
            debug(ans);
        }
        else
        {
            sortd(vec);
              c=0;
              for(int i=0;i<n;i++)
              {
                  ans[c]=vec[i];
      
                  c=c+2;
                  if(c>=n)
                  {
                      c=1;
                  }
              }

             if(check(ans))
             {
                debug(ans);
             }
             else
             {
                cout<<-1<<endl;
             }
        }
    } 
    stop_execution
    //execution_time
    return 0;
}

My solution failed in 1 test case what can be error?

It fails 4th Task

1 Like

Can anyone tell why this approach is failing. Thanks in advance.
My approach :
If we take two pointers at beginning and end of the array and place indices as { 1 6 2 5 3 4 } for sorted array of length 6 suppose.
Check the same for reversed string.

check for
1
6
1 2 3 3 4 5

Thanks bro got it.

I used a similar idea but wonder why correct answer for 2 2 2 3 3 is -1, we can make it 2 3 2 3 2, can’t we? My correct solution didn’t pass but this when this one did XD