Can anyone explain me their approach to this maximum diversity problem?
Contest got locked, can’t see other’s code.
Just use map and do iterate over the whole array once take a new array which will keep record of number of indices before current index I with same value as A[I] you can obtain that value from a map mp with mp[a[I]] .
Ok cool then do one thing in the new array obtained find first k maximum value indices
and we can put any arbitrary value at these indices I put 0 at these indices in the new array means 0 values coincides with current value at current index now again iterate over the whole array and just do one thing count (i- value at current index) do these for all indices and finally you will get the result as sum of all such values.
Don’t panic just see my solution it is very easy to understand obtain solution by clicking on my profile button.
Thanks for the help man, we kinda did same.
#include <bits/stdc++.h>
using namespace std;
int t , n , k;
long temp , c = 0;
int cD(vector<long> arr, int n)
{
int res = 0;
for (int i = 0; i < n; i++) {
// Move the index ahead while
// there are duplicates
while (i < n - 1 && arr[i] == arr[i + 1])
i++;
res++;
}
return res;
}
int main(){
cin>>t;
while(t--){
cin>>n>>k;
c = 0;
vector<long> vals;
priority_queue<long> cnts ;
for(int i = 0 ; i < n ; i++) { cin>>temp, vals.push_back(temp); }
sort( vals.begin() , vals.end() );
long prev = -1;
int res = cD(vals , n);
if ( n-res <= k ){
cout<<n*(n-1)/2<<endl;
continue;
}
unordered_map<long, int> mp;
for (int i = 0; i < n; i++)
mp[vals[i]]++;
for (auto x : mp) {
if ( x.second > 1 ) { cnts.push( x.second-1 ); }
}
while ( k > 0 && ! cnts.empty() ){
long tp = cnts.top();
cnts.pop();
if ( tp != 1 ) { cnts.push(tp-1); }
k--;
}
long a1 = n*(n-1)/2;
long a2 = 0;
while( ! cnts.empty() ){
long tp = cnts.top();
tp += 1;
cnts.pop();
a2 += tp * (tp-1)/2;
}
cout<<(a1 - a2)<<endl;
}
}Sadly, it’s locked too 
Wait it will open after sometime
For each K , try to relax the number with the maximum occurrence left.
I kept a std::set to get the element with the maximum occurrence and reduce the elements count by 1.
Assume this deleted element not to be equal to any other array element, and this shall do.
here’s the code
3 Likes
Thanks, understood your code.
I did exactly same, but the end formula to calculate result was different.
Thanks
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pb emplace_back
#define mp make_pair
#define f(i,a,n) for(int i=a ; i<n ; i++)
#define F first
#define S second
#define fast ios:: sync_with_stdio(false),cin.tie(0);
int32_t main(){
fast;
int t;
cin >> t;
while(t--)
{
int n,k;
cin >> n >> k;
map<int,int>m;
int a[n];
for(int i=0 ; i<n ; i++)
{
cin >> a[i];
m[a[i]]++;
}
priority_queue <int> p;
for(auto x : m) p.push(x.S);
while(k >0 && p.top() > 1)
{
k--;
int up = p.top();
p.pop();
p.push(1);
p.push(up - 1);
}
int ans = 0;
while(!p.empty())
{
ans += (n-p.top())*p.top();
p.pop();
}
cout << ans/2 << "\n";
}
}
1 Like