HackerEarth Count the permutations problem solution

In this HackerEarth Count the permutations problem solution You are given two sequences A and B of length N. Determine the number of different ways to permute sequence A such that it is lexicographically smaller than the sequence B.

A sequence (X1,X2,…,Xk) is strictly lexicographically smaller than a sequence (Y1,Y2,…,YK), if there exists an index t (1 <= t <= K) such that:

Xt < Yt
Xr = Yr for all 1 <= r < t

A permutation X of A is considered different from another permutation Y of A, if there exists an index i (1 <= i <= N) such that Xi != Yi. For example:

If A = (1,1,1), then there is only one different permutation of A.

If A = (1,1,2,2), then there are 6 different permutations of A.

HackerEarth Count the permutations problem solution.

#include "bits/stdc++.h"
using namespace std;
#define fi first
#define se second
#define ll long long
#define dbg(v) cerr<<#v<<" = "<<v<<'n'
#define vi vector<int>
#define vl vector <ll>
#define pii pair<int,int>
#define vii vector < pii >
#define mp make_pair
#define db long double
#define pb push_back
#define all(s) s.begin(),s.end()
template < class P , class Q > ostream& operator<<(ostream& stream, pair < P , Q > v){ stream << "(" << v.fi << ',' << v.se << ")"; return stream;}
template < class T > ostream& operator<<(ostream& stream, const vector<T> v){ stream << "[ "; for (int i=0; i<(int)v.size(); i++) stream << v[i] << " "; stream << "]"; return stream;}
template < class T > T smin(T &a,T b) {if (a > b) a = b;return a;}
template < class T > T smax(T &a,T b) {if (a < b) a = b;return a;}
const int N = 1e6 + 5;
const int C = 2e5;
const int mod = 1e9 + 7;
int a[N];
int b[N];
int t[N];
void upd(int i,int v) {
    for (;i <= C;i += i&(-i))
        t[i] += v;
}
int que(int i) {
    int ans = 0;
    for (;i > 0;i -= i&(-i))
        ans += t[i];
    return ans;
}
int f[N];
int c[N];
int cnt[N];
int pow(int a,int b,int mod) {
    int ans = 1;
    while (b) {
        if (b & 1)
            ans = (1ll * ans * a) % mod;
        a = (1ll * a * a) % mod;
        b /= 2;
    }
    return ans;
}
int main(void) {
    int n;
    cin>>n;
    for (int i = 1;i <= n;++i)
        cin>>a[i],++cnt[a[i]];
    for (int i = 1;i <= n;++i)
        cin>>b[i];
    f[0] = c[0] = 1;
    for (int i = 1;i <= C + 55;++i) {
        f[i] = (1ll * f[i - 1] * i) % mod;
        c[i] = pow(f[i],mod - 2,mod);
    }
    int comb = f[n];
    for (int i = 1;i <= C;++i)
        comb = (1ll * comb * c[cnt[i]]) % mod;
    for (int i = 1;i <= C;++i)
        upd(i,cnt[i]);
    int ans = 0;
    for (int i = 1;i <= n;++i) {
        comb = (1ll * comb * pow(n - i + 1,mod - 2,mod)) % mod;
        ans = (ans + 1ll * comb * que(b[i] - 1)) % mod;
        comb = (1ll * comb * cnt[b[i]]) % mod;
        --cnt[b[i]];    
        if (cnt[b[i]] < 0)
            break;
        upd(b[i],-1);
    }
    cout << ans << 'n';
    return 0;
}

Second solution

import numpy as np
n=int(input())
a=np.array(list(map(int,input().split())))
b=np.array(list(map(int,input().split())))
assert (n,)==a.shape and (n,)==b.shape and n<=100000 and n>=1 and np.sum(a>200000)==0 and np.sum(b>200000)==0 and np.sum(a<0)==0 and np.sum(b<0)==0, exit(1)
dict={}
kind=0
for el in a:
    if el in dict:
        dict[el]+=1
    else:
        dict[el]=1
        kind+=1
bit=[0 for i in range(200002)]
def add(pos,x):
    pos+=1
    while pos<200002:
        bit[pos]+=x
        pos+=pos&-pos
def sum(pos):
    pos+=1
    r=0
    while pos:
        r+=bit[pos];
        pos-=pos&-pos
    return r
for el in a:
    add(el,1)
MOD=1000000007
ans=0
fac=[1  for i in range(200002)]
for j in range(1,200002):
    fac[j]=fac[j-1]*j
    fac[j]%=MOD
inv=[pow(fac[i],MOD-2,MOD) for i in range(200002)]
D=1
for u in dict:
   D*=inv[dict[u]]
   D%=MOD
for i in range(n):
    F=sum(b[i]-1)
    #print(F)
    F*=fac[n-i-1]*D
    #print(fac[n-i-1])
    F%=MOD
    ans+=F
    if b[i] in dict and dict[b[i]]!=0:
        D*=fac[dict[b[i]]]
        D*=inv[dict[b[i]]-1]
        D%=MOD
        dict[b[i]]-=1
        add(b[i],-1)
    else:
        break
ans%=MOD
print(str(ans))

HackerEarth Count the permutations problem solution

HackerEarth Count the permutations problem solution.

Second solution

Leave a Reply

Pages

Practice