Statistics

Problem Statement for "ChristmasBinaryTree"

Problem Statement

Agus has a binary Christmas tree. More precisely, the decorative balls on his tree are arranged into a complete binary tree with depth levels. At the top of the Christmas tree there is a single ball: the root of the binary tree of balls. This is the only ball on level 1. For each x between 1 and depth-1, inclusive, each ball on level x has exactly two children on level x+1: one ball that is its left child and one ball that is its right child. Hence, there are exactly 2^x balls on level x. The balls on level depth are the leaves of the tree.
There are N colors, numbered 0 through N-1. Each ball has one of those N colors. The colors of the balls follow a simple pattern: If the color of a ball is c, then the color of its left child is left[c] and the color of its right child is right[c].
You are given the long depth. You are also given the int[]s left and right, each with N elements.
You do not know the colors of any of the balls on Agus's tree. Obviously, the colors of all balls are determined by the color of the ball that is the root of the tree. For each possible color r of the root of the tree, do the following:
  1. For each i, determine c(i) = the number of leaves of color i.
  2. Compute the value v(r) = (c(0)^2 + c(1)^2 + ... + c(N-1)^2) modulo 10^9+7.
Return the largest of all possible values v(r).
Note that the maximum of all v(r) is taken only after the modulo operator is used to compute each of them. In other words, we are not necessarily maximizing the sum of c(i)^2, we are maximizing the remainder that sum can give modulo 10^9+7.

Definition

Class:
ChristmasBinaryTree
Method:
count
Parameters:
long, int[], int[]
Returns:
int
Method signature:
int count(long depth, int[] left, int[] right)
(be sure your method is public)

Constraints

  • depth will be between 1 and 10^18 inclusive.
  • left will contain between 1 and 100 elements inclusive.
  • Each element of left will be between 0 and N-1 inclusive where N is the number of elements of left.
  • right and left will contain the same number of elements.
  • Each element of right will be between 0 and N-1 inclusive where N is the number of elements of right.

Examples

  1. 1

    {0}

    {0}

    Returns: 1

    This tree only has a single level. The root of the node is therefore also its only leaf. There is only one color: color 0. We have c(0) = 1 and v(0) = (1^2 modulo 10^9+7) = 1.

  2. 3

    {0,1,2}

    {0,1,2}

    Returns: 16

    There are four leaves. All four leaves always have the same color as each other, because all balls in this tree have the same color as its root. This means that one of the c(i) is always equal to 4 while the other two are zeros. Then, c(0)^2 + c(1)^2 + c(2)^2 is always 16.

  3. 4

    {1,2,0}

    {2,0,1}

    Returns: 22

    This time the arrays left and right are such that there are three distinct colors, and whenever a ball A has children B and C, each of the balls A, B, and C has a different color. In this setting we can prove that c(0), c(1), and c(2) will always be 3, 3, and 2, in some order. It follows that for any color r of the root we have v(r) = 3^2 + 3^2 + 2^2 = 22.

  4. 4

    {0,2,2}

    {1,1,2}

    Returns: 64

  5. 1000000000000

    {0,1,2,3}

    {1,1,2,2}

    Returns: 465080044

  6. 393

    {9,1,10,9,10,2,3,12,4,11,7,6,14,3,9,6}

    {3,15,12,13,11,11,6,2,8,8,13,10,3,15,10,2}

    Returns: 980994602

  7. 79

    {3,4,3,2,2,3,10,2,9,0,0,10,10,4,2,10,2}

    {10,14,9,6,6,13,9,11,4,6,16,5,10,3,1,5,14}

    Returns: 891625285

  8. 134

    {7,14,9,18,12,1,13,3,4,7,1,14,1,19,20,9,17,22,17,2,1,11,15,19,15}

    {20,17,14,0,8,3,9,1,24,10,18,12,11,14,20,3,1,2,17,6,5,16,14,19,4}

    Returns: 975633534

  9. 41

    {6,3,9,12,14,6,4,5,10,2,21,0,25,22,15,14,11,22,20,8,1,1,17,6,14,15,8}

    {11,11,13,25,21,5,2,11,3,26,11,9,11,3,11,10,6,20,7,23,14,22,22,16,8,9,4}

    Returns: 991682607

  10. 869

    {12,13,25,10,16,23,9,10,19,24,0,1,7,8,16,14,13,19,12,6,22,22,2,15,8,21}

    {11,14,9,15,15,17,23,8,25,23,2,7,10,2,2,4,3,14,5,3,3,5,6,23,16,10}

    Returns: 984048995

  11. 552

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

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

    Returns: 741986749

  12. 718

    {16,18,14,6,22,13,16,13,11,3,22,1,17,1,13,0,4,6,20,14,2,17,1,19,10,23}

    {12,1,0,20,13,24,23,25,6,6,15,19,22,11,18,3,20,20,12,16,3,20,4,14,24,7}

    Returns: 939553083

  13. 346

    {2,6,13,1,19,1,19,0,5,7,4,0,2,16,10,12,12,5,2,0}

    {7,1,12,15,19,4,11,7,8,10,18,4,9,1,4,12,10,5,19,2}

    Returns: 952012436

  14. 908

    {13,13,19,20,10,15,2,7,18,21,13,1,13,10,10,1,21,15,21,10,19,16,19}

    {9,20,12,21,13,14,22,11,9,10,17,2,16,2,12,0,8,12,12,2,20,22,18}

    Returns: 895342914

  15. 46

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

    {2,1,8,6,12,15,12,17,10,13,11,4,9,4,2,9,12,3}

    Returns: 920207727

  16. 470

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

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

    Returns: 960160738

  17. 59

    {7,5,5,2,3,9,12,7,11,10,5,10,7,8}

    {3,13,4,5,13,6,7,12,2,0,3,12,4,13}

    Returns: 978084428

  18. 33

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

    {1,7,10,7,4,8,1,4,3,10,10}

    Returns: 601905541

  19. 926

    {14,20,7,15,13,21,14,6,20,8,8,21,21,16,9,18,12,8,6,11,15,7}

    {9,6,14,16,17,11,16,11,20,19,7,6,1,5,4,2,16,19,0,19,9,8}

    Returns: 962921350

  20. 955

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

    {3,0,12,3,5,1,2,11,5,0,2,10,6}

    Returns: 870242534

  21. 427

    {22,11,20,17,16,26,10,20,0,24,6,10,12,6,9,14,24,8,7,26,0,1,23,21,1,14,5,2,11}

    {22,14,18,19,11,6,8,19,17,6,25,3,23,18,10,23,26,15,18,24,15,2,13,16,16,28,24,17,1}

    Returns: 991107550

  22. 246

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

    {5,9,1,4,5,4,8,8,2,2}

    Returns: 779617245

  23. 727

    {13,6,6,3,14,19,2,8,10,14,6,17,13,13,5,10,17,3,10,10}

    {14,13,13,14,13,17,15,19,12,17,15,11,3,8,11,18,16,15,18,4}

    Returns: 983486215

  24. 581

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

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

    Returns: 992402837

  25. 875

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

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

    Returns: 898772882

  26. 999999999999999997

    {15,15,2,3,6,11,13,11,0,12,3,16,2,0,12,9,3}

    {3,5,10,7,8,11,8,9,2,2,1,13,2,3,0,2,16}

    Returns: 932526620

  27. 999999999999999999

    {13,5,25,7,0,9,20,6,5,20,20,15,8,20,5,16,9,21,16,14,23,21,22,19,18,4}

    {24,3,17,1,18,4,24,0,14,1,19,13,12,22,9,18,23,10,3,17,23,17,2,3,13,14}

    Returns: 982119341

  28. 1000000000000000000

    {31,57,81,3,33,81,15,25,22,51,32,81,15,8,99,97,76,77,87,82,66,60,11,86,30,83,76,20,25,39,90,60,43,28,21,55,25,70,53,22,50,97,26,71,49,28,98,10,77,76,52,87,99,66,17,35,98,95,5,28,28,93,97,72,45,25,83,27,21,34,34,59,57,61,72,16,50,82,17,73,6,64,63,72,37,28,80,56,41,52,11,17,83,12,6,67,89,54,75,41}

    {13,94,81,20,82,87,96,4,92,97,34,6,57,95,62,83,54,9,32,21,63,82,85,85,90,14,16,92,28,25,36,18,37,82,10,88,15,37,8,83,57,27,69,51,10,39,88,93,90,99,31,77,57,52,41,68,84,76,66,54,8,78,55,74,0,97,12,82,93,39,21,85,54,62,41,52,62,99,54,15,51,90,91,37,59,71,87,90,70,65,69,61,51,0,38,64,32,4,79,12}

    Returns: 994876565

  29. 999999999999999992

    {69,70,44,49,65,26,83,69,52,93,89,31,64,48,77,33,49,55,68,60,23,71,77,45,61,23,0,75,42,59,89,69,51,83,33,4,81,66,67,92,2,31,74,18,83,87,73,62,33,96,41,26,80,85,5,29,98,62,19,41,10,26,89,8,38,93,10,5,13,38,21,29,80,95,24,54,69,69,73,33,87,94,99,39,42,86,49,86,11,33,22,73,19,54,24,59,18,12,5,33}

    {36,56,60,14,14,86,39,35,21,90,9,73,35,95,13,98,55,93,56,33,86,58,40,81,90,50,54,64,24,19,44,38,76,19,43,56,75,11,12,29,68,2,7,16,77,72,57,25,97,18,53,74,93,48,30,59,60,24,80,2,80,83,40,23,57,31,20,90,91,70,67,71,43,99,88,86,32,10,30,63,79,49,51,64,30,15,15,81,34,87,87,43,42,44,39,63,53,69,4,99}

    Returns: 994662163

  30. 1000000000000000000

    {0, 1, 2, 3 }

    {1, 1, 2, 2 }

    Returns: 550540002

  31. 1000000000000

    {0, 1, 2, 3 }

    {1, 1, 2, 2 }

    Returns: 465080044

  32. 22

    {0, 2, 2 }

    {1, 1, 2 }

    Returns: 954206563

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: