Connection Status:
Competition Arena > StonesOnATree

StonesOnATree

SRM 730 · 2018-02-19 · by lg5293

SRM 730 · 2018-02-19 · by lg5293 · Dynamic Programming
Class Name: StonesOnATree
Return Type: int
Method Name: minStones
Arg Types: (vector<int>, vector<int>)
Problem Statement

Problem Statement

You are given a rooted tree with n nodes. The nodes are labeled from 0 to n-1. Node 0 is the root. Each node of the tree has at most two children.



You are given the description of the tree: the int[]s p and w. The int[] p has n-1 elements. For each valid i, node p[i] is the parent of node (i+1). You may assume that for each i we have p[i] ≤ i. The int[] w has n elements. For each valid i, w[i] is the weight of node i.



The int[] w has a special property: it is non-decreasing. That is, for each valid i we have w[i-1] ≤ w[i].



All nodes of the tree are currently empty. You are now going to play a game with the tree and an unlimited supply of stones. The game is played in turns. In each turn you can either remove a single stone from anywhere into a tree, or you can place a single stone onto a node of the tree. However, there is a restriction on placing the stones: you may only place a stone onto a node if all of its children currently have stones placed on them. (Note that this means that you can always place a stone onto any leaf of the tree.)



The weight of a given state of the game is equal to the sum of weights of nodes with stones.



You win the game by placing a stone onto the root of the tree. You want to win the game. If there are multiple ways to do so, you prefer a way for which the maximum weight of a state during the game is minimized. Compute and return this weight. In other words, compute and return the smallest W for which there is a way to win the game such that during the game the total weight of nodes with stones never exceeds W.

Constraints

  • p will have between 1 and 999 elements, inclusive. (Thus, the number of nodes is between 2 and 1,000, inclusive.)
  • The i-th element of p will be between 0 and i, inclusive.
  • In the given tree each node will have at most two children. In other words, each value will appear in p at most twice.
  • w will have exactly len(p)+1 elements.
  • Each element of w will be 1 and 10^5, inclusive.
  • Elements of w will be non-decreasing.
Examples
0)
{0,1,2,3}
{1,2,2,4,4}
Returns: 8

There are five nodes in a line. Here, one optimal solution is as follows: Place stone on node 4 (weight = 4). Place stone on node 3 (weight = 8). Remove stone from node 4 (weight = 4). Place stone on node 2 (weight = 6). Place stone on node 1 (weight = 8). Remove stone from node 2 (weight = 6). Place stone on node 0 (weight = 7). The maximum weight over all states is 8. It can be shown there is no other sequence of moves that has a smaller maximum weight.

1)
{0,0}
{1,2,3}
Returns: 6

In order to be able to place a stone onto node 0 we have to place stones onto both of its children. Thus, at the end of the game each of these three nodes will have a stone.

2)
{0}
{100000,100000}
Returns: 200000
3)
{0,0,1,1,2,2}
{1,1,1,1,1,1,1}
Returns: 4
4)
{0,0,1,2,3,4,4,2,1,3,6,7}
{1,2,3,4,5,6,6,7,8,8,8,9,10}
Returns: 22

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

Coding Area

Language: C++17 · define a public class StonesOnATree with a public method int minStones(vector<int> p, vector<int> w) · 126 test cases · 2 s / 256 MB per case

Submitting as anonymous