coding

Página 1

Binary tree [Script]

subject Coding

casino 100 points

DESCRIPTION

Please read the Binary tree question before attempting this problem.

Input

First line contains an integer d, the depth of the binary tree.

Next line contains 2d+1 - 1 integers ai, each denoting the value of the nodes. It is the array representation of the binary tree. -1denotes a non-existing node. Note that values in the binary tree are unique at any point of time.

Next line contains an integer n, the number of queries.

There are four types of queries.

ADD x y z: Add a new node with a value z as y child of x. y is either "L" or "R". L represents Left child and R represents Right child.

UPDATE x y: Change the node with value x to y

DELETE x: Delete the node with value x

SUM x y: Output the sum of sub-tree rooted at y at state x. Initial state of the binary tree is 0. Each of the queries ADD, UPDATE or DELETE changes the state of the tree and the new state identifier will be one more than the previous state.

Output

For every SUM x y query, output the sum of sub-tree rooted at y at state x in a new line. If x if -1, assume the latest state of the binary tree.

Constraints

1 <= d <= 100

1 <= ai <= 105

1 <= n <= 100

Sample test cases

Input

3

2 7 5 1 6 -1 9 -1 -1 8 11 -1 -1 4 -1

7

ADD 1 L 3

SUM 0 7

UPDATE 11 13

SUM -1 7

DELETE 5

SUM 0 9

SUM 3 2

Output

33

38

13

53

EXECUTION TIME LIMIT

Default.

Página 2

Social Network

subject Subjective

casino 5 points

DESCRIPTION

Suppose there is a social network of experts where each expert is associated with one or more skills. A collaborative task is one which requires a set of skills. And the team formation problem is to find a team of experts who are able to cover all the required skills and communicate with one another in an effective manner. The communication cost between 2 experts is the shortest distance between them in the given social network.

Given a task T with a required skillset, we need to find a team of experts [X, Y, Z…] such that among the members of the team we have collectively covered all the required skills with the minimum cost of communication. Discuss various approaches to solve it.

Hint: In large graphs a heuristic approach which may not give the most optimized solution but a reasonably good solution, is also acceptable.

Input:

A weighted graph in adjacency matrix form where each node represents an expert, the value of a node represents the skills possessed by that expert and the weight of an edge represents the communication cost between two experts.

Solution:

An algorithm and code with the analysis of time and space complexity.

Instructions:

You need to design an algorithm

You can submit your solution by writing in the text box on the right side.

In case you need to add diagrams/pictures

You can drag and drop images in the text area to upload it.

You can use free tools like https://www.draw.io/ for the wireframes, flow chart, etc.

If you are using https://www.draw.io/, make sure you export it as an image.