SGIFT - Editorial

PROBLEM LINK:

Practice
Contest

Author: Srinjoy Ray
Tester: Ankur Kayal
Editorialist: Srinjoy Ray

DIFFICULTY:

EASY

PREREQUISITES:

Combinatorics

PROBLEM:

We are given N children and their goodness level A[i]. Santa will distribute some coins to each of the children. If two children have the same goodness level, then they must receive the same number of coins. If one of the children has a greater goodness level, then that child should receive more coins than the child with a lesser goodness level.
We have to output the number of ways in which Santa can distribute the coins. Also, we need print the distribution in which Santa spends the most coins.

EXPLANATION:

Since two children with the same goodness level must receive the same number of coins, the number of distinct integers in the distribution of Santa’s coins must equal to the number of distinct numbers in the goodness level of N children.

Santa has a total of N options for the array B as 1\leq B[i] \leq N. Let R be the number of distinct integers in the array A. Then the total number of ways in which Santa can distribute the coins is {N \choose R}.

Of these, the one in which Santa spends the most number of coins is where he gives N coins to the child/children with the highest goodness level, N-1 coins to the child/children with the second-highest goodness level, and so on.

We can use a vector of pair where the first part stores the goodness level and the second part stores the index number. We can sort this vector and make the required B array.

Time Complexity : O(NlogN)

SOLUTIONS:

Setter's Solution
#include<bits/stdc++.h>
using namespace std;
 
typedef long long ll;
#define mod 1000000007
 
const int N = 1e6+10;
ll fact[N];
 
ll power(ll a,ll n){
    ll res=1;
    while(n){
        if(n%2){
            res=(res*a)%mod;
        }
        a=(a*a)%mod;
        n/=2;
    }
    return res;
}
 
ll ncr(ll n, ll r){
    ll num,denom,inv_denom,ans;
    num = fact[n];
    denom = (fact[r]*fact[n-r])%mod;
    inv_denom = power(denom,mod-2);
    ans = (num*inv_denom)%mod;
    return ans;
}
 
void solve(){
    int i,j;
    int n;
    cin>>n;
    ll a[n],b[n],curr=n,unique=1,ways;
    for(i=0;i<n;i++){
        cin>>a[i];
    }
    vector<pair<int,int>> v;
    for(i=0;i<n;i++){
        v.push_back({a[i],i});
    }
 
    sort(v.begin(),v.end());
 
    for(i=v.size()-1;i>=0;i--){
        if(i<v.size()-1 && v[i].first != v[i+1].first){
            unique++;
            curr--;
        }
        b[v[i].second]=curr;
    }
 
    ways=ncr(n,unique);
 
    cout<<ways<<"\n";
 
    for(i=0;i<n;i++){
        cout<<b[i]<<" ";
    }
    cout<<"\n";
}   
 
int main(){
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t=1;
    cin>>t;
    
    fact[0]=1;
    for(int i=1;i<N;i++){
        fact[i]=(fact[i-1]*i)%mod;
    }
    
    while(t--){
        solve();
    }
}
 
Tester's Solution (cpp)
#include <bits/stdc++.h>
using namespace std;

#define nl '\n'

template<const int &MOD>
struct _m_int {
    int val;
 
    _m_int(int64_t v = 0) {
        if (v < 0) v = v % MOD + MOD;
        if (v >= MOD) v %= MOD;
        val = int(v);
    }
 
    _m_int(uint64_t v) {
        if (v >= MOD) v %= MOD;
        val = int(v);
    }
 
    _m_int(int v) : _m_int(int64_t(v)) {}
    _m_int(unsigned v) : _m_int(uint64_t(v)) {}
 
    explicit operator int() const { return val; }
    explicit operator unsigned() const { return val; }
    explicit operator int64_t() const { return val; }
    explicit operator uint64_t() const { return val; }
    explicit operator double() const { return val; }
    explicit operator long double() const { return val; }
 
    _m_int& operator+=(const _m_int &other) {
        val -= MOD - other.val;
        if (val < 0) val += MOD;
        return *this;
    }
 
    _m_int& operator-=(const _m_int &other) {
        val -= other.val;
        if (val < 0) val += MOD;
        return *this;
    }
 
    static unsigned fast_mod(uint64_t x, unsigned m = MOD) {
    #if !defined(_WIN32) || defined(_WIN64)
        return unsigned(x % m);
    #endif
        // Optimized mod for Codeforces 32-bit machines.
        // x must be less than 2^32 * m for this to work, so that x / m fits in an unsigned 32-bit int.
        unsigned x_high = unsigned(x >> 32), x_low = unsigned(x);
        unsigned quot, rem;
        asm("divl %4\n"
            : "=a" (quot), "=d" (rem)
            : "d" (x_high), "a" (x_low), "r" (m));
        return rem;
    }
 
    _m_int& operator*=(const _m_int &other) {
        val = fast_mod(uint64_t(val) * other.val);
        return *this;
    }
 
    _m_int& operator/=(const _m_int &other) {
        return *this *= other.inv();
    }
 
    friend _m_int operator+(const _m_int &a, const _m_int &b) { return _m_int(a) += b; }
    friend _m_int operator-(const _m_int &a, const _m_int &b) { return _m_int(a) -= b; }
    friend _m_int operator*(const _m_int &a, const _m_int &b) { return _m_int(a) *= b; }
    friend _m_int operator/(const _m_int &a, const _m_int &b) { return _m_int(a) /= b; }
 
    _m_int& operator++() {
        val = val == MOD - 1 ? 0 : val + 1;
        return *this;
    }
 
    _m_int& operator--() {
        val = val == 0 ? MOD - 1 : val - 1;
        return *this;
    }
 
    _m_int operator++(int) { _m_int before = *this; ++*this; return before; }
    _m_int operator--(int) { _m_int before = *this; --*this; return before; }
 
    _m_int operator-() const {
        return val == 0 ? 0 : MOD - val;
    }
 
    friend bool operator==(const _m_int &a, const _m_int &b) { return a.val == b.val; }
    friend bool operator!=(const _m_int &a, const _m_int &b) { return a.val != b.val; }
    friend bool operator<(const _m_int &a, const _m_int &b) { return a.val < b.val; }
    friend bool operator>(const _m_int &a, const _m_int &b) { return a.val > b.val; }
    friend bool operator<=(const _m_int &a, const _m_int &b) { return a.val <= b.val; }
    friend bool operator>=(const _m_int &a, const _m_int &b) { return a.val >= b.val; }
 
    static const int SAVE_INV = int(1e6) + 5;
    static _m_int save_inv[SAVE_INV];
 
    static void prepare_inv() {
        // Make sure MOD is prime, which is necessary for the inverse algorithm below.
        for (int64_t p = 2; p * p <= MOD; p += p % 2 + 1)
            assert(MOD % p != 0);
 
        save_inv[0] = 0;
        save_inv[1] = 1;
 
        for (int i = 2; i < SAVE_INV; i++)
            save_inv[i] = save_inv[MOD % i] * (MOD - MOD / i);
    }
 
    _m_int inv() const {
        if (save_inv[1] == 0)
            prepare_inv();
 
        if (val < SAVE_INV)
            return save_inv[val];
 
        _m_int product = 1;
        int v = val;
 
        while (v >= SAVE_INV) {
            product *= MOD - MOD / v;
            v = MOD % v;
        }
 
        return product * save_inv[v];
    }
 
    _m_int pow(int64_t p) const {
        if (p < 0)
            return inv().pow(-p);
 
        _m_int a = *this, result = 1;
 
        while (p > 0) {
            if (p & 1)
                result *= a;
 
            p >>= 1;
 
            if (p > 0)
                a *= a;
        }
 
        return result;
    }
 
    friend ostream& operator<<(ostream &os, const _m_int &m) {
        return os << m.val;
    }
};
 
template<const int &MOD> _m_int<MOD> _m_int<MOD>::save_inv[_m_int<MOD>::SAVE_INV];
 
extern const int MOD = int(1e9) + 7;
using mod_int = _m_int<MOD>;

vector<mod_int> _factorial = {1, 1}, _inv_factorial = {1, 1};
 
void prepare_factorials(int64_t maximum) {
    static int prepared_maximum = 1;
 
    if (maximum <= prepared_maximum)
        return;
 
    // Prevent increasing maximum by only 1 each time.
    maximum += maximum / 16;
    _factorial.resize(maximum + 1);
    _inv_factorial.resize(maximum + 1);
 
    for (int i = prepared_maximum + 1; i <= maximum; i++) {
        _factorial[i] = i * _factorial[i - 1];
        _inv_factorial[i] = _inv_factorial[i - 1] / i;
    }
 
    prepared_maximum = int(maximum);
}
 
mod_int factorial(int n) {
    if (n < 0) return 0;
    prepare_factorials(n);
    return _factorial[n];
}
 
mod_int inv_factorial(int n) {
    if (n < 0) return 0;
    prepare_factorials(n);
    return _inv_factorial[n];
}
 
mod_int choose(int64_t n, int64_t r) {
    if (r < 0 || r > n) return 0;
    prepare_factorials(n);
    return _factorial[n] * _inv_factorial[r] * _inv_factorial[n - r];
}
 
mod_int permute(int64_t n, int64_t r) {
    if (r < 0 || r > n) return 0;
    prepare_factorials(n);
    return _factorial[n] * _inv_factorial[n - r];
}
 
mod_int inv_choose(int64_t n, int64_t r) {
    assert(0 <= r && r <= n);
    prepare_factorials(n);
    return _inv_factorial[n] * _factorial[r] * _factorial[n - r];
}
 
mod_int inv_permute(int64_t n, int64_t r) {
    assert(0 <= r && r <= n);
    prepare_factorials(n);
    return _inv_factorial[n] * _factorial[n - r];
}

template<typename T_vector>
void output_vector(const T_vector &v, bool add_one = false, int start = -1, int end = -1) {
    if (start < 0) start = 0;
    if (end < 0) end = int(v.size());
 
    for (int i = start; i < end; i++)
        cout << v[i] + (add_one ? 1 : 0) << (i < end - 1 ? ' ' : '\n');
}

void run_cases() {
    int N;
    cin >> N;

    vector<int> A(N);
    for(auto &u: A)
        cin >> u;

    vector<pair<int,int>> order;
    for(int i = 0; i < N; i++) {
        order.emplace_back(A[i], i);
    }

    sort(order.rbegin(), order.rend());

    int id = N;

    vector<int> answer(N);
    for(int i = 0; i < N; i++) {
        if(i - 1 >= 0 && order[i - 1].first != order[i].first) id--;
        answer[order[i].second] = id;
    }
    id--;

    cout << choose(N, id) << '\n';

    output_vector(answer);

}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(nullptr);

    int tests = 1;
    cin >> tests;

    for(int test = 1;test <= tests;test++) {
        run_cases();
    }
}
Tester's Solution (python)
import sys

factorial = []
inverse_factorial = []

mod = 10**9+7

def inverse(n):
    return pow(n, mod - 2, mod)

def precompute(maximum):
    global factorial
    global inverse_factorial
    factorial = [1 for _ in range(maximum)]
    inverse_factorial = [1 for _ in range(maximum)]

    for i in range(2, maximum):
        factorial[i] = (factorial[i - 1] * i) % mod
        inverse_factorial[i] = inverse(factorial[i])

def choose(n, r):
    if r < 0 or r > n:
        return 0

    return (factorial[n] * inverse_factorial[r] * inverse_factorial[n - r]) % mod


def main():
    precompute(10**5+100)

    t = int(input())

    for _ in range(t):
        n = int(input())
        a = list(map(int, input().split()))

        cnt = n

        order = [[a[i], i] for i in range(n)]

        order.sort(reverse=True)

        answer = [0 for _ in range(n)]

        for i in range(n):
            if i - 1 >= 0 and order[i - 1][0] != order[i][0]:
                cnt-=1

            answer[order[i][1]] = cnt

        cnt-=1

        print(choose(n, cnt))
        print(*answer)


if __name__ == '__main__':
    input = sys.stdin.readline
    main()