ChristmasBinaryTree

SRM 705 Sponsored By Blizzard · 2016-12-22 · by ltaravilse

SRM 705 Sponsored By Blizzard · 2016-12-22 · by ltaravilse · Math

Show categories

Class Name: ChristmasBinaryTree

Return Type: int

Method Name: count

Arg Types: (long long, vector<int>, vector<int>)

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:

For each i, determine c(i) = the number of leaves of color i.
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.

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

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.

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
{0,2,2}
{1,1,2}
Returns: 64

1000000000000
{0,1,2,3}
{1,1,2,2}
Returns: 465080044

Submissions are judged against all 32 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class ChristmasBinaryTree with a public method int count(long long depth, vector<int> left, vector<int> right) · 32 test cases · 2 s / 256 MB per case