 EASY-MEDIUM

# PROBLEM:

Given a permutation array of length N. Determine the number of ways to assign a direction (left or right) to each number such that it is possible to sort the permutation by applying the following operation any number of times - Select any element of the permutation and move it to the left/right end of the array, based on the assigned direction.

# EXPLANATION:

Let f(i) represent the number of good assignments, where the integers (NOT indices) 1,2,\dots,i are assigned direction `left` and integer i+1 is assigned direction `right`.
Then, the answer is equal to f(0)+f(1)+\dots+f(N).

Let us determine f(i) for a fixed i.
Since we assign the first i integers direction `left`, we can sort them by moving them to the left in increasing order.

Then, we only concern ourselves with sorting the remaining integers.
Let pos[x] represent the index of integer x in the permutation array.

Hint 1

If pos[i+2] < pos[i+1], integer (i+2) must be assigned direction `right` (Why?)

Generalising, if for any x, pos[x+1]<pos[x] and integer x is assigned direction `right`, all integers j\ (j > x) must be assigned direction `right` (the reasoning is similar as above and easily deducible).

Hint 2

If pos[i+1] < pos[i+2], integer (i+2) can be assigned either `left` or `right`.

Why?

On extrapolating, it is easy to see that, if pos[i+1]<pos[i+2]<\dots<pos[i+k], then all integers (i+1),(i+2),\dots,(i+k) will never have to be operated on, and hence can each have their direction set to either `left` or `right`.

Solution

Let S_x represent the greatest k such that pos[x]<pos[x+1]<\dots<pos[x+k]. This array can be computed efficiently using sliding window.

Then, from hint 2, it is clear that each of the integers (i+2),(i+3),\dots, (i+S_{i+1}) can be assigned either `left` or `right` (independent of other assignments). Let p represent the number of such integers.

From hint 1, it is then clear that all other integers (i+S_{i+1}+1), \dots, N can only be assigned direction `right`.

Then, the total number of good assignments equals

f(i)=2^p

which can be determined in O(1) with suitable precomputations!

# TIME COMPLEXITY:

Calculating array S can be done using sliding window in O(N). Computing f(i) can be done in O(1) by precomputing the powers of 2. Since we calculate f(i) for each valid i, the total time complexity is

O(N+N)\approx O(N)

per test case.

# SOLUTIONS:

Editorialist’s solution can be found here.

Author's solution
``````#include <bits/stdc++.h>
#define int long long
const int MOD = 1e9 + 7;
using pii=std::pair<int,int>;
using namespace std;

const int maxn = 1e6 + 5;

int t, n, a[maxn];
int32_t main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cin >> t;
for(int cases = 0; cases < t; cases++)
{
cin >> n;
vector<pii> order;
for(int i = 0; i < n; i++)
{
cin >> a[i];
order.push_back({a[i], i});
}
sort(order.begin(), order.end());
int ans = 0, cnt = 0, curways = 1;
for(int i = 0; i < n; i++)
{
curways *= 2;
curways %= MOD;
if(i == n - 1 || order[i].second > order[i + 1].second)
{
ans += curways;
ans %= MOD;
cnt++;
curways = 1;
}
}
cout << (ans - (cnt - 1) + MOD) % MOD << "\n";
}
return 0;
}
``````
Tester's solution
``````// Super Idol的笑容
//    都没你的甜
//  八月正午的阳光
//    都没你耀眼
//  热爱105°C的你
// 滴滴清纯的蒸馏水

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

#define int long long
#define ll long long
#define ii pair<ll,ll>
#define iii pair<ii,ll>
#define fi first
#define se second
#define endl '\n'
#define debug(x) cout << #x << ": " << x << endl

#define pub push_back
#define pob pop_back
#define puf push_front
#define pof pop_front
#define lb lower_bound
#define ub upper_bound

#define rep(x,start,end) for(auto x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--))
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()

#define indexed_set tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update>
//change less to less_equal for non distinct pbds, but erase will bug

mt19937 rng(chrono::system_clock::now().time_since_epoch().count());

const int MOD=1000000007;

ll qexp(ll b,ll p,int m){
ll res=1;
while (p){
if (p&1) res=(res*b)%m;
b=(b*b)%m;
p>>=1;
}
return res;
}

int n;
int arr;
int pp;

struct TREE{
int arr;
const int BUF=1000010;

void upd(int i,int k){
i+=BUF;
arr[i]=k;

while (i){
i>>=1;
arr[i]=max(arr[i<<1],arr[i<<1|1]);
}
}

int query(int i,int j){
i+=BUF,j+=BUF+1;
int res=0;

while (i<j){
if (i&1){
res=max(res,arr[i]);
i++;
}
if (j&1){
j--;
res=max(res,arr[j]);
}
i>>=1,j>>=1;
}
return res;
}
} tree;

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

int TC;
cin>>TC;
while (TC--){
cin>>n;
rep(x,0,n) cin>>arr[x];

vector<int> idx;
rep(x,0,n) idx.pub(x);

sort(all(idx),[](int i,int j){
if (arr[i]!=arr[j]) return arr[i]<arr[j];
else return i>j;
});

rep(x,0,n) tree.upd(x,idx[x]);

//rep(x,0,n) cout<<tree.query(x,x)<<" "; cout<<endl;

pp=-1;
rep(x,1,n){
if (arr[idx[x-1]]==arr[idx[x]]) pp[x]=pp[x-1];
else pp[x]=x-1;
}

int ans=1;

int curr=0;
rep(x,0,n){
while (curr<=pp[x] && tree.query(curr,pp[x])>idx[x]) curr++;

//cout<<curr<<" "<<x<<endl;
ans=(ans+qexp(2,x-curr,MOD))%MOD;
}

cout<<ans<<endl;
}
}
``````