CONCATSORT-Editorial

editorial
, ,
1

PROBLEM LINK:

Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4

Setter: Jeevan Jyot Singh
Testers: Jatin Garg, Tejas Pandey
Editorialist: Devendra Singh

DIFFICULTY:

1637

PREREQUISITES:

None

PROBLEM:

JJ has an array A. He can perform the following operation on A:

  • Divide A into two subsequences P and Q such that each A_i belongs to either P or Q.
  • Set A := P\ \texttt{concat}\ Q

Here \texttt{concat} denotes the concatenation operation. For e.g. [2, 1, 5] \texttt{ concat } [4, 3] = [2, 1, 5, 4, 3].

Is it possible to make A sorted in non-decreasing order after applying the above operation at most once?

Note: An array X is a subsequence of an array Y if X can be obtained by deletion of several (possibly, zero or all) elements from Y.

EXPLANATION:

Let array B represent an array with same elements as of A but sorted in non-decreasing order(Sorted version of array A).
Observation 1: Subsequence P is a prefix of array B. If it is possible to sort A in non-decreasing order using the above defined operations then array B=P concat Q. This means P is a prefix of array B and Q has to be a suffix of array B. This also means that P and Q are sorted in non-decreasing order.
Claim: It is always optimal to take the largest prefix of array B which is also a subsequence of A as P.
Proof: Let K be the length of the largest prefix of array B which is also a subsequence of A and k be the length of subsequence P. Let the last element P has an index i in array A. Let’s say it is possible to obtain array B using this subsequence as P and remaining elements of array A as Q. Since k< K we must have an index j in array A such that A_j = B_{k+1}. B_{k+1} has to be the smallest (and equal to the first element) of subsequence Q and since Q is a sorted subsequence, array values at all indices of array A which are not included in P till (including) index j must be equal to B_{k+1}. We can remove index j(or one occurrence of A_j) from Q and append it to P, new P and new Q will still be sorted and it will still be possible to obtain array B from new P and new Q. Repeat the same procedure until k become equal to K.
Also it is not always possible to sort A by taking P with a length smaller than the optimal length(described above)

Example

Take A=[1,1,2,1]. B = [1,1,1,2]. Possible to sort it in non-decreasing order by taking P as [1,1,1] and Q as [2] but not possible to sort it in non-decreasing order by taking P as [1,1] and Q=[2,1] as Q is not sorted in non-decreasing order.

From these observations it is clear that we need to take P as the largest prefix of array B which is also a subsequence of A. Largest prefix of array B which is also a subsequence of A can easily be calculated by two pointers (or using Map data structure). Check whether the remaining elements (Q ) form a non-decreasing array. If they form a non-decreasing array output YES otherwise NO.

TIME COMPLEXITY:

O(Nlog(N)) for each test case.

SOLUTION:

Setter's solution 
#ifdef WTSH
    #include <wtsh.h>
#else
    #include <bits/stdc++.h>
    using namespace std;
    #define dbg(...)
#endif

#define int long long
#define endl "\n"
#define sz(w) (int)(w.size())
using pii = pair<int, int>;

const long long INF = 1e18;

const int N = 1e6 + 5; 

// -------------------- Input Checker Start --------------------

long long readInt(long long l, long long r, char endd)
{
    long long x = 0;
    int cnt = 0, 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)
        {
            if(is_neg)
                x = -x;
            if(!(l <= x && x <= r))
            {
                cerr << l << ' ' << r << ' ' << x << '\n';
                assert(false);
            }
            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, ' '); }
void readEOF() { assert(getchar() == EOF); }

vector<int> readVectorInt(int n, long long l, long long r)
{
    vector<int> a(n);
    for(int i = 0; i < n - 1; i++)
        a[i] = readIntSp(l, r);
    a[n - 1] = readIntLn(l, r);
    return a;
}

// -------------------- Input Checker End --------------------

int sumN = 0;

void solve()
{
    int n = readIntLn(2, 1e5);
    sumN += n;
    vector<int> a = readVectorInt(n, 1, 1e9);
    vector<int> b = a, rem;
    sort(b.begin(), b.end());
    int cur = 0;
    for(int i = 0; i < n; i++)
    {
        if(a[i] == b[cur])
            cur++;
        else
            rem.push_back(a[i]);
    }
    if(is_sorted(rem.begin(), rem.end()))
        cout << "YES\n";
    else
        cout << "NO\n";
}

int32_t main()
{
    ios::sync_with_stdio(0); 
    cin.tie(0);
    int T = readIntLn(1, 1e5);
    for(int tc = 1; tc <= T; tc++)
    {
        // cout << "Case #" << tc << ": ";
        solve();
    }
    assert(sumN <= 2e5);
    readEOF();
    return 0;
}
Editorialist's Solution 
#include "bits/stdc++.h"
using namespace std;
#define ll long long
#define pb push_back
#define all(_obj) _obj.begin(), _obj.end()
#define F first
#define S second
#define pll pair<ll, ll>
#define vll vector<ll>
ll INF = 1e18;
const int N = 1e5 + 11, mod = 1e9 + 7;
ll max(ll a, ll b) { return ((a > b) ? a : b); }
ll min(ll a, ll b) { return ((a > b) ? b : a); }
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
bool issorted(vll &v)
{
    for (int i = 1; i < v.size(); i++)
    {
        if (v[i] < v[i - 1])
            return false;
    }
    return true;
}
void sol(void)
{
    ll n, id = -1;
    cin >> n;
    vll v(n), p, q;
    map<ll, vll> mp;
    for (int i = 0; i < n; i++)
    {
        cin >> v[i];
        mp[v[i]].pb(i);
    }
    if (issorted(v))
    {
        cout << "YES\n";
        return;
    }
    vector<bool> vis(n, false);
    bool flag = true;
    for (auto x : mp)
    {
        for (auto y : x.S)
            if (y < id)
            {
                flag = false;
            }
            else if (y > id)
            {
                vis[y] = true;
                id = y;
            }
        if (!flag)
            break;
    }
    for (int i = 0; i < n; i++)
        if (!vis[i])
            q.pb(v[i]);
    if (issorted(q))
        cout << "YES\n";
    else
        cout << "NO\n";
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);
    int test = 1;
    cin >> test;
    while (test--)
        sol();
}
2

I can do it in O(N) using stack.

1 Like
3

Can anyone tell me where I m wrong in this approach
although I got the editorial yet I stuck with this approach

void solve( )
{
int long long n;cin>>n;
int long long cnt=0;
vector<pair<int long long,int long long>>arr(n);
bool f = true;
for(int i=0;i<n;i++){
cin>>arr[i].first;
arr[i].second = i;
if(i!=0 && arr[i]<arr[i-1]) f=false;
}
if(n==2 or f){
cout<<“YES\n”;
return;
}
stable_sort(arr.begin(),arr.end());

    for(int i=1;i<n;i++)
    {
        if(arr[i].second < arr[i-1].second)
        cnt++;
    }
    if(cnt<=1)cout<<"YES\n";
    else cout<<"NO\n";

}