Ferry load windows
HardOnline Assessment
Count the crate loadings that keep a river ferry inside its safe draft window.
A ferry may carry any set of crates from crates, including none at all. Most crates are ballast and push the ferry down, but some are floats that lift it, so each crate has an integer net load (positive for ballast, negative for a float, possibly zero). A loading is safe when the sum of the net loads of the crates it carries is between lo and hi, both inclusive.
Crates are individual objects even when they have the same net load: loading the first of two identical crates is a different loading from loading the second. Two loadings are different if they use different sets of crates. The empty loading counts (its sum is 0) whenever 0 is inside the window.
Input: crates, the list of net loads, and the window limits lo and hi.
Output: the number of safe loadings.
With up to 36 crates there can be about 7 * 10^10 loadings, so checking them one at a time will never finish. Because floats exist, you cannot stop extending a loading just because it is already too heavy.
Example 1
- Input:
- [[3,-2,5],1,4]
- Output:
- 3
- Explanation
- The net loads of the eight possible crate sets are 0, 3, -2, 5, 1, 8, 3 and 6 (empty, then each crate alone, then the pairs, then all three). Those inside [1, 4] are {3}, {3, -2} and {-2, 5}, so the answer is 3. The negative crate means a larger set can weigh less than a smaller one.
Example 2
- Input:
- [[2,2,2],2,4]
- Output:
- 6
- Explanation
- The three crates have equal weights but are different crates. Each single crate (net 2) and each pair (net 4) is in the window [2, 4], giving 3 + 3 = 6 choices. The empty set (0) and all three (6) are outside.
Example 3
- Input:
- [[4,-4],0,0]
- Output:
- 2
- Explanation
- The empty set carries a net load of 0, which is inside [0, 0], and so does the set of both crates (4 + -4 = 0). The single-crate sets are outside, so the answer is 2.
Constraints
0 <= crates.length <= 36-1,000,000,000 <= crates[i] <= 1,000,000,000-40,000,000,000 <= lo <= hi <= 40,000,000,000