How to approach a question like this?

1

You are an administrator of a society “Happy Colony”. You have a mxn matrix and are given the job of assigning houses to society members, where each cell repressents a house.Each member is of two kinds : either an Introvert or an Extrovert. Introverts do not like having neighbors. Their happiness zaps down by 30 points for every wall that they share with someone (could be either introvert or extrovert).

Extroverts love having neighbors. Their hapiness boosts by 20 points for every wall they share with someone(introvert or extrovert). There can be at most 4 neighbors( corresponding to the 4 sides of cells or houses ).Extroverts start with a happiness point of 40, while introverts start with happiness points of 120.Given values of m,n and the number of introverts and extroverts, find the maximum happiness points you can gain.

Constraints
1 <= m,n <= 10 and 0 <= I,E <= 10

  • Sample Input
    Test 1: m = 1, n=1,I =1, E=0.
    Test 2 : m=2, n=3, I=1, E=2.
  • Sample Output
    Test 1 : 120
    Test 2 : 240

For the second case, we can give the introvert 1 corner and keep the extroverts together. The points will be 120(base introvert) + 2x40 + 2x20 = 240. @anon55659401 @tmwilliamlin

2

Is this question from an ongoing contest?

1 Like
3

Link of the problem.

3 Likes
4

I’m ignoring until I see a link

2 Likes
5

@aryan12 @tmwilliamlin @l_returns No, its from a leetcode discussion thread.
Link - https://leetcode.com/discuss/interview-question/549871/Salesforce-SDE-or-2020-or-Hackerrank

6

According to me, it should be basic dynamic programming.

You initialize dp[n + 1][m + 1][i + 1][e + 1][3]

Over here, dp[i][j][k][l] shall store the maximum happiness you can achieve when you have put k introverts, l extroverts in the table from (1, 1) to (i, j). I don’t have the formula yet, but if you want to, I can think and make it up. Hope you can understand the logic :slight_smile:

The last one is to denote whether you have chosen an introvert, an extrovert or none. Basically dp[i][j][k][l][0] denotes nobody is living there, dp[i][j][k][l][1] denotes an introvert is living there, dp[i][j][k][l][2] denotes an extrovert is living there.

To be very honest, this is the very reason I see everything is <= 10. It can be easily be used into a 5d dp array.

P.S: I don’t know whether I am correct or not, so please notify me if I am wrong

7

When you transition from (i, j) to (i, j+1), not only do you need to check the state of (i, j), you also need to check (i-1, j+1). I think you need an additional dimension for the bitmask of chosen cells of the last row.

2 Likes
8

Oh, yes, true. The introvert and extrovert count will not help us there.

Edit: OMG! A 6 dimension dp. I have seen this for the 1st time, lol.