Playing with P n C (PERMUTTT)
PROBLEM LINK:
Author: Pranav Kulkarni
Editorialist: Pranav Kulkarni
DIFFICULTY:
MEDIUM
PREREQUISITES:
Combinatorics, Bit Manipulation (optional)
PROBLEM:
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.
QUICK EXPLANATION:
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.
COMPLETE EXPLANATION:
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.
SOLUTIONS:
Solution
#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)
ans[c[i]].push_back(index);
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
// 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) {
computeAns(ans,arr,combo,i);
i++;
// 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]<<" ";
cout<<"\n";
}
return 0;
}