advitiyabrijesh's blog

Hack the Interview — Global (The Fundraising Problem)
By advitiyabrijesh, history, 4 years ago, In English

I was trying to solve this problem using dp, with states(mask1, mask2, idx), where mask1 tells me how many tables I have covered so far and mask2 tells me what are the tables I have covered so far with 'idx'th group, but it will surely timeout, any other suggestions to improve complexity or are there any other solutions?

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

»
4 years ago, # |
← Rev. 2   Vote: I like it +5 Vote: I do not like it

So my solution was as follows:

1) Realize that if we select a group of students and the tables which they are serving, then the most optimal way to assign the students of this particular group would be to assign the student with the highest charm to k maximum generosity guests, then assign 2nd student with highest charm to the next k maximum guests generosity. So we can create a table best[i][mask] which will store the maximum possible donation if student group 'i' is assigned to a subset of guests tables(denoted by mask).

2) After computing the best table, now we need to assign masks to student groups such that if mask(i) is assigned to student group i, then mask(1) + mask(2) + ... + mask(m) = 2^(t) — 1 and for any two masks 'i' and 'j', mask(i) AND mask(j) = 0. This can be done using dp[mask] and iterating through all the submasks of mask for transition. Complexity: O(3^t)

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    Can you please elaborate the 2nd point, on how can I maintain this mask(i) AND mask(j) = 0 constraint, when I iterate over submasks.

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      Maintain dp[i][mask] which would store the maximum donation when student groups 1 to i has been assigned and mask tables have been assigned. Now iterate over all the sub masks of mask and update dp[i][mask] with max(dp[i][mask], dp[i — 1][mask ^ submask] + best[i][submask]). dp[m][2^t — 1] would be the answer. Complexity would be O(3^t * m) for this step.

      → Reply