Блог пользователя Mike_Mirzayanov_Is_Pussy

Автор Mike_Mirzayanov_Is_Pussy, 3 года назад, По-английски

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<=1000; k<=n; p[i]<=1e6; a[i]<=1e6$$$

We can choose first and last building and ratio is (2+8)/(1+2)=3.3333 and it's maximum possible.

  • Проголосовать: нравится
  • +10
  • Проголосовать: не нравится

»
3 года назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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?

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +4 Проголосовать: не нравится

    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.

»
3 года назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

What is max value for n and k?

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    n<=1000; k<=n; p[i]<=1e6; a[i]<=1e6

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится

      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]}.

      • »
        »
        »
        »
        3 года назад, # ^ |
          Проголосовать: нравится +6 Проголосовать: не нравится

        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.

      • »
        »
        »
        »
        3 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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]$$$?

»
3 года назад, # |
Rev. 2   Проголосовать: нравится +94 Проголосовать: не нравится

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.

»
3 года назад, # |
Rev. 2   Проголосовать: нравится -10 Проголосовать: не нравится

:)

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Is there any place to submit the solution for this problem.

»
3 года назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

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:

  • Let us assume that we have already chosen $$$k$$$ from the leftmost $$$i$$$ masses (sorted by $$$x$$$). If $$$k>i$$$ then we had picked all $$$i$$$ of them, and otherwise we had chosen some $$$k$$$ of these $$$i$$$ which gave the maximum value for the first $$$i$$$ masses.
  • Now, if we introduce $$$(i+1)^{th}$$$ mass, it is always a better strategy to drop one of the previous ones and pick this one instead.
  • But for deciding which one to drop, we would need to consider each of those $$$k$$$ as potentially droppable and compare which one gives best improvement.

This takes $$$O(k)$$$ time in each iteration and $$$O(n\log n)$$$ preprocessing (sorting). Overall complexity $$$O(nk)$$$.

  • »
    »
    3 года назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    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.

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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.

      • »
        »
        »
        »
        3 года назад, # ^ |
          Проголосовать: нравится +3 Проголосовать: не нравится

        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!