Today I had Uber coding round.
There are $$$n$$$ buildings. We are given array $$$P$$$, which represents price of each building and array $$$a$$$, which represents area of each building. We need to choose $$$k$$$ buildings so that ratio of sum of prices and sum of areas is maximum.
For example :
$$$n=4,k=2$$$
Prices : 2 4 6 8
Area : 1 4 3 2
constraints $$$n \lt =1000; k \lt =n; p[i] \lt =1e6; a[i] \lt =1e6$$$
We can choose first and last building and ratio is (2+8)/(1+2)=3.3333 and it's maximum possible.
I think Greedily taking top K buildings by Ratio (price/area) and in case of 2 pairs having equal ratio, we can take the one with minimum numerator. Will this fail somewhere?
Suppose we have the following test case:
$$$P = [5, 100, 1], a = [1, 100, 2], K = 2$$$.
If we were to think greedily about the problem and select buildings based on their individual (price/area) ratios, you would end up with an answer of $$$\frac{105}{101}$$$, when it is possible to get an answer of $$$\frac{6}{3}$$$, which is better.
I wonder, how to think such type of test cases !?
What is max value for n and k?
n<=1000; k<=n; p[i]<=1e6; a[i]<=1e6
Then, maybe dp solution works. Let dp[x][i] represent max ratio if we used selected x buildings stored as {sum of prices, sum of areas} and we are at i. So, we can easily update dp[x][i] is either dp[x][i — 1] or {dp[x — 1][i — 1].prices + price[i], dp[x — 1][i — 1].areas + area[i]}.
This doesn't work for the same reason the greedy doesn't work. "Totalled ratio" lacks optimal substructure.
Try this example P=[1,100,5],a=[2,100,1],K=2.
but what if $$$dp[x][i-1] = a/b$$$, and dp[x][i] calcucated as $$$dp[x-1][i-1] = c/d$$$ that $$$a/b=c/d$$$?
which one should we take for $$$dp[x][i]$$$?
We can use binary search on the ratio.
If there exists an answer with ratio>=R then: (price_sum)/(area_sum) >= R => (price_sum) >= R(area_sum) => (price_sum) — R(area_sum) >=0 So for an answer to exist, there must exist a subset of K buildings such that the sum over (price-R*area) for all the buildings in the subset is non-negative.
Nice Solution!
How will you check that "there must exist a subset of K buildings such that the sum over (price-R*area) for all the buildings in the subset is non-negative."?
Can you please explain, I am not getting it.
UPD: Never mind, got it..
can you please tell me, how to find this subset!?
just replace every element with $$$price[i]-R*area[i]$$$, and sort in decreasing order. Check if the sum of first k is positive.
Awesome !
:)
Is there any place to submit the solution for this problem.
This problem seems equivalent to "Choosing $$$k$$$ out of $$$n$$$ point masses to maximize the $$$x$$$-coordinate of their COM", if we set the mass as area $$$a_i$$$, and the $$$x$$$-coordinate as ratio $$$x_i = \frac{P_i}{a_i}$$$ since we are trying to maximize $$$\frac{\sum_ix_i\cdot a_i}{\sum_ia_i} = \frac{\sum_iP_i}{\sum_ia_i}$$$.
That problem, I think, can be solved like this:
This takes $$$O(k)$$$ time in each iteration and $$$O(n\log n)$$$ preprocessing (sorting). Overall complexity $$$O(nk)$$$.
This solution is flawed.
Consider P=[1, 100, 100, 10], A=[2, 100, 100, 1], K=2. Your solution would give 110/101, but 11/3 is possible.
The reason your solution fails is because in any intermediate step of your algorithm if you drop a "mass", you never reconsider it, but that might be required later on.
Yeah the reduction is fine but I wasn't confident of my solution for the reduced problem which is why I said 'I think it may be solved like this'.
Seems it is wrong though. Thanks for pointing out!