Huahua’s Tech Road

花花酱 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 1466. Reorder Routes to Make All Paths Lead to the City Zero

By zxi on May 31, 2020

There are n cities numbered from 0 to n-1 and n-1 roads such that there is only one way to travel between two different cities (this network form a tree). Last year, The ministry of transport decided to orient the roads in one direction because they are too narrow.

Roads are represented by connections where connections[i] = [a, b] represents a road from city a to b.

This year, there will be a big event in the capital (city 0), and many people want to travel to this city.

Your task consists of reorienting some roads such that each city can visit the city 0. Return the minimum number of edges changed.

It’s guaranteed that each city can reach the city 0 after reorder.

Example 1:

Input: n = 6, connections = [[0,1],[1,3],[2,3],[4,0],[4,5]]
Output: 3
Explanation: Change the direction of edges show in red such that each node can reach the node 0 (capital).

Example 2:

Input: n = 5, connections = [[1,0],[1,2],[3,2],[3,4]]
Output: 2
Explanation: Change the direction of edges show in red such that each node can reach the node 0 (capital).

Example 3:

Input: n = 3, connections = [[1,0],[2,0]]
Output: 0

Constraints:

2 <= n <= 5 * 10^4
connections.length == n-1
connections[i].length == 2
0 <= connections[i][0], connections[i][1] <= n-1
connections[i][0] != connections[i][1]

Solution: BFS

Augment the graph
g[u][v] = 1, g[v][u] = 0, u->v is an edge in the original graph.

BFS from 0, sum up all the edge costs to visit all the nodes.

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

C++

// Author: Huahua

class Solution {

public:

int minReorder(int n, vector<vector<int>>& connections) {

vector<vector<pair<int, int>>> g(n); // u -> {v, cost}

for (const auto& e : connections) {

g[e[0]].emplace_back(e[1], 1); // u -> v, needs flip

g[e[1]].emplace_back(e[0], 0); // v -> u, no cost

}

int ans = 0;

queue<int> q{{0}};

vector<int> seen(n);

while (!q.empty()) {

int cur = q.front(); q.pop();

seen[cur] = 1;

for (const auto& [nxt, cost] : g[cur]) {

if (seen[nxt]) continue;

ans += cost;

q.push(nxt);

}

return ans;

}

};

花花酱 LeetCode 1465. Maximum Area of a Piece of Cake After Horizontal and Vertical Cuts

By zxi on May 31, 2020

Given a rectangular cake with height h and width w, and two arrays of integers horizontalCuts and verticalCuts where horizontalCuts[i] is the distance from the top of the rectangular cake to the ith horizontal cut and similarly, verticalCuts[j] is the distance from the left of the rectangular cake to the jth vertical cut.

Return the maximum area of a piece of cake after you cut at each horizontal and vertical position provided in the arrays horizontalCuts and verticalCuts. Since the answer can be a huge number, return this modulo 10^9 + 7.

Example 1:

Input: h = 5, w = 4, horizontalCuts = [1,2,4], verticalCuts = [1,3]
Output: 4 
Explanation: The figure above represents the given rectangular cake. Red lines are the horizontal and vertical cuts. After you cut the cake, the green piece of cake has the maximum area.

Example 2:

Input: h = 5, w = 4, horizontalCuts = [3,1], verticalCuts = [1]
Output: 6
Explanation: The figure above represents the given rectangular cake. Red lines are the horizontal and vertical cuts. After you cut the cake, the green and yellow pieces of cake have the maximum area.

Example 3:

Input: h = 5, w = 4, horizontalCuts = [3], verticalCuts = [3]
Output: 9

Constraints:

2 <= h, w <= 10^9
1 <= horizontalCuts.length < min(h, 10^5)
1 <= verticalCuts.length < min(w, 10^5)
1 <= horizontalCuts[i] < h
1 <= verticalCuts[i] < w
It is guaranteed that all elements in horizontalCuts are distinct.
It is guaranteed that all elements in verticalCuts are distinct.

Solution: Geometry

Find the max gap between vertical cuts mx and max gap between horizontal cuts my. ans = mx * my

Time complexity: O(nlogn)
Space complexity: O(1) if sort in place otherweise O(n)

C++

// Author: Huahua

class Solution {

public:

int maxArea(int h, int w, vector<int>& horizontalCuts, vector<int>& verticalCuts) {

constexpr int kMod = 1e9 + 7;

sort(begin(verticalCuts), end(verticalCuts));

sort(begin(horizontalCuts), end(horizontalCuts));

int mx = max(verticalCuts[0], w - verticalCuts.back());

int my = max(horizontalCuts[0], h - horizontalCuts.back());

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

mx = max(mx, verticalCuts[i] - verticalCuts[i - 1]);

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

my = max(my, horizontalCuts[i] - horizontalCuts[i - 1]);

return static_cast<long>(mx) * my % kMod;

}

};

花花酱 LeetCode 1464. Maximum Product of Two Elements in an Array

By zxi on May 31, 2020

Given the array of integers nums, you will choose two different indices i and j of that array. Return the maximum value of(nums[i]-1)*(nums[j]-1).

Example 1:

Input: nums = [3,4,5,2]
Output: 12 
Explanation: If you choose the indices i=1 and j=2 (indexed from 0), you will get the maximum value, that is, (nums[1]-1)*(nums[2]-1) = (4-1)*(5-1) = 3*4 = 12.

Example 2:

Input: nums = [1,5,4,5]
Output: 16
Explanation: Choosing the indices i=1 and j=3 (indexed from 0), you will get the maximum value of (5-1)*(5-1) = 16.

Example 3:

Input: nums = [3,7]
Output: 12

Constraints:

2 <= nums.length <= 500
1 <= nums[i] <= 10^3

Solution 1: Sort

We want to find the largest and second largest elements.

Time complexity: O(nlogn)
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

int maxProduct(vector<int>& nums) {

sort(rbegin(nums), rend(nums));

return (nums[0] - 1) * (nums[1] - 1);

}

};

Solution 2: Without sorting

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

C++

// Author: Huahua

class Solution {

public:

int maxProduct(vector<int>& nums) {

int m1 = 0;

int m2 = 0;

for (int n : nums) {

if (n > m1) {

m2 = m1;

m1 = n;

} else if (n > m2) {

m2 = n;

}

return (m1 - 1) * (m2 - 1);

}

};

花花酱 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];

}

};

Huahua's Tech Road

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

Solution 0: Permutation (TLE)

C++

Solution 1: Combination

C++

C++

花花酱 LeetCode 1466. Reorder Routes to Make All Paths Lead to the City Zero

Solution: BFS

C++

花花酱 LeetCode 1465. Maximum Area of a Piece of Cake After Horizontal and Vertical Cuts

Solution: Geometry

C++

花花酱 LeetCode 1464. Maximum Product of Two Elements in an Array

Solution 1: Sort

C++

Solution 2: Without sorting

C++

花花酱 LeetCode 1463. Cherry Pickup II

Solution: DP

C++

C++

C++