PSEUDOSORT-Editorial

devendra7700 · April 21, 2022, 11:28am

PROBLEM LINK:

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

Setter: Utkarsh Gupta
Tester: Aryan, Satyam
Editorialist: Devendra Singh

DIFFICULTY:

1067

PREREQUISITES:

None

PROBLEM:

An array A of length N is said to be pseudo-sorted if it can be made non-decreasing after performing the following operation at most once.

Choose an i such that 1 \le i \leq N-1 and swap A_i and A_{i+1}

Given an array A, determine if it is pseudo-sorted or not.

EXPLANATION:

In a non-decreasing array of length N there cannot be an index i such that 1 \le i \leq N-1 and A_i>A_i+1. Therefore we keep on traversing the array from the beginning till the end and as soon as we find an index i such that A_i>A_{i+1} we swap A_i\: with\: A_{i+1} and end traversing the array.
If the array is now non-decreasing i.e. for every index i such that 1 \le i \leq N-1, we have A_i\leq A_{i+1} , the initial array A was pseudo-sorted otherwise not.

TIME COMPLEXITY:

O(N) for each test case.

SOLUTION:

Setter's Solution

//Utkarsh.25dec
#include <bits/stdc++.h>
#define ll long long int
#define pb push_back
#define mp make_pair
#define mod 1000000007
#define vl vector <ll>
#define all(c) (c).begin(),(c).end()
using namespace std;
ll power(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll modInverse(ll a){return power(a,mod-2);}
const int N=500023;
bool vis[N];
vector <int> adj[N];
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){
            if(is_neg){
                x= -x;
            }

            if(!(l <= x && x <= r))
            {
                cerr << l << ' ' << r << ' ' << x << '\n';
                assert(1 == 0);
            }

            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 sumN=0;
void solve()
{
    int n=readInt(2,100000,'\n');
    sumN+=n;
    assert(sumN<=200000);
    vector <int> v;
    for(int i=1;i<=n;i++)
    {
        int c;
        if(i==n)
            c=readInt(1,1000000000,'\n');
        else
            c=readInt(1,1000000000,' ');
        v.pb(c);
    }
    for(int i=1;i<n;i++)
    {
        if(v[i]<v[i-1])
        {
            swap(v[i],v[i-1]);
            break;
        }
    }
    for(int i=1;i<n;i++)
    {
        if(v[i]<v[i-1])
        {
            cout<<"NO\n";
            return;
        }
    }
    cout<<"YES\n";
}
int main()
{
    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #endif
    ios_base::sync_with_stdio(false);
    cin.tie(NULL),cout.tie(NULL);
    int T=readInt(1,1000,'\n');
    while(T--)
        solve();
    assert(getchar()==-1);
    cerr << "Time : " << 1000 * ((double)clock()) / (double)CLOCKS_PER_SEC << "ms\n";
}

Tester-1's Solution

/* in the name of Anton */

/*
  Compete against Yourself.
  Author - Aryan (@aryanc403)
  Atcoder library - https://atcoder.github.io/ac-library/production/document_en/
*/

#ifdef ARYANC403
    #include <header.h>
#else
    #pragma GCC optimize ("Ofast")
    #pragma GCC target ("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx")
    //#pragma GCC optimize ("-ffloat-store")
    #include<bits/stdc++.h>
    #define dbg(args...) 42;
#endif

// y_combinator from @neal template https://codeforces.com/contest/1553/submission/123849801
// http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2016/p0200r0.html
template<class Fun> class y_combinator_result {
    Fun fun_;
public:
    template<class T> explicit y_combinator_result(T &&fun): fun_(std::forward<T>(fun)) {}
    template<class ...Args> decltype(auto) operator()(Args &&...args) { return fun_(std::ref(*this), std::forward<Args>(args)...); }
};
template<class Fun> decltype(auto) y_combinator(Fun &&fun) { return y_combinator_result<std::decay_t<Fun>>(std::forward<Fun>(fun)); }

using namespace std;
#define fo(i,n)   for(i=0;i<(n);++i)
#define repA(i,j,n)   for(i=(j);i<=(n);++i)
#define repD(i,j,n)   for(i=(j);i>=(n);--i)
#define all(x) begin(x), end(x)
#define sz(x) ((lli)(x).size())
#define pb push_back
#define mp make_pair
#define X first
#define Y second
#define endl "\n"

typedef long long int lli;
typedef long double mytype;
typedef pair<lli,lli> ii;
typedef vector<ii> vii;
typedef vector<lli> vi;

const auto start_time = std::chrono::high_resolution_clock::now();
void aryanc403()
{
#ifdef ARYANC403
auto end_time = std::chrono::high_resolution_clock::now();
std::chrono::duration<double> diff = end_time-start_time;
    cerr<<"Time Taken : "<<diff.count()<<"\n";
#endif
}

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) {
            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,' ');
}

void readEOF(){
    assert(getchar()==EOF);
}

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

bool isBinaryString(const string s){
    for(auto x:s){
        if('0'<=x&&x<='1')
            continue;
        return false;
    }
    return true;
}

// #include<atcoder/dsu>
// vector<vi> readTree(const int n){
//     vector<vi> e(n);
//     atcoder::dsu d(n);
//     for(lli i=1;i<n;++i){
//         const lli u=readIntSp(1,n)-1;
//         const lli v=readIntLn(1,n)-1;
//         e[u].pb(v);
//         e[v].pb(u);
//         d.merge(u,v);
//     }
//     assert(d.size(0)==n);
//     return e;
// }

const lli INF = 0xFFFFFFFFFFFFFFFL;

lli seed;
mt19937 rng(seed=chrono::steady_clock::now().time_since_epoch().count());
inline lli rnd(lli l=0,lli r=INF)
{return uniform_int_distribution<lli>(l,r)(rng);}

class CMP
{public:
bool operator()(ii a , ii b) //For min priority_queue .
{    return ! ( a.X < b.X || ( a.X==b.X && a.Y <= b.Y ));   }};

void add( map<lli,lli> &m, lli x,lli cnt=1)
{
    auto jt=m.find(x);
    if(jt==m.end())         m.insert({x,cnt});
    else                    jt->Y+=cnt;
}

void del( map<lli,lli> &m, lli x,lli cnt=1)
{
    auto jt=m.find(x);
    if(jt->Y<=cnt)            m.erase(jt);
    else                      jt->Y-=cnt;
}

bool cmp(const ii &a,const ii &b)
{
    return a.X<b.X||(a.X==b.X&&a.Y<b.Y);
}

const lli mod = 1000000007L;
// const lli maxN = 1000000007L;

    lli T,n,i,j,k,in,cnt,l,r,u,v,x,y;
    lli m;
    string s;
    vi a;
    //priority_queue < ii , vector < ii > , CMP > pq;// min priority_queue .

int main(void) {
    ios_base::sync_with_stdio(false);cin.tie(NULL);
    // freopen("txt.in", "r", stdin);
    // freopen("txt.out", "w", stdout);
// cout<<std::fixed<<std::setprecision(35);
T=readIntLn(1,1e3);
lli sumN = 2e5;
while(T--)
{

    n=readIntLn(2,min(sumN,100000LL));
    sumN-=n;
    a=readVectorInt(n,1,1e9);
    auto b=a;
    sort(all(b));
    dbg(a,b);
    lli cnt=0;
    for(lli i=0;i<n;i++){
        if(a[i]==b[i])
            continue;
        cnt++;
        if(i+1==n||a[i+1]!=b[i]){
            cnt=INF;
            break;
        }
        swap(a[i],a[i+1]);
    }
    cout<<(cnt<2?"yEs":"nO")<<endl;
}   aryanc403();
    readEOF();
    return 0;
}

Tester-2's Solution

#include <bits/stdc++.h>
using namespace std;
#ifndef ONLINE_JUDGE    
#define debug(x) cerr<<#x<<" "; _print(x); cerr<<nline;
#else
#define debug(x);  
#endif 
#define ll long long
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());  
 
 
/*
------------------------Input Checker----------------------------------
*/
 
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){
            if(is_neg){
                x= -x;
            }
 
            if(!(l <= x && x <= r))
            {
                cerr << l << ' ' << r << ' ' << x << '\n';
                assert(1 == 0);
            }
 
            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,' ');
}
 
 
/*
------------------------Main code starts here----------------------------------
*/
ll MAX=100000;
ll tes_sum=0;
vector<string> YS={"YES","yes","yES","YeS","yEs","YEs","Yes","yeS"};
vector<string> NO={"NO","no","No","nO"}; 
void solve(){  
    ll n=readIntLn(2,MAX);
    tes_sum+=n;
    vector<ll> a;
    ll x; 
    for(ll i=1;i<n;i++){  
        x=readIntSp(1,1000000000);
        a.push_back(x); 
    }
    x=readIntLn(1,1000000000);
    a.push_back(x); 
    vector<ll> b=a;
    sort(b.begin(),b.end());
    ll prev=-MAX; 
    for(ll i=0;i<n;i++){
        if(a[i]!=b[i]){   
            if(prev==i-1){
                prev=n;
            }
            else if(prev==-MAX){
                prev=i;
            }
            else{
                cout<<NO[rng()%4]<<"\n";
                return;
            }
        }
    }
    cout<<YS[rng()%8]<<"\n"; 
    return;
}
int main(){
    ios_base::sync_with_stdio(false);                         
    cin.tie(NULL);                              
    #ifndef ONLINE_JUDGE                 
    freopen("input.txt", "r", stdin);                                              
    freopen("output.txt", "w", stdout);  
    freopen("error.txt", "w", stderr);                          
    #endif         
    int test_cases=readIntLn(1,1000); 
    while(test_cases--){
        solve();
    }
    assert(getchar()==-1);
    assert(tes_sum<=200000);
    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>
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());
void sol(void)
{
int n;
cin>>n;
vll v(n);
bool canswap=true;
for(int i=0;i<n;i++)
{
  cin>>v[i];
  if(i && v[i]<v[i-1] && canswap)
  {
      canswap=false;
      swap(v[i],v[i-1]);
  }
}
bool issorted=true;
for(int i=1;i<n;i++)
{
    if(v[i]<v[i-1])
    issorted=false;
}
if(issorted)
cout<<"YES\n";
else
cout<<"NO\n";
return ;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL),cout.tie(NULL);
    int test=1;
    cin>>test;
    while(test--) sol();
}

aviral_dewan · April 25, 2022, 10:26am

What’s wrong with my approach:-

void solve()
{
int n;cin>>n;
int a[n];
int count = 0;
rep(i,0,n)
{
cin>>a[i];
if (i >= 1 and a[i-1] > a[i])
{
count++;
}
}

string s = "NO";
if (count <= 1)
    s = "YES";
else
    s = "NO";
cout << s;

}

aryanc403 · April 25, 2022, 12:02pm

2 1 1

jatin0308_adm · April 25, 2022, 12:46pm

Hey @aviral_dewan ,
your code is giving WA due to getting stuck on cases where after first swap elements might me smaller in right side.
for example
1
6
6 5 5 5 5 5
Your output is “YES” but correct output is “NO”.
According to your code it will swap 6,5
but 5 6 5 5 5 5
what you can do is do operation what question is saying like swapping just ones(if required) . If you find element Ai-1 > Ai just swap and break and check if array is sorted or not.

#include <iostream>
#include<bits/stdc++.h>
#include<deque>
#include<algorithm>
#include<math.h>
#include<sstream>
#include<stdio.h>
#include<bitset>
#include<string>
#include<vector>
#include<unordered_map>
#include<queue>
#include<set>
#include<fstream>
#include<map>
#define int long long int
#define ld long double
#define pi 3.1415926535897932384626433832795028841971
#define MOD 1000000007
#define MOD1 998244353
#define print(vec) for (int i = 0; i < vec.size(); i++) cout << vec[i] << " "; cout << "\n";
using namespace std;
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
int inf = 1e18;
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);
    }
};
#ifdef __SIZEOF_INT128__
ostream& operator << (ostream &os, __int128 const& value) {
    static char buffer[64];
    int index = 0;
    __uint128_t T = (value < 0) ? (-(value + 1)) + __uint128_t(1) : value;
    if (value < 0)
        os << '-';
    else if (T == 0)
        return os << '0';
    for (; T > 0; ++index) {
        buffer[index] = static_cast<char>('0' + (T % 10));
        T /= 10;
    }
    while (index > 0)
        os << buffer[--index];
    return os;
}
istream& operator >> (istream& is, __int128& T) {
    static char buffer[64];
    is >> buffer;
    size_t len = strlen(buffer), index = 0;
    T = 0; int mul = 1;
    if (buffer[index] == '-')
        ++index, mul *= -1;
    for (; index < len; ++index)
        T = T * 10 + static_cast<int>(buffer[index] - '0');
    T *= mul;
    return is;
}
#endif
int add(long long a, long long b) {return ((a % MOD) + (b % MOD)) % MOD;}
int subtract(long long a, long long b) {return ((a % MOD) - (b % MOD)) % MOD;}
int mult(long long a, long long b) {return ((a % MOD) * (b % MOD)) % MOD;}
int add1(long long a, long long b) {return ((a % MOD1) + (b % MOD1)) % MOD1;}
int subtract1(long long a, long long b) {return ((a % MOD1) - (b % MOD1)) % MOD1;}
int mult1(long long a, long long b) {return ((a % MOD1) * (b % MOD1)) % MOD1;}
int expo(int a, int b, int mod) {
    int res = 1;
    while (b > 0)
    {   if (b & 1)
            res = (res * a) % mod;
        a = (a * a) % mod;
        b = b >> 1;
    } return res;
}
int gcd(int a, int b) {
    if (b == 0) return a;
    return gcd(b, a % b);
}
int mminvprime(int a, int b) {
    return expo(a, b, b + 2);
}
int32_t main() {
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int tt;
    cin >> tt;
    while (tt--) {
        int n;
        cin >> n;
        vector<int> a(n);
        int c = 0;
        int j = -1;
        bool swapped = false;
        for (int i = 0; i < n; ++i)
        {
            cin >> a[i];
            if (i && a[i - 1] > a[i] && swapped == false)
            {
                swap(a[i - 1], a[i]);
                swapped = true;
            }
        }
        if (is_sorted(a.begin(), a.end())) cout << "YES\n";
        else cout << "NO\n";
    }
    return 0;
}

ritesh_gupta97 · April 25, 2022, 3:01pm

Why am I getting some errors in this?

#include <bits/stdc++.h>
using namespace std;

#define REP(i, a, b) for (int i = a; i <= b; i++)
typedef long long ll;

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

int t = 1;
cin >> t;
while (t--)
{
    int n, count=0;
    cin>>n;
    ll a[n];
    REP(i,0,n-1)
        cin>>a[i];
    for(int i=0; i<n-1; i++)
    {
        int q=0;
        if(a[i+1]<a[i])
        {
            count++;
            if(count>1)
                break;
            swap(a[i+1], a[i]);
        }

    }
    if(count>1)
        cout<<"NO\n";
    else
        cout<<"YES\n";
    
}

return 0;

}

ankurgattani · April 25, 2022, 5:28pm

#include <stdio.h>

int main(void) {
int t, n, temp;
scanf("%d", &t);
for(int i=0; i<t;i++)
{
scanf("%d", &n);
int ar[n];
int c=0;
for(int j =0; j<n; j++)
{
scanf("%d", &ar[j]);
}
// for(int j =1; j<n-1; j++)
// {
// if(ar[j-1]>ar[j])
// {
// temp=ar[j-1];
// ar[j-1] = ar[j];
// ar[j]=temp;
// break;
// }

   //     }
   int flag=0;
   int k=1;
   while(flag==0 && k<(n-1))
   {
       if(ar[k-1]>ar[k])
            {
                temp=ar[k-1];
                ar[k-1] = ar[k];
                ar[k]=temp;
                flag++;
            }
            k++;
   }
   for(int j=0; j<(n-1) ; j++) 
   {
       if(ar[j]>ar[j+1])
            c++;
   }
        if(c>0)
            printf("No\n");
        else if(c==0)
            printf("Yes\n");
}
return 0;

}

What’s wrong in my code? I passed 5 out 0f 7 testcases and couldn’t figure out where I’m going wrong. Please help me with this

prodigy078 · April 26, 2022, 5:18pm

1 2 4 1

ritesh_gupta97 · April 26, 2022, 5:47pm

Thanks!

pokemin · July 28, 2022, 7:49am

Why it is getting WA?

#include<bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin>>t;
while(t–)
{
int n,count=0;
cin>>n;
int a[n];
for(int i=0;i<n;i++)
{
cin>>a[i];
}
for(int i=0;i<n-1;i++)
{
if(a[i]>a[i+1])
{
swap(a[i],a[i+1]);
count++;
}
}
if(count>1)
{
cout<<“No”<<endl;
}
else
{
cout<<“Yes”<<endl;
}
}
return 0;
}