# Google Online challenge -Internship 2021( Today's round questions)

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.

``````if(mx >= sum - mx) sum - mx
else sum/2
``````

@dishantpawar95 I explicitly mentioned k = 2 twice.

3 Likes

Looks good for K = 2.

1 Like

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

2 Likes

yes, you are right

1 Like

Simple Binary Search

1 Like

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.

5 Likes

Is GOOC-18 the name of the contest being conducted in 2020?

I tried but was unable, actually I do not use hackerrant

Yep buddy.

That was really cool.

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