Statistics

Problem Statement for "CandleTimerEasy"

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 three int[]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].


Compute and return the number of different times you can measure when following the above procedure.

Definition

Class:
CandleTimerEasy
Method:
differentTime
Parameters:
int[], int[], int[]
Returns:
int
Method signature:
int differentTime(int[] A, int[] B, int[] len)
(be sure your method is public)

Constraints

  • A will contain between 1 and 19 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

  1. {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.

  2. {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.

  3. {0,0,0}

    {1,2,3}

    {1,2,3}

    Returns: 4

    We can get 4 different outcomes: 2.5, 3, 4, 5.

  4. {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

  5. {0,0,0,0}

    {1,2,3,4}

    {123,456,789,1000}

    Returns: 8

  6. {0}

    {1}

    {1000}

    Returns: 2

  7. {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}

    {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19}

    {1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1}

    Returns: 2

  8. {1,2,3,4,5,6,7,8,9,10}

    {0,1,0,1,4,3,6,7,6,9}

    {8,4,3,1,11,12,7,9,8,19}

    Returns: 6

  9. {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17}

    {0,1,1,2,2,3,3,4,6,5,7,8,12,3,0,8,0}

    {2,4,1,3,1,3,5,3,3,2,5,1,5,2,4,5,5}

    Returns: 17

  10. {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16}

    {0,0,2,1,1,0,5,2,8,9,1,7,7,10,14,9}

    {3,3,1,3,3,1,1,3,3,2,3,1,1,2,2,3}

    Returns: 14

  11. {1,2,3,4,5,6,7,8}

    {0,0,2,2,2,3,6,7}

    {89,400,555,393,324,86,79,399}

    Returns: 7

  12. {1,2,3,4,5,6,7}

    {0,1,2,1,2,3,0}

    {1,1,1,1,1,1,1}

    Returns: 4

  13. {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19}

    {0,1,0,2,0,1,0,7,6,0,2,3,8,7,4,12,5,11,8}

    {5,4,2,5,5,5,6,4,2,2,4,2,4,3,1,5,1,4,5}

    Returns: 17

  14. {1,2}

    {0,1}

    {47,75}

    Returns: 2

  15. {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18}

    {0,1,1,1,4,3,0,6,2,9,5,7,4,8,5,5,11,14}

    {296,578,106,60,258,260,317,656,559,849,551,631,84,248,835,159,171,40}

    Returns: 20

  16. {1,2,3,4,5,6,7,8}

    {0,0,1,3,1,3,3,4}

    {6,2,4,5,2,2,1,7}

    Returns: 9

  17. {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17}

    {0,1,0,3,4,4,5,3,8,9,3,6,6,10,11,9,16}

    {39,3,47,36,29,1,6,48,34,46,49,21,2,36,9,24,40}

    Returns: 13

  18. {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17}

    {0,1,1,2,0,4,4,4,5,4,7,3,4,7,4,14,3}

    {1,7,6,4,2,3,1,3,8,7,1,2,4,5,7,8,4}

    Returns: 18

  19. {1,2,3,4}

    {0,0,2,3}

    {89,5,86,84}

    Returns: 2

  20. {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16}

    {0,1,0,0,3,2,5,3,1,1,1,8,3,11,8,2}

    {6,1,3,2,7,6,1,5,6,7,5,1,1,5,1,6}

    Returns: 15

  21. {1,2,3,4,5,6,7,8,9,10,11}

    {0,0,1,2,4,4,5,6,8,9,10}

    {62,35,23,61,28,41,31,9,9,67,28}

    Returns: 4

  22. {1,2}

    {0,0}

    {15,5}

    Returns: 2

  23. {1,2,3,4,5,6,7,8,9}

    {0,1,1,3,0,4,2,6,6}

    {66,42,67,36,73,5,5,54,34}

    Returns: 6

  24. {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15}

    {0,1,1,2,3,5,5,5,2,8,4,11,2,3,13}

    {5,4,1,3,4,3,5,2,3,2,4,2,5,4,2}

    Returns: 15

  25. {1,2,3,4,5,6,7}

    {0,1,2,2,4,4,5}

    {14,9,14,6,3,10,15}

    Returns: 7

  26. {1}

    {0}

    {11}

    Returns: 2

  27. {1,2,3,4,5,6,7,8,9,10,11,12,13}

    {0,1,1,3,2,4,6,6,1,6,2,11,7}

    {1,1,1,1,1,1,1,1,1,1,1,1,1}

    Returns: 7

  28. {1,2,3,4,5,6,7,8,9,10,11,12,13}

    {0,1,2,3,3,5,6,7,8,8,9,10,12}

    {6,6,6,7,2,4,5,1,3,7,7,4,5}

    Returns: 6

  29. {1,2,3,4,5,6,7,8,9,10,11,12,13}

    {0,1,1,2,4,4,5,7,8,9,10,10,12}

    {542,106,150,313,633,85,920,20,206,75,773,403,758}

    Returns: 9

  30. {1,2,3,4}

    {0,0,1,0}

    {8,6,4,7}

    Returns: 4

  31. {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15}

    {0,0,0,2,4,5,5,7,5,9,10,10,9,13,11}

    {3,7,5,5,5,3,5,4,7,2,9,2,6,3,3}

    Returns: 19

  32. {1,2,3,4,5,6}

    {0,0,2,3,4,5}

    {18,15,51,71,44,69}

    Returns: 2

  33. {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17}

    {0,0,1,3,4,5,6,6,7,8,9,11,11,12,14,15,15}

    {2,1,2,2,1,1,2,1,2,2,2,2,2,2,2,2,1}

    Returns: 8

  34. {1,2}

    {0,0}

    {54,45}

    Returns: 2

  35. {1,2,3,4,5,6,7,8,9,10,11}

    {0,1,1,1,0,5,0,4,0,8,8}

    {1,1,3,1,2,2,3,2,1,1,1}

    Returns: 8

  36. {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19}

    {0,0,0,1,0,4,2,4,3,3,10,1,5,3,13,6,13,14,12}

    {117,235,488,585,847,777,540,709,106,607,868,85,212,831,431,192,98,460,441}

    Returns: 29

  37. {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19}

    {0,0,2,3,0,4,6,6,3,4,0,1,1,9,3,0,3,17,13}

    {14,11,4,4,15,4,11,8,1,1,6,8,4,5,17,7,3,17,13}

    Returns: 27

  38. {1,2,3,4,5}

    {0,1,0,0,1}

    {46,35,46,23,49}

    Returns: 6

  39. {1,2,3,4,5,6,7,8,9,10,11,12}

    {0,1,1,2,1,5,6,2,5,7,9,10}

    {100,89,347,6,620,661,566,258,174,305,236,265}

    Returns: 9

  40. {1,2,3,4,5,6,7,8,9,10,11,12,13}

    {0,1,0,2,3,0,1,0,1,5,3,4,12}

    {242,597,310,115,498,682,762,249,520,285,318,794,155}

    Returns: 19

  41. {1,2,3}

    {0,0,2}

    {418,158,564}

    Returns: 2

  42. {1}

    {0}

    {169}

    Returns: 2

  43. {1,2,3,4,5,6,7,8,9,10,11}

    {0,0,0,0,2,5,5,5,4,8,2}

    {437,371,431,22,291,300,129,74,263,148,221}

    Returns: 14

  44. {1,2,3,4,5,6,7,8,9,10,11,12,13,14}

    {0,0,2,2,3,0,1,5,7,5,10,8,8,8}

    {578,879,84,554,23,181,373,776,764,164,350,802,494,570}

    Returns: 18

  45. {1,2,3,4,5,6,7,8,9,10,11,12,13}

    {0,0,2,3,3,1,5,0,6,9,4,6,6}

    {3,820,147,842,803,88,702,688,413,17,27,763,679}

    Returns: 14

  46. {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18}

    {0,0,2,1,2,1,2,1,5,8,2,4,9,12,3,5,16,7}

    {271,767,555,539,124,789,769,668,179,35,338,712,628,228,427,441,884,586}

    Returns: 23

  47. {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18}

    {0,1,1,3,0,3,1,3,5,7,6,6,7,13,14,11,14,15}

    {1,2,2,4,4,1,3,2,3,4,4,2,2,4,4,2,1,1}

    Returns: 19

  48. {1,2,3,4,5,6,7,8,9,10}

    {0,0,2,2,3,4,5,6,7,9}

    {1,83,51,16,29,66,29,34,86,47}

    Returns: 4

  49. {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17}

    {0,0,1,2,3,0,4,0,5,1,8,3,4,12,5,2,2}

    {16,25,21,10,34,5,24,10,26,29,30,26,32,35,18,34,11}

    Returns: 25

  50. {1,2,3,4,5,6,7,8,9}

    {0,0,1,2,1,4,6,7,8}

    {7,3,7,7,2,9,9,3,1}

    Returns: 4

  51. {1,2,3,4,5,6,7,8,9,10,11,12,13}

    {0,0,2,3,2,3,6,0,2,7,9,8,2}

    {17,14,4,14,14,31,6,27,19,24,31,28,24}

    Returns: 23

  52. {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16}

    {0,0,2,2,4,1,2,3,7,3,7,8,6,7,8,14}

    {385,272,469,593,275,539,509,596,641,93,402,393,415,71,670,34}

    Returns: 22

  53. {1}

    {0}

    {489}

    Returns: 2

  54. {1,2}

    {0,0}

    {150,411}

    Returns: 2

  55. {1}

    {0}

    {26}

    Returns: 2

  56. {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15}

    {0,0,2,3,4,4,6,7,7,9,9,11,11,12,13}

    {41,24,20,22,40,1,21,32,2,35,15,41,6,32,23}

    Returns: 15

  57. {1,2,3,4,5,6,7,8,9,10,11}

    {0,1,2,2,4,4,6,7,7,8,9}

    {45,33,30,15,9,26,39,6,28,11,6}

    Returns: 9

  58. {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

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2024, TopCoder, Inc. All rights reserved.
This problem was used for: