Problem C: Ddakji
Setter: ankit_907
Tester: mpsprasanth, ksenior2608
Difficulty:
EASY
Question:
The Salesman is playing Ddakji with Seong Gi-Hun.
There are N cardboards kept at distinct positions, the i^{th} of which can be flipped A_{i} times only. Gi-Hun gets 100 won with each flip. He has to play the game Q times and can select a series of consecutive positions to flip the cardboard kept at those positions .
The Salesman being clever, has already decided the series of positions, which Gi-Hun would have to select in all the games.
Since Gi-Hun is in huge debts, he should now stealthily arrange the cardboards in a manner so as to receive the maximum total sum of money.
Before actually arranging the cardboards, you must help him find the total number of distinct arrangements possible to obtain the maximum sum. Since the value can be large, find its modulo 10^9+7.
Note: Gi-Hun would only select the indices that The Salesman has already decided, even if their values are not the same as before.
Two arrangements are considered different if there exists at least one position where their values are not the same in both the arrangements.
Quick Explanation:
Since the indices which would be selected is given to us, we must place the largest element in the most frequently occuring index, second largest to the second most occuring index and so on…
Suppose multiple indices are selected equal number of times, placing the correspondingly large values in either place would give the same total.
Hence all we have to do is to check for the multiple positions with same frequency of getting selected, and permuting them, with the values we can place at those positions.
Note: Permuting equal elements wouldn’t make a new arrangement, even if multiple indices have the same frequency.
Detailed Explanation:
Our first task is to find the frequency of the indices. Since we are given a series of consecutive indices, we can use prefix sums.
short description
We can create a new array/vector named fre, with every element initialised with 0.
Given L,R for each query, we would increment the L^{th} index of fre with 1, and decrement (R+1)^{th} (if it exists) index by 1.
The value of fre[i] would be obtained by successively adding the vaues uptil that position.
The resultant value at the i^{th} position would give the frequency of the i^{th} index.
After having obtained the frequencies of the indices in the fre vector, we also have to keep track of the number of indices which have the same frequency.
We can define a vector hash to keep a track of this.
Now how to find the number of arrangements ?
Suppose we have 4 indices with the same value- The number of ways of arranging 4 distinct elements in those positions would be 4!. But what if 2 elements have the same value?
We can say that permuting those 2 elements would not cause any change in the number of distinct arrangements that we should obtain. Thus, the number of arrangements now would be 4!/2!.
Therefore our final answer would be \prod_{i=1}^{n}(fact[hash[i]])/(fact[ non\_distinct\_in\_hash[i]])\%(100000007)
fact denotes the precomputed factorial array.
As stated earlier, the largest frequencied should be placed at the most occuring indices - hence the count for distinct elements would be done on them.
Time Complexity
O(NLog(N)+Q)
- NLog(N): for sorting (and if used map/set )
- Q: For taking the Q queries as inputs
Setter's Code
// #pragma GCC optimize("Ofast")
// #pragma GCC target("avx")
using namespace std;
#define ll long long
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
// using namespace __gnu_pbds;
// typedef tree<ll, null_type, less_equal<ll>, rb_tree_tag,tree_order_statistics_node_update>ordered_set;
// using namespace chrono;
#include<bits/stdc++.h>
#define F first
#define S second
#define lld long double
#define vc vector<ll>
#define pb push_back
#define all(a) a.begin(),a.end()
const int MOD=(1e9 +7);
// const ll inf=(1000000000000000000);
typedef pair<ll,ll> pairs;
#define varval(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
ll power(ll a, ll b){ll res=1;a=a%MOD;while(b>0){if(b&1){res=(res*a)%MOD;b--;}a=(a*a)%MOD;b>>=1;}
return res;}
vc fact(100001);
void preC(){
fact[0]=1;
for(int i=1;i<=100000;i++)
fact[i]=(i*fact[i-1])%MOD;
return;
}
ll invf(ll a){
return power(a,MOD-2);
}
int main() {
// your code goes here
std::ios::sync_with_stdio(false);
cin.tie(NULL);cout.tie(NULL);
// auto start=high_resolution_clock::now();
// ll duration=duration_cast<milliseconds>(end-start).count();
ll t,n,i,j,k,f;
preC();
cin>>t;
for(int tc=1;tc<=t;tc++){
cin>>n;
vc a(n+1);
for(i=1;i<=n;i++)
cin>>a[i];
vc pre(n+2),hash(n+1);
ll q; cin>>q;
while(q--){
ll l,r;
cin>>l>>r;
pre[l]++;pre[r+1]--;
}
for(i=1;i<=n;i++)
pre[i]+=pre[i-1],hash[pre[i]]++;
ll ans=1;
vc par;
for(i=n;i>=0;i--){
ans=(ans*fact[hash[i]])%MOD;
if(hash[i]>0)
par.pb(hash[i]);
}
sort(a.begin()+1,a.end(),greater<ll>());
i=1;
for(auto curr:par){
unordered_map<ll,ll>m;
unordered_set<ll>st;
while(curr--){
st.insert(a[i]);
m[a[i]]++;i++;
}
for(auto x:st)ans=(ans*invf(fact[m[x]]))%MOD;
}
cout<<ans<<"\n";
// cout<<"Case #"<<tc<<": ";
}
return 0;
}
Tester's Code
#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll binexp(ll a, ll b,ll mod){
ll res = 1;
while(b > 0){
if (b & 1)res = (res * a) % mod;
b >>= 1;
a *= a; a %= mod;
}
return res;
}
int main()
{
ll mod=1000000007;
ll t,k;
cin>>t;
assert(t>=1 && t<=100000);
vector<ll>fact(100001),inv(100001);
fact[0]=1,inv[0]=1;
for(k=1;k<=100000;k++)
{
fact[k]=(fact[k-1]*k)%mod;
inv[k]=binexp(fact[k],mod-2,mod);
}
while(t--)
{
ll n,i,ans=1;
cin>>n;
assert(n>=1 && n<=100000);
ll a[n];
for(i=0;i<n;i++)
{
cin>>a[i];
assert(a[i]>=1 && t<=1e9);
}
sort(a,a+n);
vector<ll>pre(n+1);
ll q;
cin>>q;
assert(q>=1 && q<=100000);
while(q--)
{
ll l,r;
cin>>l>>r;
assert(l>=1 &&r>=1 && l<=n &&r<=n);
pre[--l]++;
pre[r]--;
}
for(i=1;i<n;i++)
{
pre[i]+=pre[i-1];
}
pre.pop_back();
sort(pre.begin(),pre.end());
unordered_map<ll,vector<ll>>mp;
for(int i=0;i<n;i++)
{
mp[pre[i]].push_back(a[i]);
}
for(i=0;i<mp.size();i++)
{
vector<ll>u=mp[i];
ll m=u.size();
ll temp=fact[m];
unordered_map<ll,ll>cnt;
int j;
for(j=0;j<u.size();j++)
{
cnt[u[j]]++;
}
for(auto it=cnt.begin();it!=cnt.end();it++)
{
temp=temp*inv[it->second];
temp=temp%mod;
}
ans=ans*temp;
ans=ans%mod;
}
cout<<ans<<"\n";
}
}
Hope you enjoyed solving the question !
Do feel free to share your feedbacks, discussing the question in the comments.
You can also head over to our forum AskREC in case of any ambiguites
Thank You !