Header Ad

HackerEarth Supreme Subset problem solution

In this HackerEarth Supreme Subset problem solution we have given a multiset of integers having cardinality n, find its Supreme Subset.
A supreme subset of a given multiset is one of its subsets in which -

if any two elements i, j are chosen from the subset, |i - j| is divisible by m, where x represents the absolute value of x.
it has the highest cardinality/size among all candidate subsets satisfying condition 1.
If there are multiple subsets satisfying the above 2 conditions, the supreme subset is the one that is smallest by set comparison.
Finding order by set comparison - Given two sets of the same size, the smaller one is defined to be the one which is lexicographically smaller when both sets are arranged in non-decreasing order, for example, the set {3,2,1} is smaller than {3,2,2}.


HackerEarth Supreme Subset problem solution


HackerEarth Supreme Subset problem solution.

#include <bits/stdc++.h>
using namespace std;

#define ff first
#define ss second

int main(){
int i,j,n,m,el,maxi,flag,mod;
vector<int> ans;
map<int, int> counter;
int arr[100005];
scanf("%d %d", &n, &m);
for(i = 0; i < n; i++){
scanf("%d", &arr[i]);
counter[arr[i] % m]++;
}

maxi = 0;
for(auto el : counter)
maxi = max(maxi, el.ss);

sort(arr, arr + n);
flag = 0;
mod = 0;
for(i = 0; i < n; i++){
if(flag == 0 && counter[arr[i] % m] == maxi){
flag = 1;
ans.push_back(arr[i]);
mod = arr[i] % m;
}
else if(flag == 1 && arr[i] % m == mod){
ans.push_back(arr[i]);
}
}
sort(ans.begin(), ans.end());
cout << ans.size() << endl;
for(auto el : ans)
printf("%d ", el);
printf("\n");

return 0;
}

Second solution

#include <bits/stdc++.h>
#define ff first
#define ss second

using namespace std;


unordered_map< int, vector<int> > arr;

void verify(int n, int l, int r){
assert(n >= l && n <= r);
}



int main(){

arr.reserve(1024*256);
arr.max_load_factor(0.25);

int n, m;
scanf("%d%d", &n, &m);
verify(n, 1, 1000*10000);
verify(m, 1, 100000*10000);

while(n--){

int val;
scanf("%d", &val);
verify(val, 1, 100000*10000);
arr[val % m].push_back(val);
}

vector<int> ans;
for(auto it : arr){

vector<int> &temp = it.ss;
sort(temp.begin(), temp.end());

if((int)temp.size() > (int)ans.size()){
ans = temp;
}
else if((int)temp.size() == (int)ans.size() && temp < ans){
ans = temp;
}
}

printf("%d\n", (int)ans.size());
for(auto it : ans)
printf("%d ", it);
return 0;
}


Post a Comment

0 Comments