Description
Following your promotion to CTO after your success with multiple popular Spider-Man services (check 14897 for backstory), you’ve caught the attention of multiple tech firms as well as criminals. One of which is the Syndicate, a secret criminal organization with deep roots in London since the Victorian era. They blackmailed you into building their organization chart tracker. If you refuse their request, a picture of you showering with your duck toy will be released. The stakes are at an all time high, keep track of the organization chart using tree data structure if you still want to be a respectable CTO! Welcome to ‘The Syndicate: Project Tree’…
Commands
Add <auth> <cun> <parent>
During this command, you will be given 3 integers input. <auth> represents authority, the commanding power a thug has in the organization. <cun> represents cunning, the defensive power a thug has in the organization. While <parent> represents the parent node of the node to be added.
When adding a node, you will assign a unique ID (never repeats) to a thug node along with the authority, and cunning values. The node will then be inserted under the parent node. Prioritize adding the node to the right branch first (thug boss always seeks a right-hand advisor). If both branches are filled, then check if the new node has a higher authority point than the existing child nodes. If the authority point is higher, insert the new node in between the parent and the child node with lower authority score. If both child nodes have equal authority, insert the new node between the left branch node and the parent node. The weaker child node along with all of its subtree will then serve the new node in the right branch. However, if the authority point is lower than or equal to the existing child nodes, do not insert the new node (they’re too weak).
If adding a node is successful, add 1 point of ‘authority’ and ‘cunning’ to the new node’s parent and all of its ancestor nodes.
* If the tree does not have a root node at the moment, make the new node a root node (new head of the syndicate).
Coup <id>
During this command, you will be given an integer, the ID <id> of the node a coup occurs in. During a coup, the children nodes (left & right) will attempt to remove their parent node (node <id>) from the tree, a power struggle! Compare the sum of child nodes’ authority value against the parent node’s cunning value.
If the combined authority is greater than the cunning value (successful coup), remove the parent node (node <id>) and replace it with the child node with the higher authority value. Shift the rest of the child nodes up the tree according to the same rule. However, if the coup is unsuccessful, remove both children from the tree and replace them with their child whose authority value is bigger. If a node has only one child, that child automatically replaces them. If two nodes have equal authority, prioritize the right branch.
Investigate <id> <intel>
An investigation by the police department!
During this command, you will be given 2 integers, the ID <id> of the node being investigated and <intel> intelligence value of the police. While being investigated, measure the height of the subtree starting from node <id>. If the height of the subtree is greater than or equal to the intel value, the subtree survives. Otherwise, remove the entire subtree from the organization (arrested by the police).
Guarantees & Notes
- Note that you should always prioritize the right branch first before the left branch when adding or shifting nodes unless specified otherwise.
- Note that when adding a new node, if there is no root node in the tree at the moment. That new node will become the root node.
- Note that the ID of a node is a unique value, and is only generated once starting from ‘1’ and increments by 1 each time. Even if a node is not added to the tree during "ADD" command!
- It is guaranteed that the <id> specified will always exist in the tree.
- It is guaranteed that the height of the tree will not exceed 500.
- You’re only allowed to use <iostream>, <string>, and <vector>.
- Note that if any part is still unclear/visualization needed. Please check the homework 3 slides first in case an answer is present there. If the answer is not present, don’t hesitate to reach out to TAs for help.
- Testcase 1~9 can be used to test your code’s correctness as it focuses on different areas of the problem.
Hints for Debugging
Test cases will test Add, Investigate, then Coup in the following order.
It is recommended to implement each command as one function, then you can call function in main accordingly.
The following testcases contain new commands as listed below:
- Testcase 1: Add is introduced
- Testcase 3: Investigate is introduced
- Testcase 7: Coup is introduced
More hints may be given during TA labs on Monday if deemed necessary. And more hints may be released here later.
Input
The first line contains 2 integers <auth> and <cun> which specifies the initial authority and cunning score of the root node; the ID of the root node is 1 by default.
The following lines will contain one of the following commands:
- Add
- Coup
- Investigate
Parameter size:
| Parameter name | Details | Size |
| auth | The authority value | 1 ≤ auth ≤ 1,000 |
| cun | The cunning value | 1 ≤ cun ≤ 1,000 |
| parent | ID of parent node | Current IDs in the tree |
| id | ID of the node | Current IDs in the tree |
| intel | The intelligence value | 1 ≤ cun ≤ 1,000 |
Output
Output according to the following specifications:
- If Add is not successful (too weak), output: “weakling!”
- If a Coup is successful, output: “dethroned!”
- If a Coup is unsuccessful, output: “traitors!”
- If an Investigate is successful, output: “<id> - busted!”
- If an Investigate is unsuccessful, output: “<id> - safe!”
Finally, after all commands are performed, Output: “=== END ===”.
It should then be followed by a summary of the tree:
- A preorder traversal output of the tree: “Pre-order Traversal: <preorder>”
- A sum of the authority value of remaining nodes in the tree: “Total Authority: <auth>”
When printing pre-order traversal, each element is separated by a blank space ‘ ‘ (even for the final element).
If the tree is empty, output nothing during traversal and ‘0’ for authority.
Enter a newline after every output.