Balanced Clubs with Distinct Memberships
Autumn Tournament (2017)
Submission name: clubs.cpp
Problem summary
Assign N residents to clubs so every pair of residents differs in membership of at least one club. First minimize the number of clubs, then minimize the largest club size. A resident may join no clubs or several clubs. Output an optimal assignment.
Input
One integer N.
Output
Print the minimum club count and minimum possible largest size, then one line per club: its size followed by its resident IDs.
Constraints
2 ≤ N ≤ 100,000; residents are numbered 1..N.
Worked example
An independently prepared valid example; output follows the implementation below.
Input
5
Output
3 2 2 2 5 2 3 5 1 4
Solution analysis
- Represent a resident by a k-bit signature: bit j means membership in club j. All signatures must differ, so k=ceil(log₂N) is necessary and sufficient. For this smallest k, minimizing the total number of memberships gives a lower bound on the largest club. Choose N signatures with smallest popcounts: all layers below a boundary weight w, plus r signatures of weight w.
- Every complete popcount layer contributes equally to all clubs. Only the partial boundary layer needs balancing. Its total rw memberships force some club to receive at least ceil(rw/k). Give the first rw mod k columns a target of floor(rw/k)+1 and the rest floor(rw/k). We will reach exactly these balanced target loads without changing any signature weight or creating duplicates.
- Choose an overloaded column a and underloaded column b. Their actual loads satisfy load[a]>load[b]. Among selected weight-w masks containing a but not b, some mask x has its swapped mask y unselected; otherwise swapping a and b bijectively would imply the opposite load inequality. Replace x with y. One surplus and one deficit disappear. Repeat at most rw times.
- To find exchanges quickly, maintain candidate bitsets for each ordered pair of columns. A set bit at x means x is selected but its a/b swap is not. Changing a mask only affects candidates involving that mask or its swapped neighbor, so refresh O(k²) bits. Two summary levels locate a set bit without scanning the whole universe. With k≤17, the universe is at most 131072 masks and this exact construction is practical.
- Worked example N=5: k=3 and signatures 000,001,010,100,011 have club loads 2,2,1. They already achieve ceil(5/3)=2 because the minimum total membership is five. The displayed clubs distinguish all five residents, including resident 1 who belongs to none.
Why it works
The signature bound proves minimal k. Selecting the lightest masks minimizes total membership F, so every assignment has largest club at least ceil(F/k). Complete layers are balanced; the exchange lemma transforms the partial layer to target loads differing by at most one while preserving distinct signatures. Therefore its largest total club size equals ceil(F/k), attaining the lower bound.
Complexity: Let U=2^k and r be the partial-layer size. Sorting masks costs O(U log U·k) with the simple popcount comparator. Candidate initialization costs O(rk²), and at most rw≤rk exchanges cost O(rk³) in total. Output takes O(Nk). Bitset storage is O(k²U) bits plus O(Nk) output memberships. Here k≤17 and U<2N; this is an exact bounded-bit construction, not a claimed linear-time algorithm.
Watch out. Distinct signatures, not distinct club lists, encode the requirement. Optimize the club count before its maximum size. Exchanges must remain in the boundary weight layer and must not introduce an already selected mask. Use unsigned 64-bit shifts in candidate summaries. The number of printed residents on each club line must match its declared size.
Commented C++17 solution
An independently written complete program with standard headers.
#include<algorithm>
#include<cstdint>
#include<iostream>
#include<numeric>
#include<vector>
using namespace std;
int bits(int value){
int count=0;
while(value!=0){
value&=value-1;
++count;
}
return count;
}
int firstBit(uint64_t value){
int result=0;
while((value&1)==0){
value>>=1;
++result;
}
return result;
}
class Candidates{
int words,groups;
vector<vector<uint64_t>>data,summary;
vector<uint64_t>top;
public:
Candidates(int pairs,int universe)
:words((universe+63)/64),groups((words+63)/64),data(pairs,vector<uint64_t>(words)),
summary(pairs,vector<uint64_t>(groups)),top(pairs){
}
void set(int pair,int mask,bool enabled){
int word=mask/64;
uint64_t bit=uint64_t(1)<<(mask%64);
if(enabled){
data[pair][word]|=bit;
}
else{
data[pair][word]&=~bit;
}
int group=word/64;
uint64_t wordBit=uint64_t(1)<<(word%64);
if(data[pair][word]!=0){
summary[pair][group]|=wordBit;
}
else{
summary[pair][group]&=~wordBit;
}
uint64_t groupBit=uint64_t(1)<<group;
if(summary[pair][group]!=0){
top[pair]|=groupBit;
}
else{
top[pair]&=~groupBit;
}
}
int first(int pair)const{
if(top[pair]==0){
return -1;
}
int group=firstBit(top[pair]);
int word=group*64+firstBit(summary[pair][group]);
return word*64+firstBit(data[pair][word]);
}
};
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin>>n;
int k=0;
while((1<<k)<n){
++k;
}
int universe=1<<k;
vector<int>order(universe);
iota(order.begin(),order.end(),0);
stable_sort(order.begin(),order.end(),[](int a,int b){
return bits(a)<bits(b);
});
vector<int>code(order.begin(),order.begin()+n);
int weight=bits(code.back());
vector<int>partial,position(universe,-1),present(universe),load(k);
for(int resident=0;resident<n;++resident){
int mask=code[resident];
if(bits(mask)==weight){
partial.push_back(resident);
present[mask]=1;
position[mask]=resident;
for(int j=0;j<k;++j){
load[j]+=(mask>>j)&1;
}
}
}
int total=static_cast<int>(partial.size())*weight;
vector<int>target(k,total/k);
for(int j=0;j<total%k;++j){
++target[j];
}
Candidates candidates(k*k,universe);
auto refresh=[&](int mask){
for(int high=0;high<k;++high){
if(((mask>>high)&1)==0){
continue;
}
for(int low=0;low<k;++low){
if((mask>>low)&1){
continue;
}
int partner=mask^(1<<high)^(1<<low);
candidates.set(high*k+low,mask,present[mask]&&!present[partner]);
candidates.set(low*k+high,partner,present[partner]&&!present[mask]);
}
}
};
for(int resident:partial){
refresh(code[resident]);
}
while(true){
int high=-1;
int low=-1;
for(int j=0;j<k;++j){
if(load[j]>target[j]){
high=j;
}
if(load[j]<target[j]){
low=j;
}
}
if(high==-1){
break;
}
int oldMask=candidates.first(high*k+low);
if(oldMask==-1){
return 1;
}
int newMask=oldMask^(1<<high)^(1<<low);
int resident=position[oldMask];
// Exchange one membership without creating a duplicate resident signature.
present[oldMask]=0;
present[newMask]=1;
position[oldMask]=-1;
position[newMask]=resident;
code[resident]=newMask;
--load[high];
++load[low];
refresh(oldMask);
refresh(newMask);
}
vector<vector<int>>club(k);
for(int resident=0;resident<n;++resident){
for(int j=0;j<k;++j){
if((code[resident]>>j)&1){
club[j].push_back(resident+1);
}
}
}
size_t largest=0;
for(const auto&members:club){
largest=max(largest,members.size());
}
cout<<k<<' '<<largest<<'\n';
for(const auto&members:club){
cout<<members.size();
for(int resident:members){
cout<<' '<<resident;
}
cout<<'\n';
}
}