DengklekGaneshAndTree
TCO17 Round 2B · 2017-03-31 · by fushar
TCO17 Round 2B · 2017-03-31 · by fushar · Dynamic Programming
Problem Statement
Problem Statement
Dengklek has a tree consisting of N nodes. The nodes are conveniently numbered 0 through N − 1. You are given an int[] parents that consists of N − 1 elements. The root of the tree is node 0, while for each 1 ≤ i < N, the parent of node i is node parents[i − 1].
Each node is initially labeled with a lowercase letter. You are give aString labels that contains N lowercase letters. The label of node i is labels[i].
Let's define the level of a node as the number of edges in the only path from it to the root. Let L be the maximum level of all nodes.
A tree is "notorious" if both the following conditions hold:
Ganesh wants to transform the tree into a notorious one. To achieve that, Ganesh will choose zero or more nodes. Then, for each chosen node, Ganesh will change the case of the label to uppercase.
Return the number of possible resulting notorious trees, modulo 1,000,000,007. Two trees are different if there is at least one node that is labeled with a lowercase letter in one tree but is labeled with an uppercase letter in the other tree.
Each node is initially labeled with a lowercase letter. You are give a
Let's define the level of a node as the number of edges in the only path from it to the root. Let L be the maximum level of all nodes.
A tree is "notorious" if both the following conditions hold:
- For each 0 ≤ i ≤ L, there must be at least one node labeled with an uppercase letter that has level i.
- For each pair of nodes connected by an edge, if they are labeled with the same letter (case insensitive), then the letters must be both lowercase or both uppercase.
Ganesh wants to transform the tree into a notorious one. To achieve that, Ganesh will choose zero or more nodes. Then, for each chosen node, Ganesh will change the case of the label to uppercase.
Return the number of possible resulting notorious trees, modulo 1,000,000,007. Two trees are different if there is at least one node that is labeled with a lowercase letter in one tree but is labeled with an uppercase letter in the other tree.
Constraints
- labels will contain between 1 and 1,000 characters, inclusive.
- Each character of labels will be a lowercase English letter ('a' to 'z').
- parents will contain exactly N − 1 elements, where N is the number of character of labels.
- For each i, parents[i] will be between 0 and i, inclusive.
Examples
0)
"seems"
{0, 1, 0, 3}
Returns: 5
Here are the five possible notorious trees. Nodes with uppercase letters are shown in bold for clarity.
1)
"like"
{0, 0, 0}
Returns: 7
For level 0, the letter 'l' must be uppercase. For level 1, each of the letters 'i', 'k', 'e' can be either lowercase or uppercase, but they cannot be all lowercase. Therefore, the number of possible notorious trees is 1 × 2 × 2 × 2 − 1 = 7.
2)
"a"
{}
Returns: 1
3)
"coincidence"
{0, 1, 2, 0, 2, 1, 4, 7, 7, 6}
Returns: 218
4)
"topcoderopenroundtwobgoodluckhavefun"
{0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0}
Returns: 147418098
Don't forget to return the answer modulo 1,000,000,007.
Submissions are judged against all 72 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class DengklekGaneshAndTree with a public method int getCount(string labels, vector<int> parents) · 72 test cases · 2 s / 256 MB per case