CandleTimer
SRM 638 · 2014-08-25 · by cgy4ever
SRM 638 · 2014-08-25 · by cgy4ever · Graph Theory, Math
Problem Statement
Problem Statement
You have a lot of candles.
The candles burn at a uniform rate: if you ignite a candle of length L, it will burn completely in L units of time.
You can also ignite a candle at both ends, which makes it burn twice as fast.
You have arranged some candles into the shape of a tree. You want to use the tree to measure time. At the beginning, you will ingite some leaves of the tree (all at the same time). Then you will just wait and watch the flames spread across the entire tree. (Whenever a flame reaches an inner node of the tree, it spreads to all branches that meet at that node.) Note that you are not allowed to light new flames during the process. The time you will measure is the time between the moment when you lighted the fire(s) and the moment when the last part of the tree finished burning.
You are given a description of the tree as threeint[] s: a, b, and len, with N elements each.
The nodes of the tree are numbered 0 through N, inclusive.
For each valid i, there is a candle between the nodes a[i] and b[i] with length len[i].
Let X be the number of different times you can measure when following the above procedure. Compute and return the value (X modulo 1,000,000,007).
You have arranged some candles into the shape of a tree. You want to use the tree to measure time. At the beginning, you will ingite some leaves of the tree (all at the same time). Then you will just wait and watch the flames spread across the entire tree. (Whenever a flame reaches an inner node of the tree, it spreads to all branches that meet at that node.) Note that you are not allowed to light new flames during the process. The time you will measure is the time between the moment when you lighted the fire(s) and the moment when the last part of the tree finished burning.
You are given a description of the tree as three
Let X be the number of different times you can measure when following the above procedure. Compute and return the value (X modulo 1,000,000,007).
Constraints
- A will contain between 1 and 200 elements, inclusive.
- A, B and len will contain same number of elements.
- Each element in A will be between 0 and |A|, inclusive.
- Each element in B will be between 0 and |A|, inclusive.
- Each element in len will be between 1 and 1000, inclusive.
- A, B and len will describe a tree.
Examples
0)
{0,1}
{1,2}
{10,1}
Returns: 2
This tree looks the same as a single candle of length 11. If we light it on one end, we will measure the time 11. If we light it on both ends, we will measure the time 5.5.
1)
{0,0,0}
{1,2,3}
{1,1,1}
Returns: 2
This time we have 3 ends. If we ignite all of them the time is 1, otherwise the time is 2.
2)
{0,0,0}
{1,2,3}
{1,2,3}
Returns: 4
We can get 4 different outcomes: 2.5, 3, 4, 5.
3)
{0,1,1,2,3,3,2,4}
{1,2,3,4,5,6,7,8}
{5,3,2,4,6,8,7,1}
Returns: 7
4)
{0,0,0,0}
{1,2,3,4}
{123,456,789,1000}
Returns: 8
Submissions are judged against all 87 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class CandleTimer with a public method int differentTime(vector<int> A, vector<int> B, vector<int> len) · 87 test cases · 2 s / 256 MB per case