Two Mysterious Alphabets from a Tree
InterviewTime limit1sMemory limit128 MB
Find the max-sum root-to-leaf path in a number triangle, breaking ties by larger sum of squares, then print both sums and their mod-26 letters.
- Level
Easy3 of 10
- Topics
- Dynamic programming
- Solved
- No attempts yet
Problem
A tree of height holds one integer in each node. Level () has nodes, and every node is joined to the two neighboring nodes on the level right below it. Those two nodes are its children. Nodes on level have no children, and a node inside a level can have two parents. The tree looks like this.
1
/ \
4 5
/ \ / \
7 8 9
Start at the root, step down to one of the children each time, and stop at the last level. Among the paths built this way, take the one whose node values add up to the largest total. In the picture that path is . Nodes that are not joined cannot be added together, so is not a path.
The chosen path gives two numbers. The first number is the sum of the squares of the values on the path, and the second number is the sum of the values on the path. In the picture the first number is and the second number is .
When several paths tie for the largest total, take the one with the largest sum of squares among them.
Each of the two numbers becomes one lower case letter from 'a' to 'z'. becomes 'a' and becomes 'z'. There are only 26 letters, so a number above uses the letter of its remainder modulo 26, which makes , , and all 'a'. In the picture becomes 'd' and becomes 'p'.
Write a program that finds the two mysterious alphabets of a given tree.
Input
The first line contains the height of the tree ().
The second line contains the values of the tree separated by spaces, from level 1 to level , and left to right inside each level. Every value is an integer with , and there are of them.
Output
On the first line, print the two numbers from the rules above, the first number then the second number, separated by one space.
On the second line, print the two decoded letters in the same order with no space between them.