zephyr_23's blog

Fair Cut problem hackerrank.
By zephyr_23, history, 7 years ago, In English

I am trying to solve this problem ( https://www.hackerrank.com/contests/hourrank-12/challenges/fair-cut ). The editorial describes D.P approach which I am not able to understand. In the discussion, I saw a greedy approach but I am not able to prove why it works.

Can someone please help me in understanding the D.P approach to this question?

Thanks.

  • Vote: I like it
  • +17
  • Vote: I do not like it

Comments Comments (3)
| Write comment?
»
7 years ago, # |
  Vote: I like it +15 Vote: I do not like it

Here is my solution to the question:

It is easier to understand than the editorial logic I suppose.

Basically for dp(index, taken), I can either choose to include the element in A's set or in B's set. If I choose to include it in B's set, then I know that this element is greater than "taken" elements of A and lesser than "k-taken" elements that are yet to be included in A (since I sorted the array before calling the DP). Hence I remove the absolute sign and add taken*a[index] and subtract (k-taken)*a[index] from the answer, since that will be the contribution of this element towards the sum.

Similar formula can be worked out for choosing to include it in A's set.

You can see my implementation for the same.

→ Reply
  • »
    »
    7 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Thank you. I understood that when we put the element in B set, we add that element a[index] for all taken elements in A and subtract a[index] for future elements in A. But what about subtracting the values from A when we put a[index] into B to get the final sum? It will be a[index]-(taken elements in A) right ? In your code, whenever you add element to B, you add or subtract a[index] but not the actual elements of A set. I am bit confused.

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
      ← Rev. 2   Vote: I like it +15 Vote: I do not like it

      What you are trying to do will lead to double counting, right?

      Basically, I'm dealing with each index as it comes.

      what about subtracting the values from A when we put a[index] into B to get the final sum

      They were (will be) subtracted/added appropriately when they were (will be) included in A's set.

      For example, n=5 and k=1, I'm at dp(2, 0) and I choose to include the current element in A's set. Then, I add a[2] once and subtract a[2] thrice. This subtraction was for all the future elements that would be added to B. Thus, when I add any future index to B (in this case, all of them), I will only add their contribution.

      → Reply