Google Code Jam Qualification Round Q4

# Google Code Jam Qualification Round Q4 - Chain Reactions

#### Declaration

This post is released after the end of the Qualification Round of Code Jam.

#### Question

Please refer to: [Code Jam Official Site](https://codingcompetitions.withgoogle.com/codejam/round/0000000000876ff1/0000000000a45ef7)

#### Solution

##### Terminology

1. **Node:** Means `Module` in the question.

2. **Sub-node:** Means the `Module` points toward a certain `Module`.  
For example, **(2) and (3) are sub-nodes of (1)** in the graph below (node ID in the bracket).
- - <img src='https://g.gravizo.com/svg?
 digraph G {
    "5 (3)" -> "1 (1)";
    "2 (2)" -> "1 (1)";
    "1 (1)" -> Abyss;
 }
'/>

3. **Single Branch:** Means the structure of a certain `Module` consists only one sub-node.  
For example, **(3) has a single branch structure** in the graph below.
- - <img src='https://g.gravizo.com/svg?
 digraph G {
    "2 (4)" -> "5 (3)";
    "5 (3)" -> "1 (1)";
    "2 (2)" -> "1 (1)";
    "1 (1)" -> Abyss;
 }
'/>

##### Idea

1. Simplify the structrue by removing single branch nodes

- - Lets consider the graph in the previous example:
 
 - - <img src='https://g.gravizo.com/svg?
 digraph G {
    "2 (4)" -> "5 (3)";
    "5 (3)" -> "1 (1)";
    "2 (2)" -> "1 (1)";
    "1 (1)" -> Abyss;
 }
'/>

- - Regardless the way of trigger, nodes, (3) and (4) in the example, involved in a single branch structure will always be in the same reaction chain.

- - Trigger (4) first,
 
 - - - <img src='https://g.gravizo.com/svg?
 digraph G {
    "2 (4)" -> "5 (3)";
    "5 (3)" -> "1 (1)";
    "2 (2)";
    "1 (1)" -> Abyss;
 }
'/> 
 - - Trigger (2) first,  
 
 - - - <img src='https://g.gravizo.com/svg?
 digraph G {
    "2 (4)" -> "5 (3)";
    "5 (3)" ;
    "2 (2)" -> "1 (1)";
    "1 (1)" -> Abyss;
 }
'/>

- - Therefore, we can collapse the single branch structure into a single node with the larger value involved in the structure with no impact on the result.

- - <img src='https://g.gravizo.com/svg?
 digraph G {
    "5 (3)" -> "1 (1)";
    "2 (2)" -> "1 (1)";
    "1 (1)" -> Abyss;
 }
'/>

- - Consider a more complex structure:
 
 - - <img src='https://g.gravizo.com/svg?
 digraph G {
    "10(10)"-> "7 (9)";
    "7 (9)" -> "2 (7)";
    "11(8)" -> "2 (7)";
    "2 (7)" -> "7 (1)";
    "4 (6)" -> "2 (3)";
    "3 (5)" -> "2 (3)";
    "5 (4)" -> "2 (3)";
    "2 (3)" -> "3 (2)";
    "3 (2)" -> "7 (1)";
    "7 (1)" -> Abyss;
 }
'/>

- - Node (3) -> (2) and (10) -> (9) are in single branch structures, and hence they can be reduced.
 
 - - <img src='https://g.gravizo.com/svg?
 digraph G {
    "10 (9)" -> "2 (7)";
    "11 (8)" -> "2 (7)";
    "2 (7)" -> "7 (1)";
    "4 (6)" -> "2 (3)";
    "3 (5)" -> "2 (3)";
    "5 (4)" -> "2 (3)";
    "2 (3)" -> "3 (2)";
    "3 (2)" -> "7 (1)";
    "7 (1)" -> Abyss;
 }
'/>

- - <img src='https://g.gravizo.com/svg?
 digraph G {
    "10 (9)" -> "2 (7)";
    "11 (8)" -> "2 (7)";
    "2 (7)" -> "7 (1)";
    "4 (6)" -> "2 (3)";
    "3 (5)" -> "2 (3)";
    "5 (4)" -> "2 (3)";
    "2 (3)" -> "7 (1)";
    "7 (1)" -> Abyss;
 }
'/>

2. Simplify the structrue by removing multiple branches nodes

- - After removing single branch nodes, triggering any sub-nodes causes the other sub-nodes on the same level isolated.
 
 - - Consider the last example, triggering node (4) causes node (5) and (6) isolated; Likewise for node (8) and (9). 
 
 - - To maximize the fun factor, we want the isolated nodes as large as possible, and hence to trigger node (5) rather than node (4) and (6). Also, the remaining node (5) -> (3) can be treated as a single branch structure.
 
 - - <img src='https://g.gravizo.com/svg?
 digraph G {
    "10 (9)" -> "2 (7)";
    "11 (8)" -> "2 (7)";
    "2 (7)" -> "7 (1)";
    "4 (6)";
    "5 (4)" ;
    "3 (3)" -> "7 (1)";
    "7 (1)" -> Abyss;
 }
'/>

- - We will not let node (3) triggers node (1) yet, because we still need to conside node (7) and its sub-nodes.
 
 - - Now trigger node (9), leave node (8) isolated and collapse branch (9) -> (7):

- - <img src='https://g.gravizo.com/svg?
 digraph G {
    "11 (8)";
    "10 (7)" -> "7 (1)";
    "4 (6)";
    "5 (4)" ;
    "3 (3)" -> "7 (1)";
    "7 (1)" -> Abyss;
 }
'/>
 
 - - Indeed, triggering node (3) will have a higher fun factor than node (7). So the trigger order is node (5) > (10) > (4) = (6) = (8) from the original structure.
 
- - <img src='https://g.gravizo.com/svg?
 digraph G {
    "11 (8)";
    "10 (7)";
    "4 (6)";
    "5 (4)" ;
    "7 (1)" -> Abyss;
 }
'/>

- - The resultant fun factor is \\( 11+10+4+5+7 = 37\\)

##### Code

1\. Using `NumPy` for better performance
```python
import numpy as np
```

2\. Define a function to calculate the fun factor:
```python
def get_fun_factor(node_parents,node_values):
    #Create a list of nodes with sub-nodes, we will reduce the structure from the largest node id
    node_reduction_order = np.unique(node_parents)[::-1]
    remaining_sum = 0
    #Create a hash map relating the sub-nodes to node_id(s)
    sub_node_id_map = {node_id:np.where(node_parents==node_id)[0] for node_id in node_reduction_order}
    for node_id in node_reduction_order[:-1]:
        sub_node_ids = sub_node_id_map[node_id] 
        #Case of single branch
        if len(sub_node_ids) == 1:
            sub_node_value = node_values[sub_node_ids[0]]
            if node_values[node_id-1] < sub_node_value:
                node_values[node_id-1] = sub_node_value
            #Instead of delete the sub-node from node_parents and node_values,
            #Simply save the value of the sub-node that has to be removed
            remaining_sum -= sub_node_value
        #Case of multiple branches
        else:
            sub_node_values = np.take(node_values,sub_node_ids)
            #Trigger the smallest sub-node
            min_sub_node_values = np.amin(sub_node_values)
            if node_values[node_id-1] < min_sub_node_values:
                node_values[node_id-1] = min_sub_node_values
            remaining_sum -= min_sub_node_values
    #remaining_sum is the negative sum of removed nodes values
    #Adding the sum of all nodes values is the desired fun factor
    remaining_sum += np.sum(node_values)
    return remaining_sum
```

3\. Necessary IO:
```python
T = int(input())
if T < 1 or T > 100:
    print("Error Input")
    exit()
for i in range(T):
    num_node = int(input())
    line_input = input()
    node_values = np.array([int(i) for i in line_input.split(" ")]) 
    line_input = input()
    node_parents = np.array([int(i) for i in line_input.split(" ")])
    print(f"Case #{i+1}: ",end="")
    print(get_fun_factor(node_parents,node_values))
```

Back to Contents

Loading