Malay Keshav

Download Resume PDF

Malay Keshav

Netaji Subhas Institute of Technology

ACM ICPC Amritapuri 2013 – Problem E (Army Formation) – Solution

December 30, 2013, by malay.keshav, category ACM ICPC, All, C++, Editorial

The problem was to find the number of ways to fill a 2xN size grid with M colors such that no two cells with the same row or column have the same color.

This could be solved using DP or the Inclusion Exclusion Principle.
I solved it using the Inclusion Exclusion principle (after the contest ended sadly). Will also share the link to the discussion for the DP approach.

To solve with the inclusion exclusion principle , first fill the first row with N colours in X = bin(M,N) * N! ways. Where bin(M,N) is number of ways to choose N items from M distinct items.
Next fill the second row with N distinct colors such that exactly T columns are invalid. (Have the same color in one column).
This can be done in

Y = bin(N, T)*bin(M-T,N-T)* (N-T)! 

where,
- bin(N, T) is the number of ways to select T invalid columns.
- bin(M-T, N-T) is the number of ways to select (N-T) correct colors from (M-T) colours. It is M-T since T colors have already been selected for the invalid columns and we are filling the row with distinct colors.
- (N-T)! to permute the different arrangements.

Initially we start with T=0, where in no column is invlaid. In doing so we add the permutations where atleast one column is invalid.
So we subtract from this the amount for T=1. Again in doing so we subtract twice those permutations where atleast two columns are invalid.
This from inclusion-exclusion principle we obtain the final answer as follows :

Ans = X * Sum{(-1)^T * Y; for all T = 0 to N}

The final code for the problem is as follows :

 

#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>

#define MOD 1000000007
using namespace std;

long long modInv(long long x, long long m){
	long long t=0,newt=1,r,newr,temp,q;
	r = m;
	newr = x;
	while(newr != 0){
		q = r/newr;
		temp = t;
		t = newt;
		newt = temp - q*newt;

		temp = r;
		r = newr;
		newr = temp - q*newr;
	}
	if(r > 1)
		return -1;
	if(t < 0)
		t += m;
	if(t>=m)
		t = t%m;
	return t;
}

long long n_t[1005][1005];
long long m_f[1005];
long long fact[1005];
long long invFact[1005];
int main(){
	ios_base::sync_with_stdio(false);
	long long t,n,m;
	for(int i =0;i<1002;i++){
		n_t[i][0] = 1;
		n_t[0][i] = 0;
	}
	n_t[0][0] = 1;
	fact[0] = 1;
	invFact[0] = 1;
	for(int i =1;i<=1002;i++){
		fact[i] = fact[i-1] *i;
		invFact[i] = modInv(fact[i], MOD);
		if(fact[i]>=MOD)
			fact[i] = fact[i]%MOD;
		for(int j = 1;j<=1002;j++){
			if(i<j){
				n_t[i][j] = 0;
				continue;
			}
			n_t[i][j] = n_t[i-1][j] + n_t[i-1][j-1];
			if(n_t[i][j] >= MOD);
			n_t[i][j] = n_t[i][j]%MOD;
		}
	}
	cin >> t;
	long long ans,toAdd;
	bool isEven;
	while(t--){
		cin >> n >> m;
		if(m < n){
			cout << 0 <<endl;
			continue;
		}
		ans = 0;
		isEven = true;
		for(int i =0;i<=n;i++){
			toAdd =n_t[n][i]* fact[m-i];
			if(toAdd >= MOD)
				toAdd = toAdd%MOD;
			ans = ans + (toAdd*(isEven?1:-1));
			if(ans >= MOD)
				ans = ans%MOD;
			if(ans < 0)
				ans += MOD;
			isEven = !isEven;
		}
		ans = ans * fact[m];
		if(ans >= MOD)
			ans = ans%MOD;
		ans = ans * invFact[m-n];
		if(ans >= MOD)
			ans = ans%MOD;
		ans = ans * invFact[m-n];
		if(ans >= MOD)
			ans = ans%MOD;
		cout << ans << endl;
	}
	return 0;
}

The link to discussion for Dynamic Programming Approach

2 Comments

  1. rohit |

    Initially we start with T=0, where in no column is invlaid. In doing so we add the permutations where atleast one column is invalid.
    So we subtract from this the amount for T=1. Again in doing so we subtract twice those permutations where atleast two columns are invalid.

    Can you please explain this part again?
    When T==0 the result is our answer right? Can't we take all the possible permutation and subtract
    the (perm(T==1) + perm (T==2) + .....)?

    Reply
    • malay.keshav |

      I guess I should rephrase the sentence as "Next fill the second row with N distinct colors such that atleast T columns are invalid. (Have the same color in one column)."

      When T==0 the result is our answer right? Can’t we take all the possible permutation and subtract
      the (perm(T==1) + perm (T==2) + …..)?

      This won't work since when we add the permutation for T=0, we are adding all the permutation where 'atleast' 0 columns are invalid. To correct this we subtract from it the columns where atleast 1 column is invalid (T = 1). But in doing so we have subtracted the permutations where alteast 2 columns are invalid, twice. (This is a bit tricky part to realise, see if you can get it).
      This continues and hence by inclusion-exclusion principle we get the final result.

      Reply

So, what do you think ?