Largest Equal-Size Genre Playlists
National Olympiad — National round (2022 season)
Submission name: playlists.cpp
Problem summary
Partition all songs into equal-size playlists using at most two genres per playlist; every genre may mix with only one partner. Maximize size d and output an involution p.
Input
N and N positive genre counts.
Output
Maximum d and p satisfying p[p[i]]=i; any optimum witness is accepted.
Constraints
1≤N≤50000; 1≤a[i]≤100000.
Worked example
Input and output for the worked example discussed below.
Input
7 1 2 3 4 5 6 7
Output
7 6 5 4 3 2 1 7
Solution analysis
- A fixed genre needs a count divisible by d; a paired block needs its two counts to sum to a multiple of d. Thus nonzero remainder r must pair with d−r. Zero remainders can stand alone.
- For each divisor d of total S with d≤2max(a), require equal counts of complementary remainders, and an even count of remainder d/2 when d is even. Try candidates descending.
- For counts1…7, d=7 pairs1+6,2+5,3+4 and leaves7 alone. Construct p by pairing the stored indices from the successful remainder buckets.
Why it works
An involution divides genres into singleton and pair blocks. Divisibility of each block is exactly the remainder condition; matching buckets constructs a valid involution and divisible blocks can fill d-sized playlists. All feasible sizes divide S and respect the two-genre upper bound, so descending search finds the maximum.
Watch out. p must be an involution. Zero buckets need no pairing; half-modulus buckets need even size. Use long long for S.
Commented C++17 solution
An independently written complete program with standard headers.
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
// An involution divides genres into singleton and pair blocks.
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin>>n;
vector<int>a(n+1);
long long total=0;
int maximum=0;
for(int i=1;i<=n;i++){
cin>>a[i];
total+=a[i];
maximum=max(maximum,a[i]);
}
vector<int>candidates;
for(long long d=1;d*d<=total;d++){
if(total%d){
continue;
}
if(d<=2*maximum){
candidates.push_back(int(d));
}
if(total/d!=d&&total/d<=2*maximum){
candidates.push_back(int(total/d));
}
}
sort(candidates.rbegin(),candidates.rend());
int chosen=1;
for(int size:candidates){
vector<int>count(size,0);
for(int i=1;i<=n;i++){
count[a[i]%size]++;
}
bool valid=true;
for(int r=1;r<size;r++){
if(2*r==size){
valid&=count[r]%2==0;
}
else{
valid&=count[r]==count[size-r];
}
}
if(valid){
chosen=size;
break;
}
}
vector<vector<int>>bucket(chosen);
vector<int>p(n+1);
for(int i=1;i<=n;i++){
bucket[a[i]%chosen].push_back(i);
p[i]=i;
}
for(int r=1;2*r<=chosen;r++){
if(2*r==chosen){
for(int j=0;j<int(bucket[r].size());j+=2){
int x=bucket[r][j],y=bucket[r][j+1];
p[x]=y;
p[y]=x;
}
}
else{
for(int j=0;j<int(bucket[r].size());j++){
int x=bucket[r][j],y=bucket[chosen-r][j];
p[x]=y;
p[y]=x;
}
}
}
cout<<chosen<<'\n';
for(int i=1;i<=n;i++){
if(i>1){
cout<<' ';
}
cout<<p[i];
}
cout<<'\n';
}