aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2024-10-13 10:54:11 -0600
committerJack Sangdahl <[email protected]>2024-10-13 10:54:11 -0600
commit0f3e9ac36b523a36c78981c031f2967e9d878136 (patch)
treecfab17765c949c87a2a5233207e0efc91bb09867
parent9230f76c2ee902e932ea5a0c6b17dbc2740a21ce (diff)
downloadleetcode-0f3e9ac36b523a36c78981c031f2967e9d878136.tar.gz
leetcode-0f3e9ac36b523a36c78981c031f2967e9d878136.zip
1659. maximise grid happiness
-rw-r--r--maximise_grid_happiness.cpp66
-rw-r--r--maximise_grid_happiness.py52
2 files changed, 118 insertions, 0 deletions
diff --git a/maximise_grid_happiness.cpp b/maximise_grid_happiness.cpp
new file mode 100644
index 0000000..612c111
--- /dev/null
+++ b/maximise_grid_happiness.cpp
@@ -0,0 +1,66 @@
+// 1659. Maximize Grid Happiness
+#include "leetcode.h"
+
+/*
+ * you are given four integers 'm', 'n', 'introvertsCount', and
+ * 'extrovertsCount'. you have an 'm * n' grid and there are two types of
+ * people: introverts and extroverts. there are 'introvertsCount' introverts and
+ * 'extrovertsCount' extroverts. you should decide how many people ou want to
+ * live in the grid and assign each of them one grid cell. note that you do not
+ * have to have all the people living in the grid. neighbours live directly
+ * adjacent cells, north, east, south, and west of a person's cell. the grid
+ * happiness is the sum of each person's happiness. return the maximum possible
+ * grid happiness
+ */
+
+class Solution {
+private:
+ int dp[25][7][7][64][64] = {};
+ int n_cost(int m, int n, int i, int j, int introvert_mask, int extrovert_mask,
+ int d) {
+ int diff = 0, up = (1 << (n - 1));
+ if (j && (introvert_mask & 1))
+ diff += d - 30;
+ if (i && (introvert_mask & up))
+ diff += d - 30;
+ if (j && (extrovert_mask & 1))
+ diff += d + 20;
+ if (i && (extrovert_mask & up))
+ diff += d + 20;
+ return diff;
+ }
+ int dfs(int m, int n, int p, int in, int out, int introvert_mask,
+ int extrovert_mask) {
+ int i = p / n, j = p % n;
+ if (i >= m)
+ return 0;
+ if (dp[p][in][out][introvert_mask][extrovert_mask])
+ return dp[p][in][out][introvert_mask][extrovert_mask] - 1;
+ int n_introvert_mask = (introvert_mask << 1) & 63,
+ n_extrovert_mask = (extrovert_mask << 1) & 63;
+ int res = dfs(m, n, p + 1, in, out, n_introvert_mask, n_extrovert_mask);
+ if (in) {
+ int diff = n_cost(m, n, i, j, introvert_mask, extrovert_mask, -30) + 120;
+ res = max(res, diff + dfs(m, n, p + 1, in - 1, out, n_introvert_mask + 1,
+ n_extrovert_mask));
+ }
+ if (out) {
+ int diff = n_cost(m, n, i, j, introvert_mask, extrovert_mask, 20) + 40;
+ res = max(res, diff + dfs(m, n, p + 1, in, out - 1, n_introvert_mask,
+ n_extrovert_mask + 1));
+ }
+ return res;
+ }
+
+public:
+ int getMaxGridHappiness(int m, int n, int introvertsCount,
+ int extrovertsCount) {
+ return dfs(m, n, 0, introvertsCount, extrovertsCount, 0, 0);
+ }
+};
+
+int main() {
+ Solution obj;
+ printf("%d\n", obj.getMaxGridHappiness(2, 3, 1, 2)); // expect: 240
+ printf("%d\n", obj.getMaxGridHappiness(3, 1, 2, 1)); // expect: 260
+}
diff --git a/maximise_grid_happiness.py b/maximise_grid_happiness.py
new file mode 100644
index 0000000..d1cc114
--- /dev/null
+++ b/maximise_grid_happiness.py
@@ -0,0 +1,52 @@
+# 1659. Maximize Grid Happiness
+
+"""
+you are given four integers 'm', 'n', 'introvertsCount', and
+'extrovertsCount'. you have an 'm * n' grid and there are two types of
+people: introverts and extroverts. there are 'introvertsCount' introverts and
+'extrovertsCount' extroverts. you should decide how many people ou want to
+live in the grid and assign each of them one grid cell. note that you do not
+have to have all the people living in the grid. neighbours live directly
+adjacent cells, north, east, south, and west of a person's cell. the grid
+happiness is the sum of each person's happiness. return the maximum possible
+grid happiness
+"""
+
+
+class Solution(object):
+ def getMaxGridHappiness(self, m, n, introvertsCount, extrovertsCount):
+ """
+ :type m: int
+ :type n: int
+ :type introvertsCount: int
+ :type extrovertsCount: int
+ :rtype: int
+ """
+ ing, exg, inl, exl = 120, 40, -30, 20
+ valid = [[0, 0, 0], [0, 2 * inl, inl + exl], [0, inl + exl, 2 * exl]]
+
+ def dp(idx, row, i, e):
+ if idx == -1:
+ return 0
+ r, c, res = idx // n, idx % n, []
+ n = [(1, i - 1, e, ing), (2, i, e - 1, exg), (0, i, e, 0)]
+ for val, dx, dy, gain in n:
+ tmp = 0
+ if dx >= 0 and dy >= 0:
+ tmp = dp(idx - 1, (val,) + row[:-1], dx, dy) + gain
+ if c < n - 1:
+ tmp += valid[val][row[0]]
+ if r < m - 1:
+ tmp += valid[val][row[-1]]
+ res.append(tmp)
+ return max(res)
+
+ if m < n:
+ n = n, m
+ return dp(m * n - 1, tuple([0] * n), introvertsCount, extrovertsCount)
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.getMaxGridHappiness(m=2, n=3, introvertsCount=1, extrovertsCount=2))
+ print(obj.getMaxGridHappiness(m=3, n=1, introvertsCount=2, extrovertsCount=1))