PERMUTTT - Editorial

Playing with P n C (PERMUTTT)



Author: Pranav Kulkarni
Editorialist: Pranav Kulkarni




Combinatorics, Bit Manipulation (optional)


Arranging N numbers into M arrays (no element repeats in a single array) of equal size such that union of any K arrays result in the sample set N, but union of any number of arrays less than K doesn’t satisfy this.


Let us now consider this simple case, let us say we have chosen k−1 arrays from M arrays at random, and we were to choose 1 more array to get the complete set. We know that the k-1 arrays cannot complete the set by themselves and hence the remaining M-k+1 arrays must have an element that the k−1 arrays don’t.


You may have got the gist of the problem from the quick explanation above.
So the overall idea is to distribute the elements in M arrays such that M-k+1 arrays must have a number which the remaining k-1 arrays don’t have.

So, here we will have C(M, k-1)combinations of each k-1 array groups. Hence N (no. of distinct elements) must also be C(M, k-1), any N other than this can result in no solution (But only the valid cases are considered in the problem). Therefore for a valid distribution, there should be M-k+1 copies of each element.

Distribute the elements by adding an element in M-k+1 arrays and exclude the element in remaining k-1 arrays.
To achieve this, you can consider C(M, M-k+1), and add an element to each selected array combination, preferably the current lowest element so that the answer itself is lexicographically non-decreasing.

To do the above in python is quite easy due to itertools module but I strongly recommend to try it on your own from scratch.


#include <bits/stdc++.h>
using namespace std;

void computeAns(vector<vector<int> > &ans,vector<int>c, int combo,int index)
    // add the current element (index) to the ans arrays whose bit is set in combo
    for (int i = 0; i < c.size(); ++i)                
        if ((combo >> i) & 1)

int main()

		freopen("input.txt", "r", stdin);
		freopen("output.txt", "w", stdout);

    //  n will always be m C k-1
	// input total distinct elements, number of arrays to be created, min arrays for union
    int n,m,k; cin>>n>>m>>k;
    vector<int> arr(m);
    // we are goining to add elements one by one in arrays from 0 to m-1
    for(int i=0;i<m;i++) arr[i]=i;  
    // to satisfy the min k condition we have to use m-k+1 copies of each distinct element
    int copies = m-k+1;             
	// set of bits (it will be used to select combinations)
    int combo = (1 << copies) - 1;       
    int i=0;
    vector< vector<int> > ans(m);
    // while combination bitset is smaller than total number of combinations over m
    while (combo < 1<<m) {          
		// refer to the link given at the end for approach for deriving combinations.
        int x = combo & -combo;
        int y = combo + x;
        int z = (combo & ~y);
        combo = z / x;
        combo >>= 1;
        combo |= y;
    for(int i=0;i<ans.size();i++)
        for(int j=0;j<ans[i].size();j++)
            cout<<ans[i][j]<<" ";
    return 0;


Selecting and Deriving Combinations