PROBLEM LINK:
Author: Kunal Anand
Tester: Gaurav Katare
Editorialist: Kunal Anand
DIFFICULTY:
EASY-MEDIUM.
PREREQUISITES:
Greedy, Two-Pointers, Binary Search, Sorting
PROBLEM:
The problem is basically selecting at least ceil of half elements from each of N arrays in such a way that the maximum difference between any two selected elements is minimum.also we have to select maximum number of elements within the above constraint.
QUICK EXPLANATION:
The approach for this problem is to first select half smallest elements from each array and then start adding elements.try to decrease the difference by removing the smaller elements of the array whose count of selected elements is greater than half its size.if the difference can’t be minimized try to maximize the number of elements with that difference.
EXPLANATION:
First of all,create an array A by merging elements of N arrays.sort array A.
now keep two pointers namely left and right at the starting index of A. Start moving right pointer towards right, every time you visit any index check whether atleast ceil of half elements are selected from each arrays or not.if yes, then find the lower_bound of smallest element and upper bound of largest element in current window.Since the maximum difference is difference between smallest and largest element,so difference between lower_bound of smallest element and upper bound of largest element is the maximum window size for this maximum difference.Now start moving left pointer towards right until the condition of selection of atleast ceil of half elements from each of N arrays holds ,this way you are decreasing the maximum difference.
ALTERNATE EXPLANATION:
Alternatively,this problem can be solved using binary search.For each maximum difference we will check whether it is possible to select at least ceil of half elements from each array if yes, we will store the maximum numbers of elements that can be selected for this maximum difference and move to left.else move to right.
SOLUTIONS:
Setter's Solution
#include<bits/stdc++.h>
#include<assert.h>
using namespace std;
#define boost ios_base::sync_with_stdio(0); cin.tie(0)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define ll long long int
#define ld long double
#define pll pair<long long int,long long int>
int main()
{
boost;
ll t,cs;
t=1;
for(cs=1;cs<=t;cs++)
{
ll i,j,n,m,a,x,cn=0,ans=LLONG_MAX,len=0;
cin >> n;
vector<pll>arr;
vector<ll>idxs(n);
for(i=0;i<n;i++){
cin >> m;
for(j=0;j<m;j++){
cin >> a;
arr.pb(mp(a,i));
}
idxs[i]=ceil((double)m/2);
}
sort(arr.begin(),arr.end());
m=arr.size();
if(n==1&&m==2){
cout << arr[1].fi-arr[0].fi << " " << 2 << endl;
return 0;
}
cn=0;
i=0;
unordered_map<ll,ll>lef,rig;
while(i<m){
x=arr[i].fi;
lef[x]=i;
while(i<m&&arr[i].fi==x){
i++;
}
rig[x]=i-1;
}
i=j=0;
while(j<m){
while(cn==n&&j<i){
if(arr[i-1].fi-arr[j].fi<ans){
ans=arr[i-1].fi-arr[j].fi;
len=rig[arr[i-1].fi]-lef[arr[j].fi]+1;
}
else if(arr[i-1].fi-arr[j].fi==ans){
len=max(len,rig[arr[i-1].fi]-lef[arr[j].fi]+1);
}
if(idxs[arr[j].se]==0)
cn--;
idxs[arr[j].se]++;
j++;
}
if(i==m)
break;
if(idxs[arr[i].se]==1)
cn++;
idxs[arr[i].se]--;
i++;
}
cout << ans << " " << len << endl;
}
return 0;
}
Tester's Solution
#include <bits/stdc++.h>
#include <algorithm>
using namespace std;
#define boost ios_base::sync_with_stdio(false);cin.tie(NULL);
typedef long long int ll;
#define ass 1e18
#define MOD 1000000007
#define mp make_pair
#define pb push_back
#define pf push_front
#define pob pop_back
#define pof pop_front
#define fi first
#define se second
#define sz(x) (ll)x.size()
#define present(c,x) ((c).find(x) != (c).end())
#define debug(x) cout << #x << ": " << x << endl;
#define debug2(x,y) cout<<#x<<": "<< x<< ", "<< #y<< ": "<< y<< endl;
#define debug3(x,y,z) cout<<#x<<": "<< x<< ", "<< #y<< ": "<< y<<" "<<#z<<" : "<<z<< endl;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set tree<ll, null_type,less<ll>, rb_tree_tag,tree_order_statistics_node_update>
void solve()
{
ll n,a,b,cnt=0,ans=ass,len=0,m;
cin>>n;
ll arr[n+1];
vector<pair<ll,ll> >v;
for(int i=0;i<n;i++)
{
cin>>a;
arr[i]=(a+1)/2;
for(int j=0;j<a;j++)
{
cin>>b;
v.pb(mp(b,i));
}
}
sort(v.begin(),v.end());
m=sz(v);
if(n==1&&m==2){
cout << v[1].fi-v[0].fi << " " << 2 << endl;
return ;
}
unordered_map<ll,ll>rig,lef;
for(int i=0;i<sz(v);i++)
rig[v[i].fi]=i;
for(int i=sz(v)-1;i>=0;i--)
lef[v[i].fi]=i;
queue<pair<ll,ll> >q;
for(int i=0;i<sz(v);i++)
{
q.push(v[i]);
if(arr[v[i].se]==1)
cnt++;
arr[v[i].se]--;
while(!q.empty()&&cnt==n)
{
pair<ll,ll> p=q.front();
if(ans>v[i].fi-p.fi){
ans=v[i].fi-p.fi;
len=rig[v[i].fi]-lef[p.fi]+1;
}
else if(ans==v[i].fi-p.fi)
len=max(len,rig[v[i].fi]-lef[p.fi]+1);
q.pop();
if(arr[p.se]==0)
cnt--;
arr[p.se]++;
}
}
cout<<ans<<" "<<len<<"\n";
}
int main()
{
boost
ll t=1;
while(t--)
{
solve();
}
return 0;
}