SweetFruits
SRM 551 · 2012-06-05 · by rng_58
SRM 551 · 2012-06-05 · by rng_58 · Brute Force, Dynamic Programming, Math
Problem Statement
Problem Statement
Beaver Bindu has found N pairwise different fruits.
Some of the fruits are sweet, others are bitter.
You are given a int[] sweetness.
The sweetness of the i-th fruit (0-based index) is sweetness[i].
Different fruits can have the same sweetness.
A fruit is bitter if its sweetness is -1.
Bindu has N-1 pieces of string. She can use each of the strings to connect two of the N fruits. She wants to use all N-1 strings to connect all N pieces of fruit into a single connected component. I.e., once she is done connecting the fruit, she will have an N-vertex tree, each fruit being one of the N vertices.
Having such a tree, we can evaluate its total sweetness as follows: A fruit on a tree is called truly sweet if it is sweet, and it is connected by a string to some other sweet fruit. The total sweetness of a tree is the sum of the sweetness of its truly sweet fruits.
You are also given aint maxSweetness.
Let X be the number of possible trees which have total sweetness at most maxSweetness, inclusive.
Compute and return the value (X modulo 1,000,000,007).
Bindu has N-1 pieces of string. She can use each of the strings to connect two of the N fruits. She wants to use all N-1 strings to connect all N pieces of fruit into a single connected component. I.e., once she is done connecting the fruit, she will have an N-vertex tree, each fruit being one of the N vertices.
Having such a tree, we can evaluate its total sweetness as follows: A fruit on a tree is called truly sweet if it is sweet, and it is connected by a string to some other sweet fruit. The total sweetness of a tree is the sum of the sweetness of its truly sweet fruits.
You are also given a
Notes
- A tree is an undirected acyclic graph.
Constraints
- sweetness will contain between 1 and 40 elements, inclusive.
- Each element of sweetness will be between -1 and 25,000,000, inclusive.
- maxSweetness will be between 0 and 1,000,000,000 (10^9), inclusive.
Examples
0)
{1, 2, -1, 3}
3
Returns: 3
The following picture shows all 3 trees whose sweetness is at most 3 (truly sweet fruits are painted red).
1)
{1, 2, -1, 3}
5
Returns: 7
When maxSweetness = 5, the following 4 additional trees are possible.
2)
{-1, -1, 2, 5, 5}
6
Returns: 20
3)
{2, 6, 8, 4, 1, 10, -1, -1, -1, -1}
15
Returns: 17024000
4)
{1078451, -1, 21580110, 8284711, -1, 4202301, 3427559, 8261270, -1, 16176713,
22915672, 24495540, 19236, 5477666, 12280316, 3305896, 17917887, 564911, 22190488, 21843923,
23389728, 14641920, 9590140, 12909561, 20405638, 100184, 23336457, 12780498, 18859535, 23180993,
10278898, 5753075, 21250919, 17563422, 10934412, 22557980, 24895749, 7593671, 10834579, 5606562}
245243285
Returns: 47225123
Submissions are judged against all 68 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class SweetFruits with a public method int countTrees(vector<int> sweetness, int maxSweetness) · 68 test cases · 2 s / 256 MB per case