Connection Status:
Competition Arena > RewardOnATree

RewardOnATree

TCO17 Pittsburgh · 2017-03-31 · by boba5551

TCO17 Pittsburgh · 2017-03-31 · by boba5551 · Dynamic Programming
Class Name: RewardOnATree
Return Type: int
Method Name: collect
Arg Types: (vector<int>, vector<int>)
Problem Statement

Problem Statement

You have a tree with N nodes, conveniently numbered 0 through N-1. You are given a int[] parent with N-1 elements. For each i between 1 and N-1, inclusive, there is an edge between the nodes i and parent[i-1]. The distance between two nodes is the number of edges on the only simple path that connects the two nodes.

You are going to traverse a part of the tree. During the traversal you may enter each node arbitrarily many times. You will get a reward whenever you enter a node for the first time. The reward may be different for different nodes. For some nodes the reward may even be negative. The reward cannot be avoided: if you enter a node, you get the reward, regardless of whether it is positive or not. In each node you only get the reward once, the next visits to the node don't give you any additional rewards.

You are given the rewards in the int[] reward. Here, reward[i] is the amount you get when you visit node i for the first time.

While traversing the tree, you have two valid types of movement:

  • You can move from your current node u to any of the adjacent nodes (i.e., along any edge that leads from u).
  • You can move from your current node u to any node v such that the distance from node u to node 0 is the same as the distance from node v to node 0.

You start your traversal by entering node 0 and collecting its reward. You may end your traversal in any node. Compute and return the maximal total reward you can have at the end of your traversal.

Constraints

  • N will be between 1 and 2,000, inclusive.
  • parent will contain exactly N - 1 elements.
  • For each i, parent[i] will be between 0 and i, inclusive.
  • reward will contain exactly N elements.
  • Every element of reward will be between -10,000 and 10,000, inclusive.
Examples
0)
{0, 1, 0, 0, 4}
{1, 3, 2, 1, -1, 2}
Returns: 9

An optimal sequence of visiting nodes is as follows: 0, 3, 0, 1, 2, 5. Note that it is possible to move from node 2 to node 5 because both node 2 and node 5 are at distance 2 from node 0. The collected reward is 1 + 1 + 3 + 2 + 2. Note that the reward for node 0 is counted only once.

1)
{0, 1, 2, 3, 4}
{1, 2, 3, -2, -1, 2}
Returns: 6
2)
{0, 1, 2, 3, 4}
{1, 2, 3, -2, -1, 4}
Returns: 7

The maximal reward is obtained by visiting all the nodes. Observe that we can visit node 5 (having reward 4) only by visiting node 3 (having reward -2) and node 4 (having reward -1) first.

3)
{}
{-10000}
Returns: -10000

The reward at node 0 is always collected.

4)
{0, 1, 2, 3, 0, 5, 6, 0, 8, 9}
{-2, 0, 0, 0, 1, -1, 1, -1, -1, 1, -1}
Returns: 1

Submissions are judged against all 113 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class RewardOnATree with a public method int collect(vector<int> parent, vector<int> reward) · 113 test cases · 2 s / 256 MB per case

Submitting as anonymous