# Ken and his Political Party codesprint problem

Can anyone have any idea how to solve this problem.

My Approach:

Sort the given array of N integers in non-increasing order.
We need to find the number of ways we can pick P elements from N elements such that the sum of those P elements is maximum.
One thing we can note is, the maximum sum can be attained by selecting the first P elements from the array after sorting.
What we need is the frequency of p^{th} Element.
Particularly, we need the frequency of p^{th} element in the whole array, say f_1 and the frequency of p^{th} element in the sub array [a_1,\ a_2,\ a_3,\dots,\ a_p], say f_2.

Hey, I just solved it in CPP. This is the first time I solved a problem first in CPP. Here’s the solution.

i got 70% correct solution but don’t able to figure out mistake.

#include <bits/stdc++.h>
#define ll long long
#define mod 1000000007
#define pb push_back
#define endl ‘\n’
using namespace std;

bool compare(pair<ll int,ll int>&a,pair<ll int,ll int>&b){
return a.first>b.second;
}

ll int comb(ll int n,ll int k){
ll int C[n+1][k+1];
for(ll int i=0;i<=n;i++){
for(ll int j=0;j<=min(i,k);j++){
if(j==0||j==i) C[i][j]=1;
else C[i][j]=(C[i-1][j-1]%mod+C[i-1][j]%mod)%mod;
}
}
return C[n][k]%mod;
}
int main() {
ios_base::sync_with_stdio(false), cin.tie(NULL);
int t;
cin>>t;
//cin.ignore(numeric_limits::max(), ‘\n’);
while(t–){
ll int n,p;
cin>>n>>p;
ll int arr[n];
for(ll int i=0;i<n;i++) cin>>arr[i];
map<ll int,ll int>mp; //O(NlogN)
for(ll int i=0;i<n;i++) mp[arr[i]]++;
vector<pair<ll int,ll int> >vec;
for(auto it:mp) vec.push_back({it.first,it.second});
sort(vec.begin(),vec.end(),compare);
ll int res=1;
for(ll int i=0;i<vec.size();i++){
if(vec[i].second<p){
p-=vec[i].second;
}
else if(vec[i].second==p){
res=1;
break;
}
else{
res=comb(vec[i].second,p)%mod;
break;
}
}
cout<<res<<endl;
}
return 0;
}

You made it too complex dude.

``````         map<ll int,ll int>mp;   //O(NlogN)
for(ll int i=0;i<n;i++) mp[arr[i]]++;
vector<pair<ll int,ll int> >vec;
for(auto it:mp) vec.push_back({it.first,it.second});
sort(vec.begin(),vec.end(),compare);
ll int res=1;
for(ll int i=0;i<vec.size();i++){ // Loop 1
if(vec[i].second<p){ // Statement 1
p-=vec[i].second;
}
else if(vec[i].second==p){
res=1;
break;
}
else{
res=comb(vec[i].second,p)%mod;
break;
}
``````

Why use `map`?
We need the frequency of p^{th} element only.
Also, why calculate the combinations \binom{n}{r} for all 1\le n\le 10^3 and 1\le r\le 10^3. You can just calculate the factorials and use the formula, right?
All I don’t understand in your code is Loop1 and Statement 1.

I got it.
Actually, I made it so complex.
Thanks.