DIVIDE_GROUP - Editorial

editorial
, ,
4

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

1 Like
7

The problem has also appeared in ABC227.
Link: link

1 Like
8

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.

9

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

2 Likes
10

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);
read(vec);

    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;

‘’’

11

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…

12

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

13

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
14

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

15

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
16

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

1 Like
17

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

18

Got it sir, thank you so much for replying …

19

Thank you sir

20

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
22

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

23

You’re right, updated.

24

I an also stuck at this point. Please explain anyone.

25

Imagine a 2D array with K rows and x columns. Each column represents a group.

Now start filling this array from top to bottom and left to right.
That is, first take the \min(x, A_1) candies and place them in the topmost row, from left to right. Since the number of columns is x, you will not go to the second row. Continue from the next cell but now fill in the \min(x, A_2) candies. And so on.

Since there are at most x of each type of candy, you will never add more than one candy of the same type to the same column. Thus, you fill up the whole array, satisfying the constraints.

3 Likes
26

Nice visualization. Thanks!!