Author: Koushal Bhat
Tester: Ajinkya Kharosekar
Editorialist: Ajinkya Kharosekar
DIFFICULTY:
EASY
PROBLEM:
Given a permutation of 1 to N, you have to check whether it follows correct rules - Rule is initially the permutation is non-decreasing and you can swap an element of array with the element to its left and you can do this operation maximum three times to an element.
QUICK EXPLANATION:
Just observe what maximum three times swapping means ??
EXPLANATION:
Clearly when you swap element with its left element and do it maximum times i.e. 3 times, then that element shifts maximum 3 position to left. for e.g. initially if array is 1,2,3,4,5 and if we apply the operation maximum times to 5 then final array will be 1,5,2,3,4 then clearly we can see change in index is 5-2 = 3 (1-based indexing). So for every element we have to check what is change in its initial index(i.e. the element itself) and index now. If the differenece is more than 3, the rule is broken - answer will be ‘Yes’. Otherwise, the changes are well within rules - answer will be ‘No’.
Time Complexity:
Worst case - O(n)
Solutions:
Setter's Solution
#include <bits/stdc++.h>
using namespace std;
typedef signed long long int ll;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t=0;
cin>>t;
while(t--)
{
ll n;
cin>>n;
int flag=0;
ll temp=0;
ll count=0;
ll a[n]={0};
ll b[n]={0};
for(ll i=0;i<n;i++)
{
cin>>a[i];
}
for(ll i=0;i<n;i++)
{
b[i]=i+1;
}
for(ll i=0;i<n;i++)
{
b[i]=a[i]-b[i];
}
for(ll i=0;i<n;i++)
{
if(b[i]>3)
{
cout<<"Yes"<<'\n';
flag=1;
break;
}
}
if(flag!=1)
{
cout<< "No"<<'\n';
}
}
return 0;
}
Tester's Solution
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> p32;
typedef pair<ll,ll> p64;
typedef pair<double,double> pdd;
typedef vector<ll> v64;
typedef vector<int> v32;
typedef vector<vector<int> > vv32;
typedef vector<vector<ll> > vv64;
typedef vector<vector<p64> > vvp64;
typedef vector<p64> vp64;
typedef vector<p32> vp32;
ll MOD = 998244353;
double eps = 1e-12;
#define forn(i,e) for(ll i = 0; i < e; i++)
#define forsn(i,s,e) for(ll i = s; i < e; i++)
#define rforn(i,s) for(ll i = s; i >= 0; i--)
#define rforsn(i,s,e) for(ll i = s; i >= e; i--)
#define ln "\n"
#define dbg(x) cout<<#x<<" = "<<x<<ln
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define INF 2e18
#define fast_cin() ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
#define all(x) (x).begin(), (x).end()
#define sz(x) ((ll)(x).size())
ll arr1[100001];
ll arr2[100001];
ll arr2D[1001][1001];
vector<ll> vec;
void solve(){
ll n,m,a,b,c,d;
string s;
cin >> n;
forn(i,n) cin >> arr1[i];
bool flag = false;
forn(i,n)
{
if(arr1[i] != i+1)
{
if(abs(arr1[i]-(i+1)) > 3)
{
flag = true;
}
}
}
if(flag) cout << "Yes" << endl;
else
{
cout << "No" << endl;
}
}
int main()
{
fast_cin();
ll t = 1;
cin >> t;
for(int it=1;it<=t;it++) {
//cout << "Case #" << it+1 << ": ";
solve();
}
return 0;
}