Need help in a problem

#1

This is question is asked in one of coding round during placement .
The Teacher wants to divide the group of students for singing competition . Each group will have one mic . If the number of mic is greater than the number of groups then teacher can select group and divide it such that the largest group among all groups is as small as possible .
Test case 1 :
n = 5 , k =7 ; k is number of groups mics and n is number of groups initially
[10 , 8 , 6 , 3 ,2 ] – > initially number of students in each group .
Output = 6 ;
we can divide the group of 10 into 5 ,5 —> [5,5, 8 ,6 ,3, 2]
again we divide the group of 8 into 4, 4 – > [5 ,5 , 4 ,4 ,6,3 ,2]
The numbers of groups equals to the number of mics Hence the largest group is of size 6 .

Test case 2 :
n = 5 ,k =9
[100 , 80 , 60 ,40 , 30] – > initially number of students in each group .
Output = 40
First divide the group of 100 into 80 , 20 – > [80 ,20 ,80 , 60 , 40 ,30]
Now divide the group of 80 into 40 ,40 --> [40 , 40 , 20 , 80 , 60 ,40 ,30]
again divide the group of 80 into 40, 40 – > [40 , 40 ,20 ,40 ,40 ,60 ,40 ,30]
divide the group of 60 into 30 ,30 --> [40, 40 , 20 , 40 ,40 , 30 ,30 ,40 ,30]
The numbers of groups equals to the number of mics Hence the largest group is of size 40 .

1 Like
#2

Possible way may be
Since you have to divide array at most (k-n) times to achieve end case.
So do this you can solve using priority queue. Loop for (k-n) times and in each iteration you have to pop an element and divide that into two and insert back into queue.
And After (k-n) iteration you have to just pop an element from queue which may be answer if I am correct.

If I am wrong anywhere please correct me.

1 Like
#3

What dose the answer represent or it’s use

#4

We can solve this using Binary Search.

Let X be the size of the largest group. So all elements in the array must be <= X. If any element is already <= X, we do not divide that group further. If a group is >X, then we keep on dividing the group such that all the newly formed groups have size <= X.

So, total number of groups (M)= Sum(ceil(A[i] / X)) for all 1 <= i <= N.

If M <= K, then we will check for lower values of X else go for higher values of X

2 Likes
#5

In what ratio to divide the element . like if poped element is 100 we can divide it into [90 ,10] , [80,20] ,[70 ,30] , [60, 40] , [50 ,50] . look closer to second test case if we divide the element into two equal halfs , the user output is 50 after all operations , and the judge output is 40 .

#6

This problem can be solved by normal binary search, you can divide the groups (k-n) times.
Now do a binary search on your answer values, first i would try the value 1 , i would count the number of divisions required over the array, if it is >(n-k), it is not a possible ans, now search on mid value that is 50 as max is 100 in your case,it is possible, next try 25 , not possible, next 37 not possible, next 43 possible, next 40 ,possible, next 41 not possible, so 40 will be your ans.

Time complexity , O(n logn).

A similar question
Atcoder beginner contest 174 E question

Try coding this before seeing code
My code for atcoder question
solution

1 Like
#7

Thanks :slight_smile:
This worked

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

signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL) ;

int n , k  ;
cin >> n >> k  ; 
vector<int> a(n) ; 
for(int i = 0; i < n ; ++i)
	cin >> a[i] ; 
int lo = 1, hi = 1e10 ; 
while(lo < hi)
{
	int mid = (lo + hi)/2  , r = 0 ; 
	for(int i = 0 ; i < n ; ++i)
	{
		r += ceil((double)a[i]/mid) ; 
	}

	if(r <= k)
	{
		hi= mid ;
	}
	else 	
		lo = mid +1 ; 
	
}
cout << hi ;

}

1 Like
#8

I wish I have upsolved this question :pensive:

1 Like
#9

Really sad ,U missed a good chance in the placement round, for a seen question. :pensive:

3 Likes
#10

By the way Thanks for tagging this problem :slight_smile:

#11

I was dividing in half but there is any test case where it might fail.

#12

yes second test case

#13

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

int main() {
priority_queue<vector>pq;
int n,m;
cin>>n>>m;
vectorv(n);
for(int i=0;i<n;i++)
{
cin>>v[i];
}
for(int i=0;i<n;i++)
{
vectortemp;
temp.push_back(v[i]);
pq.push(temp);
}
while(m>n)
{
vectortemp=pq.top();
pq.pop();
int sum=0;
for(int i=0;i<temp.size();i++)
{
sum+=temp[i];
}
int l=sum/(temp.size()+1);
int rem=sum%(temp.size()+1);
vectortemp2;
for(int i=0;i<temp.size()+1;i++)
{
if(rem>0)
{
temp2.push_back(l+1);
rem–;
}
else
{
temp2.push_back(l);
}
}
pq.push(temp2);
m–;

}
cout<<pq.top()[0];

return 0;

}

#14

Hey can you make a video on proper explanation or it’ll we very grateful if you explain it please

#15

which theory have be used?

#16

Hey Can Anyone Explain where this code getting failed for the above question (Here N is number of Mics and M is size of array and teams is array)

priority_queue pq;
for(int i=0;i<M;i++)
{
pq.push(teams[i]);
}
while(M<N)
{
int p=pq.top();
pq.pop();
if(p%2==1)
{
int k=p/2;
pq.push(k);
pq.push(k+1);
}
else
{
int k=p/2;
pq.push(k);
pq.push(k);
}
M++;
}
return pq.top();

#17

binary search. you can read here

#18

because dividing in half is not optimal solution.
for ex : we have 100 students in one group and we can divide them in 3 groups than
100 --> 70 30 – > 35 35 30 is better than 100 -->50 50 --> 25 25 50