forked from keshavnandan/Topcoder
-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathUnrelatedPaths.html
46 lines (38 loc) · 4.74 KB
/
UnrelatedPaths.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
<html><body bgcolor="#000000" text="#ffffff"><table><tr><td colspan="2"><h3>Problem Statement</h3></td></tr><tr><td>    </td><td><p>
This problem is about paths on a tree.
A path is any sequence of one or more vertices such that all the vertices are distinct and each pair of consecutive vertices is connected by an edge of the tree.
</p>
<p></p>
<p>
Our tree is a rooted tree with N+1 vertices, labeled 0 through N.
The label of the root is 0.
For each i, the parent of vertex i has a number smaller than i.
You are given the description of the tree: a vector <int> <b>parent</b> with N elements.
For each i, the vertex <b>parent</b>[i] is the parent of the vertex i+1.
</p>
<p></p>
<p>
The vertex u is an ancestor of the vertex v if u lies on the (only) path that connects v to the root.
Note that each vertex is its own ancestor.
Also note that the root is an ancestor of all other vertices.
</p>
<p></p>
<p>
Two paths A and B in our tree are said to be related if path A contains a vertex u and path B contains a vertex v such that one of u, v is an ancestor of the other.
</p>
<p></p>
<p>
We want to choose many paths in such a way that no two of them will be related.
Find and return the largest possible number of pairwise unrelated paths in the given tree.
</p></td></tr><tr><td colspan="2"><h3>Definition</h3></td></tr><tr><td>    </td><td><table><tr><td>Class:</td><td>UnrelatedPaths</td></tr><tr><td>Method:</td><td>maxUnrelatedPaths</td></tr><tr><td>Parameters:</td><td>vector <int></td></tr><tr><td>Returns:</td><td>int</td></tr><tr><td>Method signature:</td><td>int maxUnrelatedPaths(vector <int> parent)</td></tr><tr><td colspan="2">(be sure your method is public)</td></tr></table></td></tr><tr><td colspan="2"><h3>Limits</h3></td></tr><tr><td>    </td><td><table><tr><td>Time limit (s):</td><td>2.000</td></tr><tr><td>Memory limit (MB):</td><td>256</td></tr><tr><td>Stack limit (MB):</td><td>256</td></tr></table></td></tr><tr><td colspan="2"><h3>Constraints</h3></td></tr><tr><td align="center" valign="top">-</td><td>N will be between 0 and 50, inclusive.</td></tr><tr><td align="center" valign="top">-</td><td><b>parent</b> will contain exactly N elements.</td></tr><tr><td align="center" valign="top">-</td><td>For each i, <b>parent</b>[i] will be between 0 and i, inclusive.</td></tr><tr><td colspan="2"><h3>Examples</h3></td></tr><tr><td align="center" nowrap="true">0)</td><td></td></tr><tr><td>    </td><td><table><tr><td><table><tr><td><pre>{0, 1, 1, 2, 3}</pre></td></tr></table></td></tr><tr><td><pre>Returns: 2</pre></td></tr><tr><td><table><tr><td colspan="2">The vector <int> <b>parent</b> tells us the following information:
<ul>
<li>The parent of vertex 1 is vertex 0.</li>
<li>The parent of vertex 2 is vertex 1.</li>
<li>The parent of vertex 3 is vertex 1.</li>
<li>The parent of vertex 4 is vertex 2.</li>
<li>The parent of vertex 5 is vertex 3.</li>
</ul>
In this tree it is possible to select two unrelated paths.
One possible way of doing so is to select the paths 4-2 and 3-5.</td></tr></table></td></tr></table></td></tr><tr><td align="center" nowrap="true">1)</td><td></td></tr><tr><td>    </td><td><table><tr><td><table><tr><td><pre>{0, 0, 1, 1, 2, 2}</pre></td></tr></table></td></tr><tr><td><pre>Returns: 4</pre></td></tr><tr><td><table><tr><td colspan="2"></td></tr></table></td></tr></table></td></tr><tr><td align="center" nowrap="true">2)</td><td></td></tr><tr><td>    </td><td><table><tr><td><table><tr><td><pre>{0, 1, 2, 3}</pre></td></tr></table></td></tr><tr><td><pre>Returns: 1</pre></td></tr><tr><td><table><tr><td colspan="2"></td></tr></table></td></tr></table></td></tr><tr><td align="center" nowrap="true">3)</td><td></td></tr><tr><td>    </td><td><table><tr><td><table><tr><td><pre>{0,1,1,2,2,2,4,6,5,0,10,5,12,12,10,4,16,12,5,3,20,12,11,21,9,5,1,20,15,24,6,8,15}
</pre></td></tr></table></td></tr><tr><td><pre>Returns: 17</pre></td></tr><tr><td><table><tr><td colspan="2"></td></tr></table></td></tr></table></td></tr><tr><td align="center" nowrap="true">4)</td><td></td></tr><tr><td>    </td><td><table><tr><td><table><tr><td><pre>{0,1,1,1,1,0,2,5,1,6,7,10,5,10,8,5,16,14,8,14,4,14,15,21,0,24,11,1,9,18,13,20,6,28,19,28,14,11,38,26,25,10,23,43}
</pre></td></tr></table></td></tr><tr><td><pre>Returns: 19</pre></td></tr><tr><td><table><tr><td colspan="2"></td></tr></table></td></tr></table></td></tr></table><p>This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved. </p></body></html>