LeetCode - Last Stone Weight II

https://leetcode.com/problems/last-stone-weight-ii/

Problem

You are given an array of integers stones where stones[i] is the weight of the ith stone.

We are playing a game with the stones. On each turn, we choose any two stones and smash them together. Suppose the stones have weights x and y with x <= y. The result of this smash is:

  • If x == y, both stones are destroyed, and
  • If x != y, the stone of weight x is destroyed, and the stone of weight y has new weight y - x.
    At the end of the game, there is at most one stone left.

Return the smallest possible weight of the left stone. If there are no stones left, return 0.

Solution

You can convert this problem into knapsack problem: splitting the given array into 2 parts which the sum diff of two parts is minimum. The sum diff is the result of this problem.

Why? I was struggled while proving this. Well, i will put a really good mathematic proof (which i stealed from leetcode). It took me around 30m to understand this… I’m old :<

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Given stones {x_1, ..., x_k}
a(x_1, ..., x_k) be the minimum among all expressions of the form (y_1+...+y_m) - (z_1+...+z_n) that are >= 0 such that {x_1,...x_k} is the disjoint union of {y_1,...,y_m} and {z_1,...z_n} (i.e. a solution of the corresponding knapsack problem), and let
b(x_1, ..., x_k) be the minimum final stone starting from {x_1,...,x_k}.
Since any final stone can be written in the form (y_1+...+y_m) - (z_1+...+z_n), we have b >= a (Ineq 0).
We show a(x_1,...,x_k) = b(x_1,...,x_k) by induction:
if k = 0 or k = 1, it is trivial that a = b;
if k >= 2, write a(x_1,...,x_k) = (y_1+...+y_m) - (z_1+...+z_n) (Eq 1), then clearly m >= 1 and n >= 1.

If y_1 > z_1, consider ((y_1-z_1)+(y_2+...+y_m)) - (z_2+...+z_n); we know that it is >= 0, so it is >= the minimum a(y_1-z_1, y_2,...,y_m, z_2,...,z_n) (Ineq 1).
By induction hypothesis (we've reduced the number of stones by one), a(y_1-z_1, y_2,...,y_m, z_2,...,z_n) = b(y_1-z_1, y_2,...,y_m, z_2,...,z_n) (Eq 2).
Note that b(x_1, ..., x_k) is the minimum among all first-step choices of two stones to cancel. Since {y_1,z_1} is one possible choice, we have b(y_1-z_1, y_2,...,y_m, z_2,...,z_n) >= b(x_1, ..., x_k) (Ineq 2).
Combining (Eq 1), (Ineq 1), (Eq 2) and (Ineq 2), we get a(x_1,...,x_k) >= b(x_1,...,x_k), hence a(x_1,...,x_k) = b(x_1,...,x_k) by (Ineq 0).
If y_1 < z_1, consider (y_2+...+y_m) - ((z_1-y_1)+z_2+...+z_n) and the same reasoning applies.
If y_1 = z_1, consider (y_2+...+y_m) - (z_2+...+z_n) and the same reasoning applies.
In the last case we reduce the number of stones by two. We've shown that a=b for any k stones given that a=b for any (k-1) stones and any (k-2) stones. By induction we know a=b for any number of stones.

TL;DR: No, read it please, it’s a really cool induction math :))

So, how we solve the knapsack problem? We need to know, which sum we can build by using some stones in given stones.

Let define f[i] = true if we can build sum i. For each stone, we will need to update the f array. It’s clearly that we can build sum i+stone if we can build sum i.

In the below code, i made a twist of the second loop (len(f)-1 -> 0) to avoid using duplicated stone.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
func lastStoneWeightII(stones []int) int {
f := make([]bool, 30*100/2 + 1)
f[0] = true
sum := 0
for _, stone := range stones {
for i := len(f) - 1; i >= stone; i-- {
if f[i-stone] {
f[i] = true
}
}
sum += stone
}

smallerSum := 0
for i := sum/2; i > 0; i -= 1 {
if f[i] {
smallerSum = i
break
}
}
diff := sum - 2 * smallerSum
return diff
}

There is an optimization i made in the code: The f array has 1500 elements which is equal MAX_STONES * MAX_WEIGHT / 2. Why /2? Well, the smallerSum is less than or equal sum/2.

The time complexity is O(N*MAX_WEIGHT) and memory complexity is O(MAX_WEIGHT)


Support me via: https://ko-fi.com/iamquang95