Flagpole
SRM 807 · 2021-06-07 · by misof
Problem Statement
Time limit is 4 seconds.
The leader of the neighboring country has just unveiled a giant flagpole with their national flag. Our national pride is hurt. We need a bigger flagpole. (True story.)
Their flagpole measures LO nanometers. The maximum safe height of a flagpole is HI nanometers.
A flagpole is built by placing one or more segments on top of each other. The final height of the flagpole is the sum of heights of segments used.
Our government must purchase all flagpole segments from its only official flagpole segment provider.
The lengths of the segments the provider has in their warehouse are given in the
Count all ways in which we can purchase a subset of the available segments if we want a safe flagpole that is bigger than what our neighbors have.
Notes
- Note that we want you to return the exact number of ways in which a subset of segments can be selected, and not the number modulo something (as is sometimes the case in similar problems).
Constraints
- segments will have between 1 and 40 elements, inclusive.
- Each element of segments will be between 1 and 2*10^9, inclusive.
- LO will be between 1 and 10^11, inclusive.
- HI will be between LO+1 and 10^11, inclusive.
{10, 10, 10, 10, 10}
9
49
Returns: 30
Out of the 2^5 = 32 possible purchases only two are invalid: If we don't purchase any segments, our flagpole will have height 0 and our neighbors will laugh at us. If we purchase all five segments, the flagpole will exceed the maximum safe height.
{10, 10, 10, 10, 10}
30
39
Returns: 0
There is no solution: either we make a flagpole that is at most as long as our neighbor's, or we make one that is too tall to be safe.
{1, 2, 4, 8, 16, 32, 64, 128}
47
100
Returns: 53
For each of the heights 48-100 there is exactly one way to purchase some segments that sum to the chosen flagpole height.
{50, 10, 40, 30, 20}
45
63
Returns: 6
We can build a flagpole of height 50 as 50, 10+40, or 20+30. We can build a flagpole of height 60 as 10+50, 20+40, or 10+20+30.
{134271794, 923817928, 1188933014, 974250759, 1225763433, 134271794, 923817928, 1188933014, 974250759, 1225763433, 737595659, 552822148, 1100465897, 830124985, 842705656, 1321907875, 87850801, 1707427140, 898791927, 1414390308, 50809161, 220022264, 1345418, 566520438, 1701332471, 1034126713, 1554472261, 1174003062, 19618886, 1970109602, 1751726525, 1930025925, 677697582, 1218843450, 918477526, 494022073, 510546715, 1123712904, 1103705096, 771122962}
8408530690
17322737448
Returns: 389442612825
Submissions are judged against all 107 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class Flagpole with a public method long long build(vector<int> segments, long long LO, long long HI) · 107 test cases · 2 s / 256 MB per case