Posts tagged as “hard”

花花酱 LeetCode 1444. Number of Ways of Cutting a Pizza

By zxi on May 15, 2020

Given a rectangular pizza represented as a rows x cols matrix containing the following characters: 'A' (an apple) and '.' (empty cell) and given the integer k. You have to cut the pizza into k pieces using k-1 cuts.

For each cut you choose the direction: vertical or horizontal, then you choose a cut position at the cell boundary and cut the pizza into two pieces. If you cut the pizza vertically, give the left part of the pizza to a person. If you cut the pizza horizontally, give the upper part of the pizza to a person. Give the last piece of pizza to the last person.

Return the number of ways of cutting the pizza such that each piece contains at least one apple. Since the answer can be a huge number, return this modulo 10^9 + 7.

Example 1:

Input: pizza = ["A..","AAA","..."], k = 3
Output: 3 
Explanation: The figure above shows the three ways to cut the pizza. Note that pieces must contain at least one apple.

Example 2:

Input: pizza = ["A..","AA.","..."], k = 3
Output: 1

Example 3:

Input: pizza = ["A..","A..","..."], k = 1
Output: 1

Constraints:

1 <= rows, cols <= 50
rows == pizza.length
cols == pizza[i].length
1 <= k <= 10
pizza consists of characters 'A' and '.' only.

Solution: DP

dp(n, m, k) := # of ways to cut pizza[n:N][m:M] with k cuts.

dp(n, m, k) = sum(hasApples(n, m, N – 1, y) * dp(y + 1, n, k – 1) for y in range(n, M)) + sum(hasApples(n, m, x, M – 1) * dp(m, x + 1, k – 1) for x in range(n, M))

Time complexity: O(M*N*(M+N)*K) = O(N^3 * K)
Space complexity: O(M*N*K)

C++

// Author: Huahua

class Solution {

public:

int ways(vector<string>& pizza, int K) {

constexpr int kMod = 1e9 + 7;

const int M = pizza.size();

const int N = pizza[0].size();

vector<vector<int>> A(M + 1, vector<int>(N + 1));

for (int y = 0; y < M; ++y)

for (int x = 0; x < N; ++x)

A[y + 1][x + 1] = A[y + 1][x] + A[y][x + 1] + (pizza[y][x] == 'A') - A[y][x];

auto hasApples = [&](int x1, int y1, int x2, int y2) {

return (A[y2 + 1][x2 + 1] - A[y2 + 1][x1] - A[y1][x2 + 1] + A[y1][x1]) > 0;

};

vector<vector<vector<int>>> cache(M, vector<vector<int>>(N, vector<int>(K, -1)));

// dp(m, n, k) := # of ways to cut pizza[m:M][n:N] with k cuts.

function<int(int, int, int)> dp = [&](int m, int n, int k) -> int {

if (k == 0) return hasApples(n, m, N - 1, M - 1);

int& ans = cache[m][n][k];

if (ans != -1) return ans;

ans = 0;

for (int y = m; y < M - 1; ++y) // Cut horizontally.

ans = (ans + hasApples(n, m, N - 1, y) * dp(y + 1, n, k - 1)) % kMod;

for (int x = n; x < N - 1; ++x) // Cut vertically.

ans = (ans + hasApples(n, m, x, M - 1) * dp(m, x + 1, k - 1)) % kMod;

return ans;

};

return dp(0, 0, K - 1);

}

};

花花酱 LeetCode 1439. Find the Kth Smallest Sum of a Matrix With Sorted Rows

By zxi on May 5, 2020

You are given an m * n matrix, mat, and an integer k, which has its rows sorted in non-decreasing order.

You are allowed to choose exactly 1 element from each row to form an array. Return the Kth smallest array sum among all possible arrays.

Example 1:

Input: mat = [[1,3,11],[2,4,6]], k = 5
Output: 7
Explanation: Choosing one element from each row, the first k smallest sum are:
[1,2], [1,4], [3,2], [3,4], [1,6]. Where the 5th sum is 7.

Example 2:

Input: mat = [[1,3,11],[2,4,6]], k = 9
Output: 17

Example 3:

Input: mat = [[1,10,10],[1,4,5],[2,3,6]], k = 7
Output: 9
Explanation: Choosing one element from each row, the first k smallest sum are:
[1,1,2], [1,1,3], [1,4,2], [1,4,3], [1,1,6], [1,5,2], [1,5,3]. Where the 7th sum is 9.

Example 4:

Input: mat = [[1,1,10],[2,2,9]], k = 7
Output: 12

Constraints:

m == mat.length
n == mat.length[i]
1 <= m, n <= 40
1 <= k <= min(200, n ^ m)
1 <= mat[i][j] <= 5000
mat[i] is a non decreasing array.

Solution 1: Priority Queue

Generate the arrays in order.

Each node is {sum, idx_0, idx_1, …, idx_m},

Start with {sum_0, 0, 0, …, 0}.

For expansion, pick one row and increase its index

Time complexity: O(k * m ^ 2* log k)
Space complexity: O(k)

C++

// Author: Huahua

class Solution {

public:

int kthSmallest(vector<vector<int>>& mat, int k) {

const int m = mat.size();

const int n = mat[0].size();

priority_queue<vector<int>> q;

vector<int> node(m + 1); // {-sum, idx_0, idx_1, ..., idx_m}

for (int i = 0; i < m; ++i) node[0] -= mat[i][0];

q.push(node);

set<vector<int>> seen{{node}};

while (!q.empty()) {

const vector<int> cur = q.top(); q.pop();

if (--k == 0) return -cur[0];

for (int i = 1; i <= m; ++i) {

if (cur[i] == n - 1) continue;

vector<int> nxt(cur);

++nxt[i]; // increase i-th row's index.

// Update sum.

nxt[0] -= (mat[i - 1][nxt[i]] - mat[i - 1][nxt[i] - 1]);

if (!seen.insert(nxt).second) continue;

q.push(move(nxt));

}

return -1;

}

};

花花酱 LeetCode 1434. Number of Ways to Wear Different Hats to Each Other

By zxi on May 3, 2020

There are n people and 40 types of hats labeled from 1 to 40.

Given a list of list of integers hats, where hats[i] is a list of all hats preferred by the i-th person.

Return the number of ways that the n people wear different hats to each other.

Since the answer may be too large, return it modulo 10^9 + 7.

Example 1:

Input: hats = [[3,4],[4,5],[5]]
Output: 1
Explanation: There is only one way to choose hats given the conditions. 
First person choose hat 3, Second person choose hat 4 and last one hat 5.

Example 2:

Input: hats = [[3,5,1],[3,5]]
Output: 4
Explanation: There are 4 ways to choose hats
(3,5), (5,3), (1,3) and (1,5)

Example 3:

Input: hats = [[1,2,3,4],[1,2,3,4],[1,2,3,4],[1,2,3,4]]
Output: 24
Explanation: Each person can choose hats labeled from 1 to 4.
Number of Permutations of (1,2,3,4) = 24.

Example 4:

Input: hats = [[1,2,3],[2,3,5,6],[1,3,7,9],[1,8,9],[2,5,7]]
Output: 111

Constraints:

n == hats.length
1 <= n <= 10
1 <= hats[i].length <= 40
1 <= hats[i][j] <= 40
hats[i] contains a list of unique integers.

Solution: DP

dp[i][j] := # of ways using first i hats, j is the bit mask of people wearing hats.

e.g. dp[3][101] == # of ways using first 3 hats that people 1 and 3 are wearing hats.

init dp[0][0] = 1

dp[i][mask | (1 << p)] = dp[i-1][mask | (1 << p)] + dp[i-1][mask], where people p prefers hats i.

ans: dp[nHat][1…1]

Time complexity: O(2^n * h * n)
Space complexity: O(2^n * h) -> O(2^n)

C++

// Author: Huahua

class Solution {

public:

int numberWays(vector<vector<int>>& hats) {

constexpr int kHat = 40;

constexpr int kMod = 1e9 + 7;

const int n = hats.size();

vector<vector<int>> people(kHat + 1); // hat -> {people}

for (int i = 0; i < n; ++i)

for (int hat : hats[i])

people[hat].push_back(i);

// dp[i][j] := # of ways using first i hats where j is bit mask of people wearing hats.

vector<vector<int>> dp(kHat + 1, vector<int>(1 << n));

dp[0][0] = 1;

for (int i = 1; i <= kHat; ++i) {

dp[i] = dp[i - 1];

for (int mask = (1 << n) - 1; mask >= 0; --mask)

for (int p : people[i]) {

if (mask & (1 << p)) continue;

dp[i][mask | (1 << p)] += dp[i - 1][mask];

dp[i][mask | (1 << p)] %= kMod;

}

return dp.back().back();

}

};

O(2^n) memory

C++

// Author: Huahua

class Solution {

public:

int numberWays(vector<vector<int>>& hats) {

constexpr int kHat = 40;

constexpr int kMod = 1e9 + 7;

const int n = hats.size();

vector<vector<int>> people(kHat + 1); // hat -> {people}

for (int i = 0; i < n; ++i)

for (int hat : hats[i])

people[hat].push_back(i);

// dp([i])[j] := # of ways using first i hats where j is bit mask of people wearing hat.

vector<int> dp(1 << n);

dp[0] = 1;

for (int i = 1; i <= kHat; ++i)

for (int mask = (1 << n) - 1; mask >= 0; --mask)

for (int p : people[i]) {

if (mask & (1 << p)) continue;

dp[mask | (1 << p)] += dp[mask];

dp[mask | (1 << p)] %= kMod;

}

return dp.back();

}

};

花花酱 LeetCode 1425. Constrained Subset Sum

By zxi on April 26, 2020

Given an integer array nums and an integer k, return the maximum sum of a non-empty subset of that array such that for every two consecutive integers in the subset, nums[i] and nums[j], where i < j, the condition j - i <= k is satisfied.

A subset of an array is obtained by deleting some number of elements (can be zero) from the array, leaving the remaining elements in their original order.

Example 1:

Input: nums = [10,2,-10,5,20], k = 2
Output: 37
Explanation: The subset is [10, 2, 5, 20].

Example 2:

Input: nums = [-1,-2,-3], k = 1
Output: -1
Explanation: The subset must be non-empty, so we choose the largest number.

Example 3:

Input: nums = [10,-2,-10,-5,20], k = 2
Output: 23
Explanation: The subset is [10, -2, -5, 20].

Constraints:

1 <= k <= nums.length <= 10^5
-10^4 <= nums[i] <= 10^4

Solution: DP / Sliding window / monotonic queue

dp[i] := max sum of a subset that include nums[i]
dp[i] := max(dp[i-1], dp[i-2], …, dp[i-k-1], 0) + nums[i]

C++

// Author: Huahua

class Solution {

public:

int constrainedSubsetSum(vector<int>& nums, int k) {

const int n = nums.size();

vector<int> dp(n);

multiset<int> s{INT_MIN};

int ans = INT_MIN;

for (int i = 0; i < nums.size(); ++i) {

if (i > k) s.erase(s.equal_range(dp[i - k - 1]).first);

dp[i] = max(*rbegin(s), 0) + nums[i];

s.insert(dp[i]);

ans = max(ans, dp[i]);

}

return ans;

}

};

Use a monotonic queue to track the maximum of a sliding window dp[i-k-1] ~ dp[i-1].

Time complexity: O(n)
Space complexity: O(n)

C++

// Author: Huahua 184 ms

class Solution {

public:

int constrainedSubsetSum(vector<int>& nums, int k) {

const int n = nums.size();

vector<int> dp(n);

deque<int> q;

int ans = INT_MIN;

for (int i = 0; i < nums.size(); ++i) {

if (i > k && q.front() == i - k - 1)

q.pop_front();

dp[i] = (q.empty() ? 0 : max(dp[q.front()], 0))

+ nums[i];

while (!q.empty() && dp[i] >= dp[q.back()])

q.pop_back();

q.push_back(i);

ans = max(ans, dp[i]);

}

return ans;

}

};

花花酱 LeetCode 1420. Build Array Where You Can Find The Maximum Exactly K Comparisons

By zxi on April 20, 2020

Given three integers n, m and k. Consider the following algorithm to find the maximum element of an array of positive integers:

You should build the array arr which has the following properties:

arr has exactly n integers.
1 <= arr[i] <= m where (0 <= i < n).
After applying the mentioned algorithm to arr, the value search_cost is equal to k.

Return the number of ways to build the array arr under the mentioned conditions. As the answer may grow large, the answer must be computed modulo 10^9 + 7.

Example 1:

Input: n = 2, m = 3, k = 1
Output: 6
Explanation: The possible arrays are [1, 1], [2, 1], [2, 2], [3, 1], [3, 2] [3, 3]

Example 2:

Input: n = 5, m = 2, k = 3
Output: 0
Explanation: There are no possible arrays that satisify the mentioned conditions.

Example 3:

Input: n = 9, m = 1, k = 1
Output: 1
Explanation: The only possible array is [1, 1, 1, 1, 1, 1, 1, 1, 1]

Example 4:

Input: n = 50, m = 100, k = 25
Output: 34549172
Explanation: Don't forget to compute the answer modulo 1000000007

Example 5:

Input: n = 37, m = 17, k = 7
Output: 418930126

Constraints:

1 <= n <= 50
1 <= m <= 100
0 <= k <= n

Solution: DP

dp[n][m][k] := ways to build given n,m,k.

dp[n][m][k] = sum(dp[n-1][m][k] + dp[n-1][i-1][k-1] – dp[n-1][i-1][k]), 1 <= i <= m
dp[1][m][1] = m
dp[n][m][k] = 0 if k < 1 or k > m or k > n

Time complexity: O(n*m^2*k)
Space complexity: O(n*m*k)

C++

// Author: Huahua

int mem[51][101][51] = {0};

class Solution {

public:

int numOfArrays(int n, int m, int k) {

const int kMod = 1e9 + 7;

function<int(int, int, int)> dp = [&dp](int n, int m, int k) {

if (k < 1 || k > m || k > n) return 0;

if (n == 1 && k == 1) return m;

if (mem[n][m][k]) return mem[n][m][k];

long ans = 0;

for (int i = 1; i <= m; ++i) {

ans += dp(n - 1, m, k);

ans += dp(n - 1, i - 1, k - 1);

ans -= dp(n - 1, i - 1, k);

ans = (ans + kMod) % kMod;

}

return mem[n][m][k] = ans;

};

return dp(n, m, k);

}

};