PERMUTATE - Editorial

pratik291219 · March 31, 2022, 5:38am

Problem link

Practice
Contest
Author: Pratik
Tester: Arjun
Editorialist: Pratik

DIFFICULTY:

HARD.

PREREQUISITES:

Sliding-windows

PROBLEM:

Given an array A of N positive integers, find the minimum number of operations required to transform array A to array B such that the following condition is satisfied.

Let the largest element in B be Y and the smallest be X .
Y (1 + Y) + X(1 - Y) is equal to two times the sum of all elements in B
In one operation you can change A[i] to any integer of your choice.

EXPLANATION:

The idea is to simply form a permutation of 1 to N, with some constant X added to all of them. So we use the Sliding Window technique before which we create a set S of unique elements in sorted order. Now for each element, we try to include elements that are in the range S[i] + N - 1 in the current window and all the other elements need to be changed. In this way we try to slide the window and compare the number of elements to be changed after each slide.

SOLUTIONS:

Setter's Solution

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

#define google(tc) cout<<“Case #”<<tc++<<": ";
#define FILE freopen(“input.txt”,“r”,stdin); freopen(“output.txt”,“w”, stdout);
#define GetSetBolt ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define ll long long int
#define LD long double

#ifndef LOCAL
#pragma GCC optimize(“Ofast”)
#pragma GCC target(“avx,avx2,fma”)
#pragma GCC optimization(“unroll-loops”)
#pragma GCC optimize (“O3”)
#pragma GCC target (“sse4”)
#endif

#define max3(a,b,c) max(a,max(b,c))
#define min3(a,b,c) min(a,min(b,c))
#define FF first
#define SS second
#define PB push_back
#define PF push_front
#define PPB pop_back
#define PPF pop_front
#define Endl endl

#define in(arr,n) for(int i=0;i<n;i++) cin>>arr[i];
#define in2(arr,n,m) for(int i=0;i<n;i++){ for(int j=0;j<m;j++) cin>>arr[i][j];}
#define dis(arr,n) for(int i=0;i<n;i++) cout<<arr[i]<<" “; cout<<endl;
#define dis2(arr,n,m) for(int ii=0;ii<n;ii++){for(int j=0;j<m;j++)cout<<arr[ii][j]<<” ";cout<<endl;}
#define tc int t=0;cin>>t; while(t–)

#define For(n) for(ll i=0;i<n;i++)
#define For0(x,z) for(ll x=0;x<z;x++)
#define Forx(x,z) for(x;x<z;x++)
#define all(x) x.begin(),x.end()
#define allr(x) x.rbegin(),x.rend()

#define toLower(s) transform(s.begin(),s.end(),s.begin(),::tolower)
#define toUpperr(s) transform(s.begin(),s.end(),s.begin(),::toupper)

#define sortAD(arr,n) sort(arr,arr+n, greater());
#define sortVD(v) sort(v.begin(), v.end(), greater());
#define sortA(arr) sort(arr,arr+n);
#define sortV(v) sort(v.begin(),v.end());

#define mem0(X) memset((X), 0, sizeof((X)))
#define memx(X,x) memset((X), x, sizeof((X)))
#define setbits(X) __builtin_popcountll(X)
#define precise(X) cout<<fixed << setprecision(X);
#define valid(x,y,row,col) (((x) >= 0 and (x) < row) and ((y) >= 0 and (y) < col))
#define debug(…) fprintf(stderr, VA_ARGS), fflush(stderr)
#define timer(d) for(long blockTime=NULL;(blockTime==NULL?(blockTime=clock())!=NULL:false); debug(“%s:%.4fs”,d,(double)(clock()-blockTime)/CLOCKS_PER_SEC))

// #ifndef ONLINE_JUDGE
// cerr<<“\ntime taken : “<<(float)clock()/CLOCKS_PER_SEC<<” secs”<<“\n”;
// #endif
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;
typedef pair<double,double> PDD;
typedef pair<string, string> PSS;
typedef pair<string, ll> PSL;
typedef long double lld;

typedef vector VI;
typedef vector VL;
typedef vector VD;
typedef vector VS;
typedef vector VVI;
typedef vector VVL;
typedef vector VVS;
typedef vector VPII;
typedef vector VPLL;
typedef vector VPSS;
typedef vector VPSL;

typedef map<int,int> MII;
typedef map<ll,ll> MLL;
typedef map<char,ll> MCL;
typedef map<char,int> MCI;
typedef map<char,ll> MCL;
typedef map<string,string> MSS;
typedef map<string,int> MSI;
typedef map<string,ll> MSL;

typedef unordered_map<int,int> UMII;
typedef unordered_map<ll,ll> UMLL;
typedef unordered_map<char,ll> UMCL;
typedef unordered_map<char,int> UMCI;
typedef unordered_map<char,ll> UMCL;
typedef unordered_map<string,string> UMSS;
typedef unordered_map<string,int> UMSI;
typedef unordered_map<string,ll> UMSL;
typedef unordered_map<int,bool> UMIIB;

typedef unsigned long long ull;

void _print(ll t) {cerr << t;}
void _print(int t) {cerr << t;}
void _print(string t) {cerr << t;}
void _print(char t) {cerr << t;}
void _print(lld t) {cerr << t;}
void _print(double t) {cerr << t;}
void _print(ull t) {cerr << t;}

template <class T, class V> void _print(pair <T, V> p);
template void _print(vector v);
template void _print(set v);
template <class T, class V> void _print(map <T, V> v);
template void _print(multiset v);
template <class T, class V> void _print(pair <T, V> p) {cerr << “{”; _print(p.ff); cerr << “,”; _print(p.ss); cerr << “}”;}
template void _print(vector v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << “]”;}
template void _print(set v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << “]”;}
template void _print(multiset v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << “]”;}
template <class T, class V> void _print(map <T, V> v) {cerr << "[ "; for (auto i : v) {_print(i); cerr << " ";} cerr << “]”;}

void solve(VI &arr, int n) {
UMIIB hash;
VI s;

For(n) {
    if (!hash[arr[i]]) {
        s.PB(arr[i]);
        hash[arr[i]] = true;
    }
}

sortV(s)

int i = 0;
int j = 0;
int ans = n;

while (i < s.size() && j < s.size()) {
    if (s[j] <= s[i] + n - 1)
        j++;
    else {
        int okay = j - i;
        ans = min(ans, n - okay);
        while (s[i] + n - 1 < s[j]) i++;
    }
}



ans = min(ans, n - (j - i));

cout << ans << "\n";

}

int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);

#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
freopen("errorf.txt" , "w" , stderr) ;
#endif

 tc
 {
    // code here
     ll n;
    cin >> n;
   VI arr(n);
    For(n)
    {
       cin >> arr[i];
    }
  solve(arr,n);

  }
return 0;

}

Tester's Solution