Ok I will prove it, so my memory doesn’t betray me.
Consider some set of n-1 type of objects. Each pair must consume at least one from this set. So we can show upper bound of sum-mx.
This upper bound can only be reached if we take one from mx, and one from the rest.
Therefore we can show if (mx >= sum-mx) answer is sum-mx.
Let’s consider it to be lesser. We are now considering the case where
mx < sum - mx.
Let’s take a pair from the largest two elements. Do a little bit of casework when 2*mx is just less than sum, there can only be 2 of mx, therefore we can reach a state where only one object is left.
So answer is
if(mx >= sum - mx) sum - mx
@dishantpawar95 I explicitly mentioned k = 2 twice.
Does Google invite the students for this challenge or are we supposed to apply for it?
Can you please share the link for the first problem. I wasn’t able to find that question in any site. Thanks in advance.
First we have to apply and then Google sends an email regarding the test
Can you please ellaborate your approach a bit.
Please tell how will you find if mid groups are possible??
Sure, say we want to check if we can make g groups from the array, then first convert array to a new array where ai = min(ai, g). Now I claim that the only necessary and sufficient condition to form g groups out of the array elements is that sum(array elements) >=k*g
I can prove this claim by finding a valid arrangement. Say above criteria is satisfied, then let us arrange element in a grid of g columns, and fill them row by row, one after another in the grid , obviously the number of rows would be at least k, and all columns are valid group partitions because no element in a column can repeat because it’s frequency is limited by g in the new array.
Hence we have a valid arrangement.
Is GOOC-18 the name of the contest being conducted in 2020?
I tried but was unable, actually I do not use hackerrant
can’t we use dijkstra’s algorithm for 1st question?
Hey did u got the link for the first question?
Hello, can u provide solution for those problems, I want to upsolve them.
Hy, can u provide link for first them bcoz I have searched toroughly in Google but couldnot find it