SRM 730, D1, 250-Pointer (StonesOnATree)

James S. Plank

Thu Aug 30 16:52:44 EDT 2018

Problem Statement.
A main() with the examples compiled in.
A skeleton that compiles with main.cpp.
Problem Given in Topcoder: February, 2018
Competitors who opened the problem: 217
Competitors who submitted a solution: 182
Number of correct solutions: 110
Accuracy (percentage correct vs those who opened): 50.7%
Average Correct Time: 28 minutes, 12 seconds.

In case Topcoder's servers are down

Here is a summary of the problem:

You are given the definition of a tree with weighted nodes in the vectors p and w.
Each node may have a maximum of two children.
The nodes are numbered from 0 to w.size()-1. Node i's weight is w[i].
The vector p is a vector of parent id's. Node 0 has no parent. Otherwise, node i's parent has an id that is less then i. It is specified in p[i-1].
You are playing a solitare game which has the following rules.
At each step, you may remove a stone from the tree, or add a stone to the tree.
You may only add a stone to a node if there is a stone on each of its children (or if it's a leaf node).
The game is over when you add a stone to the root.
The value of a state of the game is the sum of the weights of all nodes with stones on them.
The score of a game is the maximum value of any state of the game.
Return the minimum possible score.
The maximum size of the tree is 1,000 nodes in Topcoder. I have made that 100,000 in my tests.
Weights are between 1 and 100,000.

The class name is StonesOnATree, and the method is:

int StonesOnATree::minStones(vector <int> p, vector <int> w);

The examples

Example 0:
```
p = { 0, 1, 2, 3 }
w = { 1, 2, 2, 4, 4 }
```
The tree is a line 0 - 1 - 2 - 3 - 4. You play the game optimally as follows:
- Place the only legal stone you can, onto node 4. Let's call that node i.
- Repeat the following until you have placed a stone onto node 0:
- Place a stone on i's parent.
- Remove the stone from i.
- Set i to be i's parent.
If you play the game in this manner, your optimal score will be 8.
Example 1:
```
p = { 0, 0 }
w = { 1, 2, 3 }
Answer: 6
```

Example 2:

p = { 0 }
w = { 100000, 100000 }
Answer: 200000

Example 3:

p = {0, 0, 1, 1, 2, 2}
w = {1, 1, 1, 1, 1, 1, 1}
Answer: 4

Example 4:

p = {0, 0, 1, 2, 3, 4, 4, 2, 1, 3, 6, 7}
w = {1, 2, 3, 4, 5, 6, 6, 7, 8, 8, 8, 9, 10}
Answer: 22

Testing yourself

Like the Cryptography Problem, I have a shell script tests.sh, that you can use to test your program. When you run tests.sh, your answer should be identical to answers.txt. My program took 0.75 seconds on tests.sh, without compiler optimization.

Hints

Like most problems that involve trees, this one involves recursion. In this case, it's a postorder tree traversal. What you want to do is solve the problem recursively for every subtree in the tree. When you're done with a subtree rooted at node n, you'll return the minimum score for that subtree, and that subtree will only have one stone in it -- in node n.

What I did was convert p to an adjacency list representation. I have a vector of vectors of integers called Adj, where Adj[i] is a vector of the id's of the children of node i. And I stored w in the class in a vector named W.

You should stop here and add Adj and W to the StonesOnATree class, and create them from p and w. Print them out and verify that they are correct for the examples.

Next, I wrote added a method called S() to the class:

int StonesOnATree::S(int n);

This solves the problem for the subtree rooted at node n. S(n) performs a postorder traversal, so when you call it on a node n, you'll do the following:

If node n is a leaf, put a stone there. You can easily calculate the return value.
If node n is not a leaf, then you need to call S() on each of n's children. When this is done, there are stones in your node's children, and nowhere else in the stubtree, and you have stored solutions for your children. You place a stone in n, and in doing so, you can calculate the solution for S(n). You remove the stones from n's children, and return the solution.

In my solution, I didn't really store the state of the game by explicitly adding and removing stones. You can solve the problem just by looking at return values for S() and the vector W.

I'm not telling you how to do this calculation -- I want you to use your logic skills to figure it out.

Here is ASCII art for the last example, which should help you a lot!

                                                            ---------------------
                                                            | N: 0              |
                                                            | W[0]: 1           |
                                                            | Adj[0] = { 1, 2 } |
                                                            | S(0) = 22         |
                                                            ---------------------
                                                          /                     \
                                                   /-----/                       \-----\
                                                  /                                     \
                             ---------------------                                       ---------------------
                             | N: 1              |                                       | N: 2              |
                             | W[1] = 2          |                                       | W[2] = 3          |
                             | Adj[1] = { 3, 9 } |                                       | Adj[2] = { 4, 8 } |
                             | S(1) = 18         |                                       | S(2) = 22         |
                             ---------------------                                       ---------------------
                            /                     \                                     /                     \
           ---------------------           ---------------------              ---------------------           ---------------------
           | N: 3              |           | N: 9              |              | N: 4              |           | N: 8              |
           | W[3] = 4          |           | W[9] = 8          |              | W[4] = 5          |           | W[8] = 8          |
           | Adj[3] = { 5, 10 }|           | Adj[9] = {}       |              | Adj[4] = { 6, 7 } |           | Adj[8] = {}       |
           | S(3) = 18         |           | S(9) = 8          |              | S(4) = 22         |           | S(8) = 8          |
           ---------------------           ---------------------              ---------------------           ---------------------
          /                     \                                             /                    \
 ---------------------           ---------------------              ---------------------           ---------------------
 | N: 5              |           | N: 10             |              | N: 6              |           | N: 7              |
 | W[5] = 6          |           | W[10] = 8         |              | W[6] = 6          |           | W[7] = 7          |
 | Adj[5] = {}       |           | Adj[10] = {}      |              | Adj[6] = { 11 }   |           | Adj[7] = { 12 }   |
 | S(5) = 6          |           | S(10) = 8         |              | S(6) = 15         |           | S(7) = 17         |
 ---------------------           ---------------------              ---------------------           ---------------------
                                                                              |                              |
                                                                    ---------------------           ---------------------
                                                                    | N: 11             |           | N: 12             |
                                                                    | W[11] = 9         |           | W[12] = 10        |
                                                                    | Adj[11] = {}      |           | Adj[12] = {}      |
                                                                    | S(11) = 9         |           | S(12) = 10        |
                                                                    ---------------------           ---------------------