Posts tagged as “hard”

花花酱 LeetCode 1478. Allocate Mailboxes

By zxi on June 14, 2020

Given the array houses and an integer k. where houses[i] is the location of the ith house along a street, your task is to allocate k mailboxes in the street.

Return the minimum total distance between each house and its nearest mailbox.

The answer is guaranteed to fit in a 32-bit signed integer.

Example 1:

Input: houses = [1,4,8,10,20], k = 3
Output: 5
Explanation: Allocate mailboxes in position 3, 9 and 20.
Minimum total distance from each houses to nearest mailboxes is |3-1| + |4-3| + |9-8| + |10-9| + |20-20| = 5

Example 2:

Input: houses = [2,3,5,12,18], k = 2
Output: 9
Explanation: Allocate mailboxes in position 3 and 14.
Minimum total distance from each houses to nearest mailboxes is |2-3| + |3-3| + |5-3| + |12-14| + |18-14| = 9.

Example 3:

Input: houses = [7,4,6,1], k = 1
Output: 8

Example 4:

Input: houses = [3,6,14,10], k = 4
Output: 0

Constraints:

n == houses.length
1 <= n <= 100
1 <= houses[i] <= 10^4
1 <= k <= n
Array houses contain unique integers.

Solution: DP

First, we need to sort the houses by their location.

This is a partitioning problem, e.g. optimal solution to partition first N houses into K groups. (allocating K mailboxes for the first N houses).

The key of this problem is to solve a base case, optimally allocating one mailbox for houses[i~j], The intuition is to put the mailbox in the middle location, this only works if there are only tow houses, or all the houses are evenly distributed. The correct location is the “median position” of a set of houses. For example, if the sorted locations are [1,2,3,100], the average will be 26 which costs 146 while the median is 2, and the cost becomes 100.

dp[i][k] := min cost to allocate k mailboxes houses[0~i].

base cases:

dp[i][1] = cost(0, i), min cost to allocate one mailbox.
dp[i][k] = 0 if k > i, more mailboxes than houses. // this is actually a pruning.

transition:

dp[i][k] = min(dp[p][k-1] + cost(p + 1, i)) 0 <= p < i,

allocate k-1 mailboxes for houses[0~p], and allocate one for houses[p+1~i]

ans:

dp[n-1][k]

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

C++

// Author: Huahua

class Solution {

public:

int minDistance(vector<int>& houses, int k) {

constexpr int kInf = 1e9;

const int n = houses.size();

sort(begin(houses), end(houses));

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

vector<vector<int>> costs(n + 1, vector<int>(n + 1, kInf));

// min cost to allocate one mailbox for houses[i~j].

auto cost = [&](int i, int j) {

int& ans = costs[i][j];

if (ans != kInf) return ans;

const int m = i + (j - i) / 2;

int box = 0;

if ((j - i + 1) & 1) // odd number of houses.

box = houses[m];

else // even number of houses.

box = (houses[m] + houses[m + 1]) / 2;

ans = 0;

for (int h = i; h <= j; ++h)

ans += abs(houses[h] - box);

return ans;

};

// min cost to allocate k mailboxes for houses[0~i].

function<int(int, int)> solve = [&](int i, int k) {

if (k > i) return 0; // more mailboxs than houses.

if (k == 1) return cost(0, i);

int& ans = dp[i][k];

if (ans != kInf) return ans;

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

ans = min(ans, solve(p, k - 1) + cost(p + 1, i));

return ans;

};

return solve(n - 1, k);

}

};

O(1) time to compute cost. O(n) Time and space for pre-processing.

C++

// Author: Huahua

vector<int> sums(n + 1);

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

sums[i] = sums[i - 1] + houses[i - 1];

// min cost to allocate one mailbox for houses[i~j].

auto cost = [&](int i, int j) {

const int m1 = (i + j) / 2;

const int m2 = (i + j + 1) / 2;

const int center = (houses[m1] + houses[m2]) / 2;

return (m1 - i + 1) * center - (sums[m1 + 1] - sums[i])

+ (sums[j + 1] - sums[m2]) - (j - m2 + 1) * center;

};

花花酱 LeetCode 1473. Paint House III

By zxi on June 7, 2020

There is a row of m houses in a small city, each house must be painted with one of the n colors (labeled from 1 to n), some houses that has been painted last summer should not be painted again.

A neighborhood is a maximal group of continuous houses that are painted with the same color. (For example: houses = [1,2,2,3,3,2,1,1] contains 5 neighborhoods [{1}, {2,2}, {3,3}, {2}, {1,1}]).

Given an array houses, an m * n matrix cost and an integer target where:

houses[i]: is the color of the house i, 0 if the house is not painted yet.
cost[i][j]: is the cost of paint the house i with the color j+1.

Return the minimum cost of painting all the remaining houses in such a way that there are exactly target neighborhoods, if not possible return -1.

Example 1:

Input: houses = [0,0,0,0,0], cost = [[1,10],[10,1],[10,1],[1,10],[5,1]], m = 5, n = 2, target = 3
Output: 9
Explanation: Paint houses of this way [1,2,2,1,1]
This array contains target = 3 neighborhoods, [{1}, {2,2}, {1,1}].
Cost of paint all houses (1 + 1 + 1 + 1 + 5) = 9.

Example 2:

Input: houses = [0,2,1,2,0], cost = [[1,10],[10,1],[10,1],[1,10],[5,1]], m = 5, n = 2, target = 3
Output: 11
Explanation: Some houses are already painted, Paint the houses of this way [2,2,1,2,2]
This array contains target = 3 neighborhoods, [{2,2}, {1}, {2,2}]. 
Cost of paint the first and last house (10 + 1) = 11.

Example 3:

Input: houses = [0,0,0,0,0], cost = [[1,10],[10,1],[1,10],[10,1],[1,10]], m = 5, n = 2, target = 5
Output: 5

Example 4:

Input: houses = [3,1,2,3], cost = [[1,1,1],[1,1,1],[1,1,1],[1,1,1]], m = 4, n = 3, target = 3
Output: -1
Explanation: Houses are already painted with a total of 4 neighborhoods [{3},{1},{2},{3}] different of target = 3.

Constraints:

m == houses.length == cost.length
n == cost[i].length
1 <= m <= 100
1 <= n <= 20
1 <= target <= m
0 <= houses[i] <= n
1 <= cost[i][j] <= 10^4

Solution: DP

dp[k][i][c] := min cost to form k neighbors with first i houses and i-th house is in color c.

dp[k][i][c] := min{dp[k-(c != cj)][j][cj] for cj in 1..n} + 0 if houses[i] == c else cost[i][c]

init: dp[0][0][*] = 0 otherwise inf
ans = min(dp[target][m])

Time complexity: O(T*M*N^2)
Space complexity: O(T*M*N) -> O(M*N)

C++

// Author: Huahua

// Author: Huahua， 104ms, 17.9MB

class Solution {

public:

int minCost(vector<int>& houses, vector<vector<int>>& cost, int m, int n, int target) {

constexpr int kInf = 1e9 + 7, s = 1;

// dp[k][i][c] := min cost to form k neighbors with first i houses and end with color c.

vector<vector<vector<int>>> dp(target + 1, vector<vector<int>>(m + 1, vector<int>(n + 1, kInf)));

fill(begin(dp[0][0]), end(dp[0][0]), 0);

for (int k = 1; k <= target; ++k)

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

const int hi = houses[i - 1];

const int hj = i >= 2 ? houses[i - 2] : 0;

const auto& [si, ei] = hi ? tie(hi, hi) : tie(s, n);

const auto& [sj, ej] = hj ? tie(hj, hj) : tie(s, n);

for (int ci = si; ci <= ei; ++ci) {

const int v = ci == hi ? 0 : cost[i - 1][ci - 1];

for (int cj = sj; cj <= ej; ++cj)

dp[k][i][ci] = min(dp[k][i][ci], dp[k - (ci != cj)][i - 1][cj] + v);

}

const int ans = *min_element(begin(dp[target][m]), end(dp[target][m]));

return ans >= kInf ? -1 : ans;

}

};

花花酱 LeetCode 1467. Probability of a Two Boxes Having The Same Number of Distinct Balls

By zxi on June 3, 2020

Given 2n balls of k distinct colors. You will be given an integer array balls of size k where balls[i] is the number of balls of color i.

All the balls will be shuffled uniformly at random, then we will distribute the first n balls to the first box and the remaining n balls to the other box (Please read the explanation of the second example carefully).

Please note that the two boxes are considered different. For example, if we have two balls of colors a and b, and two boxes [] and (), then the distribution [a] (b) is considered different than the distribution [b] (a) (Please read the explanation of the first example carefully).

We want to calculate the probability that the two boxes have the same number of distinct balls.

Example 1:

Input: balls = [1,1]
Output: 1.00000
Explanation: Only 2 ways to divide the balls equally:
- A ball of color 1 to box 1 and a ball of color 2 to box 2
- A ball of color 2 to box 1 and a ball of color 1 to box 2
In both ways, the number of distinct colors in each box is equal. The probability is 2/2 = 1

Example 2:

Input: balls = [2,1,1]
Output: 0.66667
Explanation: We have the set of balls [1, 1, 2, 3]
This set of balls will be shuffled randomly and we may have one of the 12 distinct shuffles with equale probability (i.e. 1/12):
[1,1 / 2,3], [1,1 / 3,2], [1,2 / 1,3], [1,2 / 3,1], [1,3 / 1,2], [1,3 / 2,1], [2,1 / 1,3], [2,1 / 3,1], [2,3 / 1,1], [3,1 / 1,2], [3,1 / 2,1], [3,2 / 1,1]
After that we add the first two balls to the first box and the second two balls to the second box.
We can see that 8 of these 12 possible random distributions have the same number of distinct colors of balls in each box.
Probability is 8/12 = 0.66667

Example 3:

Input: balls = [1,2,1,2]
Output: 0.60000
Explanation: The set of balls is [1, 2, 2, 3, 4, 4]. It is hard to display all the 180 possible random shuffles of this set but it is easy to check that 108 of them will have the same number of distinct colors in each box.
Probability = 108 / 180 = 0.6

Example 4:

Input: balls = [3,2,1]
Output: 0.30000
Explanation: The set of balls is [1, 1, 1, 2, 2, 3]. It is hard to display all the 60 possible random shuffles of this set but it is easy to check that 18 of them will have the same number of distinct colors in each box.
Probability = 18 / 60 = 0.3

Example 5:

Input: balls = [6,6,6,6,6,6]
Output: 0.90327

Constraints:

1 <= balls.length <= 8
1 <= balls[i] <= 6
sum(balls) is even.
Answers within 10^-5 of the actual value will be accepted as correct.

Solution 0: Permutation (TLE)

Enumerate all permutations of the balls, count valid ones and divide that by the total.

Time complexity: O((8*6)!) = O(48!)
After deduplication: O(48!/(6!)^8) ~ 1.7e38
Space complexity: O(8*6)

C++

// Author: Huahua, TLE 4/21 passed

class Solution {

public:

double getProbability(vector<int>& balls) {

const int k = balls.size();

vector<int> bs;

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

for (int j = 0; j < balls[i]; ++j)

bs.push_back(i);

const int n = bs.size();

double total = 0.0;

double valid = 0.0;

// d : depth

// used : bitmap of bs's usage

// c1: bitmap of colors of box1

// c2: bitmap of colors of box1

function<void(int, long, int, int)> dfs = [&](int d, long used, int c1, int c2) {

if (d == n) {

total += 1;

valid += __builtin_popcount(c1) == __builtin_popcount(c2);

return;

}

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

if (used & (1L << i)) continue;

// Deduplication.

if (i > 0 && bs[i] == bs[i - 1] && !(used & (1L << (i - 1)))) continue;

int tc1 = (d < n / 2) ? (c1 | (1 << bs[i])) : c1;

int tc2 = (d < n / 2) ? c2 : (c2 | (1 << bs[i]));

dfs(d + 1, used | (1L << i), tc1, tc2);

}

};

dfs(0, 0, 0, 0);

return valid / total;

}

};

Solution 1: Combination

For each color, put n_i balls into box1, the left t_i – n_i balls go to box2.
permutations = fact(n//2) / PROD(fact(n_i)) * fact(n//2) * PROD(fact(t_i – n_i))
E.g
balls = [1×2, 2×6, 3×4]
One possible combination:
box1: 1 22 333
box2: 1 2222 3
permutations = 6! / (1! * 2! * 3!) * 6! / (1! * 4! * 1!) = 1800

Time complexity: O((t+1)^k) = O(7^8)
Space complexity: O(k + (t*k)) = O(8 + 48)

C++

// Author: Huahua

class Solution {

public:

double getProbability(vector<int>& balls) {

const int n = accumulate(begin(balls), end(balls), 0);

const int k = balls.size();

double total = 0.0;

double valid = 0.0;

vector<double> fact(50, 1.0);

for (int i = 1; i < fact.size(); ++i)

fact[i] = fact[i - 1] * i;

// d: depth

// b1, b2: # of balls in box1, box2

// c1, c2: # of distinct colors in box1, box2

// p1, p2: # permutations of duplicate balls in box1, box2

function<void(int, int, int, int, int, double, double)> dfs = [&]

(int d, int b1, int b2, int c1, int c2, double p1, double p2) {

if (b1 > n / 2 || b2 > n / 2) return;

if (d == k) {

const double count = fact[b1] / p1 * fact[b2] / p2;

total += count;

valid += count * (c1 == c2);

return;

}

for (int s1 = 0; s1 <= balls[d]; ++s1) {

const int s2 = balls[d] - s1;

dfs(d + 1,

b1 + s1,

b2 + s2,

c1 + (s1 > 0),

c2 + (s2 > 0),

p1 * fact[s1],

p2 * fact[s2]);

}

};

dfs(0, 0, 0, 0, 0, 1.0, 1.0);

return valid / total;

}

};

vector version

C++

// Author: Huahua

class Solution {

public:

double getProbability(vector<int>& balls) {

const int k = balls.size();

const int n = accumulate(begin(balls), end(balls), 0);

vector<double> fact(49, 1.0);

for (int i = 1; i < fact.size(); ++i)

fact[i] = fact[i - 1] * i;

auto perms = [&](const vector<int>& bs, int n) -> double {

double p = fact[n];

for (int b : bs) p /= fact[b];

return p;

};

vector<int> box1, box2;

function<double(int)> dfs = [&](int d) -> double {

const int n1 = accumulate(begin(box1), end(box1), 0);

const int n2 = accumulate(begin(box2), end(box2), 0);

if (n1 > n / 2 || n2 > n / 2) return 0;

if (d == k)

return (box1.size() == box2.size()) * perms(box1, n1) * perms(box2, n2);

double total = 0;

for (int s1 = 0; s1 <= balls[d]; ++s1) {

const int s2 = balls[d] - s1;

if (s1) box1.push_back(s1);

if (s2) box2.push_back(s2);

total += dfs(d + 1);

if (s1) box1.pop_back();

if (s2) box2.pop_back();

}

return total;

};

return dfs(0) / perms(balls, n);

}

};

花花酱 LeetCode 1463. Cherry Pickup II

By zxi on May 30, 2020

Given a rows x cols matrix grid representing a field of cherries. Each cell in grid represents the number of cherries that you can collect.

You have two robots that can collect cherries for you, Robot #1 is located at the top-left corner (0,0) , and Robot #2 is located at the top-right corner (0, cols-1) of the grid.

Return the maximum number of cherries collection using both robots by following the rules below:

From a cell (i,j), robots can move to cell (i+1, j-1) , (i+1, j) or (i+1, j+1).
When any robot is passing through a cell, It picks it up all cherries, and the cell becomes an empty cell (0).
When both robots stay on the same cell, only one of them takes the cherries.
Both robots cannot move outside of the grid at any moment.
Both robots should reach the bottom row in the grid.

Example 1:

Input: grid = [[3,1,1],[2,5,1],[1,5,5],[2,1,1]]
Output: 24
Explanation: Path of robot #1 and #2 are described in color green and blue respectively.
Cherries taken by Robot #1, (3 + 2 + 5 + 2) = 12.
Cherries taken by Robot #2, (1 + 5 + 5 + 1) = 12.
Total of cherries: 12 + 12 = 24.

Example 2:

Input: grid = [[1,0,0,0,0,0,1],[2,0,0,0,0,3,0],[2,0,9,0,0,0,0],[0,3,0,5,4,0,0],[1,0,2,3,0,0,6]]
Output: 28
Explanation: Path of robot #1 and #2 are described in color green and blue respectively.
Cherries taken by Robot #1, (1 + 9 + 5 + 2) = 17.
Cherries taken by Robot #2, (1 + 3 + 4 + 3) = 11.
Total of cherries: 17 + 11 = 28.

Example 3:

Input: grid = [[1,0,0,3],[0,0,0,3],[0,0,3,3],[9,0,3,3]]
Output: 22

Example 4:

Input: grid = [[1,1],[1,1]]
Output: 4

Constraints:

rows == grid.length
cols == grid[i].length
2 <= rows, cols <= 70
0 <= grid[i][j] <= 100

Solution: DP

dp[y][x1][x2] := max cherry when ro1 at (x1, y) and ro2 at (x2, y)
dp[y][x1][x2] = max(dp[y+1][x1 + dx1][x2 + dx2]) -1 <= dx1, dx2 <= 1

Time complexity: O(c^2*r)
Space complexity: O(c^2*r)

C++

// Author: Huahua

class Solution {

public:

int cherryPickup(vector<vector<int>>& grid) {

const int r = grid.size();

const int c = grid[0].size();

vector<vector<vector<int>>> cache(r, vector<vector<int>>(c, vector<int>(c, -1)));

function<int(int, int, int)> dp = [&](int y, int x1, int x2) {

if (x1 < 0 || x1 >= c || x2 < 0 || x2 >= c || y < 0 || y >= r) return 0;

int& ans = cache[y][x1][x2];

if (ans != -1) return ans;

const int cur = grid[y][x1] + (x1 != x2) * grid[y][x2];

for (int d1 = -1; d1 <= 1; ++d1)

for (int d2 = -1; d2 <= 1; ++d2)

ans = max(ans, cur + dp(y + 1, x1 + d1, x2 + d2));

return ans;

};

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

}

};

Bottom-up

C++

// Author: Huahua

class Solution {

public:

int cherryPickup(vector<vector<int>>& grid) {

const int r = grid.size();

const int c = grid[0].size();

vector<vector<vector<int>>> dp(r + 2,

vector<vector<int>>(c + 2, vector<int>(c + 2)));

for (int y = r; y >= 1; --y)

for (int x1 = 1; x1 <= c; ++x1)

for (int x2 = 1; x2 <= c; ++x2) {

const int cur = grid[y - 1][x1 - 1] + (x1 != x2) * grid[y - 1][x2 - 1];

int& ans = dp[y][x1][x2];

for (int d1 = -1; d1 <= 1; ++d1)

for (int d2 = -1; d2 <= 1; ++d2)

ans = max(ans, cur + dp[y + 1][x1 + d1][x2 + d2]);

}

return dp[1][1][c];

}

};

O(c^2) Space

C++

// Author: Huahua

class Solution {

public:

int cherryPickup(vector<vector<int>>& grid) {

const int r = grid.size();

const int c = grid[0].size();

vector<vector<int>> dp(c + 2, vector<int>(c + 2));

for (int y = r; y >= 1; --y) {

vector<vector<int>> tmp(c + 2, vector<int>(c + 2));

for (int x1 = 1; x1 <= c; ++x1)

for (int x2 = 1; x2 <= c; ++x2) {

const int cur = grid[y - 1][x1 - 1] + (x1 != x2) * grid[y - 1][x2 - 1];

for (int d1 = -1; d1 <= 1; ++d1)

for (int d2 = -1; d2 <= 1; ++d2)

tmp[x1][x2] = max(tmp[x1][x2], cur + dp[x1 + d1][x2 + d2]);

}

dp.swap(tmp);

}

return dp[1][c];

}

};

花花酱 LeetCode 1453. Maximum Number of Darts Inside of a Circular Dartboard

By zxi on May 16, 2020

You have a very large square wall and a circular dartboard placed on the wall. You have been challenged to throw darts into the board blindfolded. Darts thrown at the wall are represented as an array of points on a 2D plane.

Return the maximum number of points that are within or lie on any circular dartboard of radius r.

Example 1:

Input: points = [[-2,0],[2,0],[0,2],[0,-2]], r = 2
Output: 4
Explanation: Circle dartboard with center in (0,0) and radius = 2 contain all points.

Example 2:

Input: points = [[-3,0],[3,0],[2,6],[5,4],[0,9],[7,8]], r = 5
Output: 5
Explanation: Circle dartboard with center in (0,4) and radius = 5 contain all points except the point (7,8).

Example 3:

Input: points = [[-2,0],[2,0],[0,2],[0,-2]], r = 1
Output: 1

Example 4:

Input: points = [[1,2],[3,5],[1,-1],[2,3],[4,1],[1,3]], r = 2
Output: 4

Constraints:

1 <= points.length <= 100
points[i].length == 2
-10^4 <= points[i][0], points[i][1] <= 10^4
1 <= r <= 5000

Solution 1: Angular Sweep

See for more details: https://www.geeksforgeeks.org/angular-sweep-maximum-points-can-enclosed-circle-given-radius/

Time complexity: O(n^2*logn)
Space complexity: O(n^2)

C++

// Author: Huahua

// Python-Like enumerate() In C++17

// http://reedbeta.com/blog/python-like-enumerate-in-cpp17/

template <typename T,

typename TIter = decltype(std::begin(std::declval<T>())),

typename = decltype(std::end(std::declval<T>()))>

constexpr auto enumerate(T && iterable) {

struct iterator {

size_t i;

TIter iter;

bool operator != (const iterator & other) const { return iter != other.iter; }

void operator ++ () { ++i; ++iter; }

auto operator * () const { return std::tie(i, *iter); }

};

struct iterable_wrapper {

T iterable;

auto begin() { return iterator{ 0, std::begin(iterable) }; }

auto end() { return iterator{ 0, std::end(iterable) }; }

};

return iterable_wrapper{ std::forward<T>(iterable) };

}

class Solution {

public:

int numPoints(vector<vector<int>>& points, int r) {

const int n = points.size();

vector<vector<double>> d(n, vector<double>(n));

for (const auto& [i, pi] : enumerate(points))

for (const auto& [j, pj] : enumerate(points))

d[i][j] = d[j][i] = sqrt((pi[0] - pj[0]) * (pi[0] - pj[0])

+ (pi[1] - pj[1]) * (pi[1] - pj[1]));

int ans = 1;

for (const auto& [i, pi] : enumerate(points)) {

vector<pair<double, int>> angles; // {angle, event_type}

for (const auto& [j, pj] : enumerate(points)) {

if (i != j && d[i][j] <= 2 * r) {

const double a = atan2(pj[1] - pi[1], pj[0] - pi[0]);

const double b = acos(d[i][j] / (2 * r));

angles.emplace_back(a - b, -1); // entering

angles.emplace_back(a + b, 1); // exiting

}

// If angles are the same, entering points go first.

sort(begin(angles), end(angles));

int pts = 1;

for (const auto& [_, event] : angles)

ans = max(ans, pts -= event);

}

return ans;

}

};