SEPX - Editorial

editorial
, ,
1

PROBLEM LINK:

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

Author: iceknight1093
Tester: raysh07
Editorialist: iceknight1093

DIFFICULTY:

Simple

PREREQUISITES:

None

PROBLEM:

An array A is said to separate X, if there exists an index i satisfying one of the following conditions:

  • A_i \lt X and A_{i+1} \gt X, or
  • A_i \gt X and A_{i+1} \lt X

You’re given an array A of length N as well as the value X.
Can A be rearranged to separate X?

EXPLANATION:

A separates X if and only if it has some element \lt X adjacent to some element \gt X.
We want to check if there exists a rearrangement of A that avoids such an adjacency.

From the given array A,let’s create two lists L_1 and L_2.
L_1 will hold all the elements of A that are \lt X, while L_2 will hold all the elements of A that are \gt X.
We want to ensure that no element of L_1 ends up next an element of L_2 in the final array.

Observe that:

  • If L_1 is empty (so there are no elements \lt X), this is trivially possible.
    This is just because all the elements of the array are \ge X, so any rearrangement at all will work.
  • Similarly, if L_2 is empty, we have every element being \le x, and any rearrangement will work.

That means the only interesting case is when L_1 and L_2 are both non-empty.

Observe that now, if we had only the elements of L_1 and L_2 with us, no matter what we do some element of L_1 will be next to an element of L_2, which is bad.
(This can be thought of as having a binary string that contains at least one occurrence of both zero and one - certainly some 0 must be next to a 1.)

However, we do have one potential saving grace: there is one type of element that’s not present in either L_1 or L_2, and that’s the element X itself!
Since we want a strict inequality with X, having A_i = X disables index i from being able to participate in the strict inequality.

So, in the case where L_1 and L_2 are both non-empty,

  • If there are no occurrences of X in the array, then no valid rearrangement can exist - X will always be separated.
  • If there’s at least one occurrence of X in the array, then a valid rearrangement will always exist: a simple construction is to first place all elements of L_1 (in any order), then all occurrences of X, and then all elements of L_2 (again in any order).

There are a couple of ways of implementing this fairly easily.

  • One way is to check if X \le \min(A) or X \ge \max(A) or if X appears in A.
    In all three cases, the answer is Yes; and in any other case the answer is No.
  • Alternately, it can be observed from the above construction that sorting A is the best-case scenario; so a valid solution is to sort A and then check if X is separated or not.

TIME COMPLEXITY:

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

CODE:

Editorialist's code (C++) 
// #include <bits/allocator.h>
// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include "bits/stdc++.h"
using namespace std;
using ll = long long int;
mt19937_64 RNG(chrono::high_resolution_clock::now().time_since_epoch().count());

int main()
{
    ios::sync_with_stdio(false); cin.tie(0);

    int t; cin >> t;
    while (t--) {
        int n, x; cin >> n >> x;
        vector a(n, 0);

        int mn = 1e9, mx = 0, found = 0;
        for (int &y : a) {
            cin >> y;
            mn = min(mn, y);
            mx = max(mx, y);
            found |= x == y;
        }

        if (x <= mn or x >= mx or found) cout << "Yes\n";
        else cout << "No\n";
    }
}