This question was asked in a coding test.
There are K burners in the lab and N gas cylinders for the fuel. Each cylinder has a different capacity. Now in each lab K students come to use the K burners. When lab starts all students connect their burner to a cylinder and start the burner. Students can change the cylinder in between themselves and with the cylinder which is idle, exchange takes negligible time. Now find the maximum time possible for which all K burners can burn simultaneously. Exchange can be done only in integral units not fractional. (you can exchange at 1 second or 2 seconds, not at 1.5 seconds).
Constraints: N < 1e5 K < N X[i] < 1e9
Sample Case:
N=3, K=2, X=[3,3,3] Answer = 4
N=5 K=3, X = [10,10,6,9,3] Answer = 12
Isn't it $$$\lfloor \frac{\sum_{i = 1}^{N}X_i}{K} \rfloor$$$?
I think not always e.g.
Here the answer is 2.
I think we have to build K subsets from X such that sum of the minimum subset is maximized. I think we have to do binary search on the answer
Same cylinder may be used to satisfy different students at different times. For example, in a case like following
N=4, K=3, X = [2,2,2,4]
the answer would be 3 as the last cylinder can be given once at different times to all 3 students. So forming partitions of X beforehand may not work
Rough solution, might be some mistakes somewhere, do let me know if you find any.
Some basic intuition:
Each cylinder can clearly burn at most 1 unit / second, so if the burn time is $$$b$$$, then the true capacity of a cylinder is $$$min(x_{i}, b)$$$.
We can exchange cylinders freely at any integer instant of time. Combined with the true capacity constraint this gives us a simple check if a burn time $$$b$$$ is possible, by just checking if $$$\sum_{i = 0}^{n} {min(x_{i}, b)} \geq k \times b$$$.
(A different way of visualizing this is by considering a grid with $$$k$$$ rows and $$$b$$$ columns. We have $$$n$$$ items, the $$$i$$$-th of which can be placed at most $$$x_i$$$ times. Additionally we can't place the same item in the same column multiple times.)
This gives us an easy way to check the condition for a given $$$b$$$ in $$$O(n)$$$ time.
It might feel like binary search on $$$b$$$ won't work here because the $$$min(x_{i}, b)$$$ part might result in $$$b$$$ being impossible but $$$b + 1$$$ being possible. Logically such a case is clearly absurd, and mathematically we can prove that case is impossible:
If $$$\sum_{i = 0}^{n} {min(x_{i}, b)} \lt k \times b$$$, it is impossible for $$$count(x_{i} \gt b)$$$ to be $$$k$$$ or larger, since this would immediately contradict the aforementioned equation, so $$$\sum_{i = 0}^{n} {min(x_{i}, b + 1)} \leq \sum_{i = 0}^{n} {min(x_{i}, b)} + (k - 1)$$$ and therefore definitely less than $$$k \times (b + 1)$$$. So the range is monotonic and can be binary searched on yielding an $$$O(n log(nx))$$$ solution.
Agreed.But I have one doubt-
Consider current $$$b$$$, lets remove all $$$x_i(s)>=b$$$ so now we left with some $$$k'$$$ burners and $$$N'$$$ cylinders now problem becomes as $$$\sum_{i=0}^{N'} x_i>=b*k'$$$. Now problem is that if this hold how you can claim that you will always be able to distribute these $$$N'$$$ cylinders among $$$k'$$$ burners for $$$b$$$ time? Can you provide the proof for this?
Note that "Students can change the cylinder in between themselves and with the cylinder which is idle, exchange takes negligible time. $$$\ldots$$$ Exchange can be done only in integral units not fractional."
As far as I understand this means at every integer instant of time I can arbitrarily exchange cylinders. This means in essence I can arbitrarily choose the cylinders I want to use from the $$$j$$$-th to $$$(j + 1)$$$-th second as long as I don't use the same cylinder twice in the same second and a cylinder at most $$$x_i$$$ times. Since $$$x_i \lt b$$$ there clearly exists a valid arrangement.
Formal proof of a general construction which satisfies it:
We can view this assignment as a grid with $$$k'$$$ rows and $$$b$$$ columns where the cylinder in the cell (x, y) is the cylinder that will be used by the $$$x$$$-th burner between the $$$y$$$-th to $$$(y + 1)$$$-th second where clearly no column must use the same cylinder twice.
We can just fill this grid row by row (say left to right for a given row), using the $$$n'$$$ cylinders one at a time.
Since the grid has $$$b$$$ columns and $$$x_i \lt b$$$, while filling in this manner we will never have the same cylinder used for the same column multiple times.
Example taken from another comment for clarity of the construction — $$$n = 4$$$, $$$k = 3$$$, $$$X = [2,2,2,4]$$$, where $$$b = 3$$$
By your definition $$$n' = 3$$$, $$$k' = 2$$$ with the corresponding $$$n'$$$ remaining cells being $$$[2, 2, 2]$$$, or a sequence $$$[1, 1, 2, 2, 3, 3]$$$, which when filled row by row becomes:
1 1 2
2 3 3
which is a valid arrangement.
Ahh I can see it. Thank you!
We choose the largest K elements, and take the sum of rest of the elements and distribute this sum to these K elements maximizing the minimum value of these K elements, and finally return answer as the minimum value of the K elements. (This works in O(N*log(N)))
For example N=5, K=3 X=[10,10,10,11,12] Then the largest K elements are [10,11,12] and we try to maximize the minimum of these K elements by distributing 20(=10+10) in them (this could be done by binary search) here in optimal case the K elements will become [17,18,18] (or any K values which can give the minimum value as 17) and thus the answer will be 17.
Now this approach is just by some intution and I am not sure why exactly will this work but I tried stress testing it with a brute code that reduces the maximum K elements by 1 everytime it's possible and increasing the ans by 1, and probably both these codes doesen't seem to contradict on any test case.
If someone could explain why this should work or should not work please help...
(Your username checks out.)
I have a constructive proof to show that your approach is correct.
Let's call the $$$K$$$ largest cylinders main and the rest spare. The idea is to supplement the main cylinders with spare ones such that each spare one is used for at most one main cylinder (i.e., at most one student) at a time. Suppose the answer is $$$a$$$ seconds. Then we know, for each main cylinder, how many seconds to supplement it. We will process the main ones in some fixed order, one at a time. Likewise for the spare ones.
We will consider the time second by second in a loop: $$$1,2,3,\ldots,a-1,a$$$, $$$1,2,3,\ldots,a-1,a$$$, $$$1,\ldots$$$. For each time unit in the sequence, we schedule the current spare one to supplement the current main one. This way, each spare one will be used for at most two consecutive time intervals (exactly two if the whole interval breaks across the $$$a/1$$$ boundary). Since $$$a$$$ is greater than or equal to the smallest main one, the intervals will not overlap, and so each spare is used for at most one main cylinder at a time. For the rest of the time, the main ones are used. And there you have it.
The idea is related to a problem where you have to pair $$$2n$$$ colored socks so that each pair has two different colors. A solution exists if and only if each color appears at most $$$n$$$ times.
Could someone in brief explain how the answer for sample1 is 4?
Binary search over answer. For time t check
$$$\frac{\sum_{i=1}^{n} min(x_i,t)}{k} \geq t$$$