Skip to content

1659. Maximize Grid Happiness 👍

  • Time: $O(mn \cdot 2^m2^n)$
  • Space: $O(mn \cdot 2^m2^n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
class Solution {
 public:
  int getMaxGridHappiness(int m, int n, int introvertsCount,
                          int extrovertsCount) {
    return getMaxGridHappiness(m, n, 0, 0, 0, introvertsCount, extrovertsCount);
  }

 private:
  int dp[25][64][64][7][7] = {};

  // Calculates the cost based on left and up neighbors.
  //
  // The `diff` parameter represents the happiness change due to the current
  // placed person in (i, j). We add `diff` each time we encounter a neighbor
  // (left or up) who is already placed.
  //
  // Case 1: If the neighbor is an introvert, we subtract 30 from cost.
  // Case 2: If the neighbor is an extrovert, we add 20 to from cost.
  int getPlacementCost(int n, int i, int j, int inMask, int exMask, int diff) {
    int cost = 0;
    if (i > 0) {
      if ((1 << (n - 1)) & inMask)
        cost += diff - 30;
      if ((1 << (n - 1)) & exMask)
        cost += diff + 20;
    }
    if (j > 0) {
      if (1 & inMask)
        cost += diff - 30;
      if (1 & exMask)
        cost += diff + 20;
    }
    return cost;
  }

  int getMaxGridHappiness(int m, int n, int pos, int inMask, int exMask,
                          int inCount, int exCount) {
    // `inMask` is the placement of introvert people in the last n cells.
    // e.g. if we have m = 2, n = 3, i = 1, j = 1, then inMask = 0b101 means
    //
    // ? 1 0
    // 1 x ? (x := current position)
    const int i = pos / n;
    const int j = pos % n;
    if (i == m)
      return 0;
    if (dp[pos][inMask][exMask][inCount][exCount] > 0)
      return dp[pos][inMask][exMask][inCount][exCount];

    const int shiftedInMask = (inMask << 1) & ((1 << n) - 1);
    const int shiftedExMask = (exMask << 1) & ((1 << n) - 1);

    const int skip = getMaxGridHappiness(m, n, pos + 1, shiftedInMask,
                                         shiftedExMask, inCount, exCount);
    const int placeIntrovert =
        inCount > 0
            ? 120 + getPlacementCost(n, i, j, inMask, exMask, -30) +
                  getMaxGridHappiness(m, n, pos + 1, shiftedInMask | 1,
                                      shiftedExMask, inCount - 1, exCount)
            : INT_MIN;
    const int placeExtrovert =
        exCount > 0
            ? 40 + getPlacementCost(n, i, j, inMask, exMask, 20) +
                  getMaxGridHappiness(m, n, pos + 1, shiftedInMask,
                                      shiftedExMask | 1, inCount, exCount - 1)
            : INT_MIN;
    return dp[pos][inMask][exMask][inCount][exCount] =
               max({skip, placeIntrovert, placeExtrovert});
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
public class Solution {
  public int getMaxGridHappiness(int m, int n, int introvertsCount, int extrovertsCount) {
    final int twoToThePowerOfN = (int) Math.pow(2, n);
    dp = new int[m * n][twoToThePowerOfN][twoToThePowerOfN][introvertsCount + 1]
                [extrovertsCount + 1];
    return getMaxGridHappiness(m, n, 0, 0, 0, introvertsCount, extrovertsCount);
  }

  private int[][][][][] dp;

  // Calculates the cost based on left and up neighbors.
  //
  // The `diff` parameter represents the happiness change due to the current
  // placed person in (i, j). We add `diff` each time we encounter a neighbor
  // (left or up) who is already placed.
  //
  // Case 1: If the neighbor is an introvert, we subtract 30 from cost.
  // Case 2: If the neighbor is an extrovert, we add 20 to from cost.
  private int getPlacementCost(int n, int i, int j, int inMask, int exMask, int diff) {
    int cost = 0;
    if (i > 0) {
      if (((1 << (n - 1)) & inMask) > 0)
        cost += diff - 30;
      if (((1 << (n - 1)) & exMask) > 0)
        cost += diff + 20;
    }
    if (j > 0) {
      if ((1 & inMask) > 0)
        cost += diff - 30;
      if ((1 & exMask) > 0)
        cost += diff + 20;
    }
    return cost;
  }

  private int getMaxGridHappiness(int m, int n, int pos, int inMask, int exMask, int inCount,
                                  int exCount) {
    // `inMask` is the placement of introvert people in the last n cells.
    // e.g. if we have m = 2, n = 3, i = 1, j = 1, then inMask = 0b101 means
    //
    // ? 1 0
    // 1 x ? (x := current position)
    final int i = pos / n;
    final int j = pos % n;
    if (i == m)
      return 0;
    if (dp[pos][inMask][exMask][inCount][exCount] > 0)
      return dp[pos][inMask][exMask][inCount][exCount];

    final int shiftedInMask = (inMask << 1) & ((1 << n) - 1);
    final int shiftedExMask = (exMask << 1) & ((1 << n) - 1);

    final int skip =
        getMaxGridHappiness(m, n, pos + 1, shiftedInMask, shiftedExMask, inCount, exCount);
    final int placeIntrovert = inCount > 0
                                   ? 120 + getPlacementCost(n, i, j, inMask, exMask, -30) +
                                         getMaxGridHappiness(m, n, pos + 1, shiftedInMask | 1,
                                                             shiftedExMask, inCount - 1, exCount)
                                   : Integer.MIN_VALUE;
    final int placeExtrovert =
        exCount > 0 ? 40 + getPlacementCost(n, i, j, inMask, exMask, 20) +
                          getMaxGridHappiness(m, n, pos + 1, shiftedInMask, shiftedExMask | 1,
                                              inCount, exCount - 1)
                    : Integer.MIN_VALUE;
    return dp[pos][inMask][exMask][inCount][exCount] =
               Math.max(skip, Math.max(placeIntrovert, placeExtrovert));
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
class Solution:
  def getMaxGridHappiness(self, m: int, n: int, introvertsCount: int, extrovertsCount: int) -> int:
    def getPlacementCost(i: int, j: int, inMask: int, exMask: int, diff: int) -> int:
      """Calculates the cost based on left and up neighbors.

      The `diff` parameter represents the happiness change due to the current
      placed person in (i, j). We add `diff` each time we encounter a neighbor
      (left or up) who is already placed.

      Case 1: If the neighbor is an introvert, we subtract 30 from cost.
      Case 2: If the neighbor is an extrovert, we add 20 to from cost.
      """
      cost = 0
      if i > 0:
        if (1 << (n - 1)) & inMask:
          cost += diff - 30
        if (1 << (n - 1)) & exMask:
          cost += diff + 20
      if j > 0:
        if 1 & inMask:
          cost += diff - 30
        if 1 & exMask:
          cost += diff + 20
      return cost

    @functools.lru_cache(None)
    def dp(pos: int, inMask: int, exMask: int, inCount: int, exCount: int) -> int:
      # `inMask` is the placement of introvert people in the last n cells.
      # e.g. if we have m = 2, n = 3, i = 1, j = 1, then inMask = 0b101 means
      #
      # ? 1 0
      # 1 x ? (x := current position)
      i, j = divmod(pos, n)
      if i == m:
        return 0

      shiftedInMask = (inMask << 1) & ((1 << n) - 1)
      shiftedExMask = (exMask << 1) & ((1 << n) - 1)

      skip = dp(pos + 1, shiftedInMask, shiftedExMask, inCount, exCount)
      placeIntrovert = 120 + getPlacementCost(i, j, inMask, exMask, -30) + \
          dp(pos + 1, shiftedInMask + 1, shiftedExMask, inCount - 1, exCount) if inCount > 0 \
          else -math.inf
      placeExtrovert = 40 + getPlacementCost(i, j, inMask, exMask, 20) + \
          dp(pos + 1, shiftedInMask, shiftedExMask + 1, inCount, exCount - 1) if exCount > 0 \
          else -math.inf
      return max(skip, placeIntrovert, placeExtrovert)

    return dp(0, 0, 0, introvertsCount, extrovertsCount)