# DIVIDE_GROUP - Editorial

Author: ayu_19
Tester & Editorialist: iceknight1093

2183

Binary search

# PROBLEM:

There are N types of candies, and you have A_i of the i-th type.
Find the maximum number of groups of candies you can make such that:

• Each group contains exactly K candies; and
• Within a group, all candies are distinct

# EXPLANATION:

If we can make x groups satisfying the condition, we can certainly make x-1 groups.
This allows us to use binary search to find the largest valid x.

Now, our task switches to the following:
Given x, is it possible to make exactly x groups of candies satisfying the given conditions?

To answer this, let’s look at each of the types of candies.
For the i-th type, we have A_i of them. However, we’re trying to make x groups, and each group can contain at most one of this type.
So, we can only really use \min(x, A_i) candies of type i.

This means the total number of candies usable by us is S_x = \sum_{i=1}^N \min(x, A_i).

Now, since each group should have size K, that means we need x\cdot K candies in total.
So, if S_x \lt x\cdot K, then surely making x groups is impossible.
On the other hand, if S_x \geq x\cdot K, it’s not very hard to see that making x groups is possible (since we have at most x of each type now).

This gives us a check in \mathcal{O}(N) for the binary search: compute S_x = \sum_{i=1}^N \min(x, A_i), and compare it against x\cdot K.

# TIME COMPLEXITY

\mathcal{O}(N\log {\left(\sum A_i\right)}) per testcase.

# CODE:

Author's code (C++)
#include "bits/stdc++.h"
using namespace std;

// #include <ext/pb_ds/assoc_container.hpp>
// using namespace __gnu_pbds;
// template<class T> using oset = tree<T,null_type,less_equal// for indexed_multiset */
// <T> ,rb_tree_tag,tree_order_statistics_node_update> ;    // order_of_key (k) -> # of elem strictly < k .
//                                                      // *(s.find_by_order(k)) -> element at index K .
#define int              long long
using   ll=              long long;
#define ld               long double
#define endl             '\n'
#define dbg(x)           cout<<#x<<" is -> "<<x<<endl
#define speed_           ios_base::sync_with_stdio(false),cin.tie(0), cout.tie(0)
#define pb               push_back
#define po               pop_back
#define mp               make_pair
#define sab(x)           x.begin(),x.end()
#define rsab(x)          x.rbegin(),x.rend()
#define ff               first
#define ss               second
#define sz(x)            (int)x.size()
#define sp(x)            fixed<<setprecision(x)
#define uni(edge)        edge.erase(unique(edge.begin(),edge.end()),edge.end());
#define to_up(x)         transform(sab(x),x.begin(),::toupper)
#define to_low(x)        transform(x.begin(),x.end(),x.begin(),::tolower)

const int M = 1000000007;
const int MM = 998244353;
const ld Pi= acos(-1);
const int N=1e6+5;
const int inf=1e18;

void simp(){

// dp?, graph?, bs on answer?, compress/sort queries/array?, stupid observation?

int m;
cin>>m;
int n;
cin>>n;
vector<int>a(m);
int sum=0;
for(int i=0;i<m;i++){
cin>>a[i];
sum+=a[i];
}
if(n>m){
cout<<0<<endl;
return ;
}
int l=1;
int r=(sum+n-1)/n;
r+=2;
while(l+1<r){

int mid=(l+r)/2;
int req=mid*n;
for(int i=0;i<m;i++){

req-=min(mid,a[i]);
if(req<=0)break;
}
if(req<=0){

l=mid;
}
else r=mid;
}
cout<<l<<"\n";

}

signed main(){

speed_;

// freopen("input06.txt", "r", stdin);
// freopen("ouput06.txt", "w", stdout);

int t;
t=1;
cin>>t;

int curr=1;
while(t--){

// cout<<"Case #"<<curr++<<": ";
simp();

}
return 0;
}

Editorialist's code (Python)
for _ in range(int(input())):
n, k = map(int, input().split())
a = list(map(int, input().split()))
lo, hi = 0, sum(a)//k + 1
while lo+1 < hi:
mid = (lo + hi)//2
have, need = 0, mid * k
for x in a: have += min(x, mid)
if have >= need: lo = mid
else: hi = mid
print(lo)

2 Likes

I don’t know how can someone not check if the problem is already present or not. It was already posted on this link. I guess this was the duty of the author

5 Likes

can i know my logic is correct or not
basically i reverse sort the array
push all elements in a max heap
push top k elements in a new vector v
get minimum value in the vector add ans with the min value
and push v[i]-minval if it is greater than 0 in priority queue again and get top k elements this repeats till the queue has less the k elements
im passing 2 test cases
hope anyone will help me
thanks

1 Like

Even i did the exact same thing ,if u find the reason why this logic fails. Please inform me.

1 Like

The problem has also appeared in ABC227.

1 Like

Apologies for not realizing that this problem already existed elsewhere. It’s a natural enough problem, but we didn’t find it while googling for it.

Why are we taking high =sum initially, and not 1e9?

2 Likes

If we keep on picking greatest k element from array and keep on making group is that will not lead to form the maximum number of groups?
Can you prove my claim wrong or give any counter example.

My Brute Force code
‘’’
ll int n,k;
cin>>n>>k;
vectorvec(n);

    priority_queue<int,vector<int>,greater<int>>pq;
ll int tot=0;
for(int i=0;i<n;i++)
{
if(pq.size()<k)
{
pq.push(vec[i]);
}
if(pq.size()==k)
{
tot+=pq.top();
ll int got=pq.top();
vector<int>v;
while(!pq.empty())
{
v.push_back(pq.top());
pq.pop();
}
for(auto x:v)
{
if(x-got>0)
{
pq.push(x-got);
}
}
}
}
cout<<tot<<endl;


‘’’

I also thought of like that. And tried finding online any data structure that supports these kind of queries. But I should have kept things simple…

If you get wrong answer with binary search in C++ check your left, right values
I set right = LLONG_MAX. But overflow may occur while calculating mid = (left+right)/2
So I used __int128 and got ac

You cannot take upto 1e9 , because sum of a[i] can go upto 1e14 so u have to take upto 1e15 , but if you will take 1e15 then mid*k can go upto 1e19 which will overflow so use unsigned long long


bool check(ll int mid,int k,vector<ll int>&vec)
{
ll int ans=0;
for(int i=0;i<vec.size();i++)
{
ans+=min(mid,vec[i]);
}
unsigned ll a=1ull*mid*k;
return ans>=a;
}
1 Like

@iceknight1093 Sir can you share the testcase where my code is failing?
https://www.codechef.com/viewsolution/97424774

Consider the input

1
5 2
4 4 4 1 1


Your algo will change the array like this, in each step:

Step 1: 4 4 4 1 1
Step 2: 4 1 1 0 0
Step 3: 3 1 0 0 0
Step 4: 2 0 0 0 0


And it can’t go further, so you are wasting 2 candies. But you can use all the candies by doing this:

Step 1: 4 4 4 1 1
Step 2: 4 3 3 1 1
Step 3: 3 3 2 1 1
Step 4: 2 2 2 1 1
Step 5: 2 1 1 1 1
Step 6: 1 1 1 1 0
Step 7: 1 1 0 0 0
Step 8: 0 0 0 0 0

2 Likes

@silenttkillerr @vedantmishra69
Both of your approaches also fail on the above testcase.

1 Like

I have also solved priority queue i still don’t understand why it didn’t got accepted if you find any case then please let me know

Got it sir, thank you so much for replying …

Thank you sir

I am confused with the above approach. Here we are just checking only if x*k<=sum(min(x,Ai)) but I feel like this is not enough condition to ensure that each group is getting different candies. Can somebody explain the logic behind it please?

2 Likes

Shouldn’t the time complexity be O(N log (sum of all elements)) ?

You’re right, updated.