PROBLEM LINK:
Contest - Division 4
Contest - Division 3
Contest - Division 2
Contest - Division 1
DIFFICULTY:
EASY-MEDIUM
PREREQUISITES:
Combinatorics, Dynamic Programming, Sliding Window
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
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
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[1000005];
int pp[1000005];
struct TREE{
int arr[2000020];
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);
cin.exceptions(ios::badbit | ios::failbit);
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[0]=-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;
}
}