GIFTPAIRS - Editorial

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3

Author and Editorialist: Sahil Tiwari
Tester (C++): Abhishek Jugdar
Tester (Python): Aman Singhal

DIFFICULTY:

EASY-MEDIUM

PREREQUISITES:

Dynamic Programming , Combinatorics

PROBLEM:

Given an array A of size N, where elements are either unique or 0, find the number of ways to generate an array B such that if A_i \neq 0 then B_i = A_i and if A_i = 0 then B_i \neq i. Also B should contain all numbers from 1 to N.

EXPLANATION:

The question is basically a derangement problem. For any given array A, there are two types of undecided players:

  1. Player who’s mannequin is selected by some other player hence this player can select any of the available mannequins.
  2. Player who’s mannequins are still not selected and this player can select any mannequin except 1.

Let the number of type 1 players be i and the number of players of type 2 be j.
Answer to this parameter be dp[i][j].
Base Case:
dp[i][0] = factorial(i)
dp[0][j] = derangement(j)

Lets find ways such that j players find mannequins.

  1. The j^{th} player can select one of the j-1 players mannequins. Then i will increase by 1 since whoever amongst j-1 player’s mannequins was selected, becomes a type 1 player. Hence dp[i][j] = (j-1)*dp[i+1][j-2]
  2. The j^{th} player can select one of the i players mannequins. Hence dp[i][j] = i*dp[i][j-1]

We can precompute the answer for every pair of (i,j) and answer for every test case in linear time.

Time Complexity: O(max(N)^2 + \sum N )

ALTERNATE SOLUTION:

There exists an O(N) solution using the principle of Inclusion-Exclusion.

For the given pair of (i,j).

  1. There are total (i+j)! permutations.
  2. There are total ^jC_1 * (i+j-1)! permutations where at least one element is at restricted position.
  3. There are total ^jC_2 * (i+j-2)! permutations where at least two elements are at restricted position.
    .
    and so on…

This logic can be better understood by the derangement proof.

SOLUTIONS:

Setter's Solution
#include <bits/stdc++.h>
#define int long long int
using namespace std;

const int N = 1000;
int der[N + 1] = {0};
map<int,int> f;

int mod = 1e9+7;

// function to precompute dearrangement
void countDer(int N)
{
    der[1] = 0;
    der[2] = 1;
    for (int i = 3; i <= N; ++i)
        der[i] = ((i - 1) * (der[i - 1] + der[i - 2])) % mod;
}

int fact(int n){
    if(n<2)
        return 1;
    if(f.find(n) != f.end())
        return f[n];
    return f[n] = n*fact(n-1) % mod;
}

int dp[1001][1001];

signed main()
{

    for(auto &i: dp)
        for(auto &j: i)
            j = 0;

    countDer(N);
    // i = free set
    // j = restricting set
    for(int i=1;i<=1000;i++){
        dp[i][0] = fact(i);
        dp[0][i] = der[i];
        dp[i][1] = i*fact(i) % mod;
    }
    for(int j=2 ; j<=1000 ; j++){
        for(int i=1000 ; i>0 ; i--){
            if(i+j > 1000)
                continue;
            dp[i][j] = (dp[i][j] + i*dp[i][j-1] % mod) % mod;
            dp[i][j] = (dp[i][j] + (j-1)*dp[i+1][j-2] % mod) % mod;
        }
    }

    int t;
    cin >> t;
    while (t--)
    {
        int n;
        cin >> n;
        vector<int> b(n);
        for(int &i: b)
            cin>>i;
        map<int, int> c;
        for (int i : b)
            c[i]++;
        int r = 0, k = 0;
        for (int i = 1; i <= n; i++)
            if (b[i - 1] == 0 && c[i] == 0)
                r++;
            else if (b[i - 1] == 0)
                k++;
        // r = restricted set
        // k = non restricted set

        cout<<dp[k][r]<<endl;
    }
    cerr << "time taken : " << (float)clock() / CLOCKS_PER_SEC << " secs" << endl;
    return 0;
}
Tester's Solution (C++)
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

class Mint {
private:
	const static int mod = 1e9 + 7;
	int val;

public:
	Mint () {val = 0;}

	Mint(int _val) : val(_val) {}

	Mint& operator += (const Mint &o) {val = (val + o.val < mod ? val + o.val : val + o.val - mod); return *this;}
	template <typename T> Mint& operator += (const T &o) {return *this += Mint(o);} 

	Mint& operator -= (const Mint &o) {val = (val < o.val ? val - o.val + mod : val - o.val); return *this;}
	template <typename T> Mint& operator -= (const T &o) {return *this -= Mint(o);} 

	Mint& operator *= (const Mint &o) {return *this = (1LL * val * o.val >= mod ? (1LL * val * o.val) % mod : val * o.val);}
	template <typename T> Mint& operator *= (const T &o) {return *this *= Mint(o);} 

	friend bool operator == (const Mint &o1, const Mint &o2) {return (o1.val == o2.val);}
	template <typename T> friend bool operator == (const Mint &o1, const T &o2) {return (o1 == Mint(o2));}
	template <typename T> friend bool operator == (const T &o1, const Mint &o2) {return (Mint(o1) == o2);}

	friend bool operator != (const Mint &o1, const Mint &o2) {return (o1.val != o2.val);}
	template <typename T> friend bool operator != (const Mint &o1, const T &o2) {return (o1 != Mint(o2));}
	template <typename T> friend bool operator != (const T &o1, const Mint &o2) {return (Mint(o1) != o2);}

	friend Mint operator + (const Mint &o1, const Mint &o2) {return Mint(o1) += o2;}
	template <typename T> friend Mint operator + (const Mint &o1, const T &o2) {return Mint(o1) += o2;}
	template <typename T> friend Mint operator + (const T &o1, const Mint &o2) {return Mint(o1) += o2;}

	friend Mint operator - (const Mint &o1, const Mint &o2) {return Mint(o1) -= o2;}
	template <typename T> friend Mint operator - (const Mint &o1, const T &o2) {return Mint(o1) -= o2;}
	template <typename T> friend Mint operator - (const T &o1, const Mint &o2) {return Mint(o1) -= o2;}

	friend Mint operator * (const Mint &o1, const Mint &o2) {return Mint(o1) *= o2;}
	template <typename T> friend Mint operator * (const Mint &o1, const T &o2) {return Mint(o1) *= o2;}
	template <typename T> friend Mint operator * (const T &o1, const Mint &o2) {return Mint(o1) *= o2;}

	Mint power(long long y) {
		Mint ans = 1;
		Mint x = *this;

		while(y > 0) {
			if(y & 1) ans *= x;
			y >>= 1;
			x *= x;
		} 
		return ans;
	}

	Mint inverse () {return power(mod - 2);}

	Mint& operator /= (const Mint &o) {return *this *= Mint(o).inverse();}
	template <typename T> Mint& operator /= (const T &o) {return *this *= Mint(o).inverse();} 

	friend Mint operator / (const Mint &o1, const Mint &o2) {return Mint(o1) /= o2;}
	template <typename T> friend Mint operator / (const Mint &o1, const T &o2) {return Mint(o1) /= o2;}
	template <typename T> friend Mint operator / (const T &o1, const Mint &o2) {return Mint(o1) /= o2;}

	bool operator ~ () const {return ~(this -> val);}
	bool operator ! () const {return (this -> val == 0);}
	void operator ++ () {*this += 1;}
	void operator -- () {*this -= 1;} 
	void operator ++ (int) {*this += 1;}
	void operator -- (int) {*this -= 1;}

	friend ostream &operator << (ostream &os, const Mint &o) {os << o.val; return os;}
};

const int maxN = 1e3 + 5;
vector<Mint> fact(maxN), ivfact(maxN);
Mint nCr(int n, int r) {if(n < r || n < 0 || r < 0) return 0; return fact[n] * ivfact[r] * ivfact[n - r];}
 
void preprocess() {
	fact[0] = ivfact[0] = 1;
	for(int i = 1; i < maxN; i++) {
		fact[i] = fact[i - 1] * i;
		ivfact[i] = 1 / fact[i];
	}
}

int main() {
	ios::sync_with_stdio(false); cin.tie(0);
	preprocess();
	int t;
	cin >> t;
	while (t--) {
		int n;
		cin >> n;

		vector<int> a(n);
		for (int i = 0; i < n; i++) {
			cin >> a[i];
		}

		vector<bool> vis(n + 1, false);
		for (int x : a) {
			vis[x] = true;
		}

		int s1 = 0, s2 = 0;
		for (int i = 1; i <= n; i++) {
			if (vis[i]) continue;

			if (a[i - 1] == 0) s1++;
			else s2++; 
		}

		int rem = s1 + s2;

		if (rem == 0) {
			cout << 0 << '\n';
			continue;
		}

		Mint ans = fact[rem];
		for (int i = 1; i <= s1; i++) {
			Mint res = nCr(s1, i) * fact[rem - i];
			if (i & 1) ans -= res;
			else ans += res;
		}

		cout << ans << '\n';
	}
}
Tester's Solution (Python)
N=1000
mod=(10**9)+7

fact=[1 for i in range(N+1)]
inv=[1 for i in range(N+1)]
val=1
for i in range(1,N+1):
    val=(val*i)%mod
    fact[i]=val
    inv[i]=pow(fact[i],mod-2,mod)

def nCr(n,r):
    return (fact[n]*inv[r]*inv[n-r])%mod

def solve(A):
    n=len(A)
    s1,s2=0,0
    s=set(A)
    
    for i in range(1,n+1):
        if i not in s:
            if (A[i-1]==0):
                s1+=1
            else:
                s2+=1

    rem=s1+s2
    if (rem==0):
        return 0
    res=0
    for i in range(1,s1+1):
        if (i%2!=0):
            res=(res+((nCr(s1,i)*fact[rem-i])%mod))%mod
        else:
            res=(res-((nCr(s1,i)*fact[rem-i])%mod))%mod

    ans=(fact[rem]-res)%mod
    return ans

T=int(input())
for _ in range(T):
    n=int(input())
    A=list(map(int,input().split()))
    print(solve(A))
3 Likes

Can somebody provide me with some good derangement problems’ link?

1 Like

Here you have considered situation W.R.T “j” and made two cases

and what about cases W.R.T “i”?

like if I am prioritising “i” case , there will be two cases like →

CASE1 →
any one of i is choosing mannequins from the ones that does not belong to any of the "j"s
then dp[i][j] = i x dp[i-1][j]
CASE2 →
anyone of i is choosing mannequins from the ones that belong to one of the "j"s
then dp[i][j] = j x dp[i-1 + 1][j-1] = j x dp[i][j-1]

CONCLUSION →
so basically dp[i][j] = (i x dp[i-1][j]) + (j x dp[i][j-1]) (I have checked that it works as an alternate solution :innocent: Solution: 55348925 | CodeChef )

I am basically editing this comment! I got it now! Thanks for the wonderful problem man!

I am unable to understand why I am getting wrong answer can somebody help.
Solution link

https://www.codechef.com/viewsolution/55355415
Here’s your fixed version bro, I guess the problem was in modular subtraction.
ModularSub( a , b ) should be (a%mod - b%mod + mod)%mod ;