PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: satyam_343
Testers: apoorv_me, tabr
Editorialist: iceknight1093
DIFFICULTY:
TBD
PREREQUISITES:
Sorting
PROBLEM:
Find the longest subsequence of the given array A such that the length of the subsequence is divisible by the number of distinct elements within it.
EXPLANATION:
Let \text{freq}[x] denote the number of times x occurs in A.
Let’s fix the number of distinct elements in the subsequence to be d, and figure out the longest possible subsequence containing d distinct elements we can make.
Taking the maximum of this across all d will give us the answer.
Since we can take only d distinct elements, and we want the subsequence to be as long as possible, it’s clearly best to choose the d elements with largest frequencies.
Let these elements be x_1, x_2, \ldots, x_d.
Since we need to ensure that the subsequence length is a multiple of d, the best we can do is to pick the largest multiple of d that doesn’t exceed
\text{freq}[x_1] + \text{freq}[x_2] + \dots + \text{freq}[x_d].
Note that this will be exactly
where \left\lfloor \ \ \right\rfloor denotes the floor function.
Now, we do need to compute this for every d quickly.
To do that, note that the only “slow” part is knowing the sum of the d largest frequencies: if that sum is known, the remaining computation is constant time.
So, let’s sort the array \text{freq}!
This way, the largest frequencies will all form a suffix (or prefix, if sorted in reverse order) of the array, so their sum is easily computed while just iterating across the array.
TIME COMPLEXITY:
\mathcal{O}(N\log N) per testcase.
CODE:
Author's code (C++)
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define nline "\n"
#define all(x) x.begin(),x.end()
const ll MOD=998244353;
const ll MAX=500500;
void solve(){
ll n; cin>>n;
vector<ll> freq(n+5,0);
for(ll i=1;i<=n;i++){
ll x; cin>>x;
freq[x]++;
}
sort(all(freq));
reverse(all(freq));
ll ans=0,sum=0;
for(ll i=0;freq[i];i++){
ll now=i+1;
sum+=freq[i];
ans=max(ans,(sum/now)*now);
}
cout<<ans<<nline;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
ll test_cases=1;
cin>>test_cases;
while(test_cases--){
solve();
}
cout<<fixed<<setprecision(10);
cerr<<"Time:"<<1000*((double)clock())/(double)CLOCKS_PER_SEC<<"ms\n";
}
Editorialist's code (Python)
for _ in range(int(input())):
n = int(input())
a = list(map(int, input().split()))
freq = [0]*(n+1)
for x in a: freq[x] += 1
freq = sorted(freq)[::-1]
ans, tot = 0, 0
for i in range(1, n+1):
if freq[i-1] == 0: break
tot += freq[i-1]
ans = max(ans, i * (tot // i))
print(ans)