CoverTreePaths | Topcoder Archive

Problem Statement

You are given tree on n vertices that are labeled 0 through n-1. The tree is rooted at vertex 0. For each i ≥ 1, the parent of vertex i is p[i-1].

You are also given an int[] d. The value d[i] represents the demand of vertex i. Your goal is to assign an integer value v[j] to each vertex j so that the total sum of the values of the vertices on the unique simple path from vertex i to the root (including both vertex i and the root) is at least d[i].

Furthermore, with each vertex i is associated a positive integer cost c[i]. Then, the cost of an assigment v is the summation of v[i] * c[i] over all 0 ≤ i < n.

Return the minimum cost over all the assignments that satisfy the demands given by d.

On the input you will be given p, d and c corresponding only to the vertices 0, ..., t - 1, for some 2 ≤ t ≤ n. The rest of these int[]s is generated by the following pseudocode, that is parametrized by int[] params. Watch out for integer overflow.

for i = t-1 .. n-2
	p[i] = (params[0] * p[i-1] + params[1]) mod (i+1)

for i = t .. n-1
	d[i] = 1 + ((params[2] * d[i-1] + params[3]) mod params[4])

for i = t .. n-1
	c[i] = 1 + ((params[5] * c[i-1] + params[6]) mod params[7])

Definition

Class:: CoverTreePaths
Method:: minimumCost
Parameters:: int, int[], int[], int[], int[]
Returns:: long
Method signature:: long minimumCost(int n, int[] p, int[] d, int[] c, int[] params)
(be sure your method is public)

Notes

The intended solution should work within the given time limit for arbitrary int[]s p, d, c, and params that satisfy the constraints. It does not depend on any special properties of the pseudorandom generator.

Constraints

n will be between 2 and 100,000, inclusive.
p will contain between 1 and min(n - 1, 499) elements, inclusive.
Each p[i] will be between 0 and i, inclusive.
d will contain |p|+1 elements.
c will contain |p|+1 elements.
Each element of d will be between 1 and 1,000,000, inclusive.
Each element of c will be between 1 and 1,000,000, inclusive.
params will contain exactly 8 elements.
For each i in {0, 1, 2, 3, 5, 6}, params[i] will be between 0 and 1,000,000, inclusive.
params[4] and params[7] will be between 1 and 1,000,000, inclusive.

Examples

```
4
```
```
{0, 1, 2}
```
```
{2, 2, 1, 3}
```
```
{9, 4, 3, 3}
```
```
{1, 1, 1, 1, 1, 1, 1, 1}
```
```
Returns: 21
```
One solution for this case is to set v[0]=2, v[1]=0, v[2]=0, and v[3]=1. This has the total cost of 2*9+0*4+0*3+1*3=21.

{0, 1, 2}

{2, 2, 1, 3}

{9, 4, 3, 2}

{1, 1, 1, 1, 1, 1, 1, 1}

Returns: 20

{0, 0, 0, 0, 1}

{1, 2, 2, 2, 7, 1}

{2, 4, 5, 6, 1, 1}

{1, 1, 1, 1, 1, 1, 1, 1}

Returns: 9

The optimum here is to set v[0]=2, v[4]=5, and each other value of v to be 0.

{0, 0, 2, 0, 1, 4, 5, 1, 4}

{1, 2, 4, 2, 7, 1, 3, 1, 10, 1}

{2, 4, 3, 6, 1, 2, 6, 9, 10, 4}

{1, 1, 1, 1, 1, 1, 1, 1}

Returns: 20

{0, 1, 2, 3}

{1, 2, 3, 4, 5}

{5, 4, 3, 2, 1}

{1, 1, 1, 1, 1, 1, 1, 1}

Returns: 15

{0}

{8, 5}

{10, 1}

{1, 1, 1, 1, 1, 1, 1, 1}

Returns: 80

```
100
```
```
{0}
```
```
{3, 1}
```
```
{900, 820}
```
```
{2, 7, 3, 11, 200, 4, 2, 321}
```
```
Returns: 58344
```
Most of the input in this case is generated by the provided code. First ten entries of p are {0, 1, 0, 3, 3, 1, 2, 3, 4, 5}, of d are {3, 1, 15, 57, 183, 161, 95, 97, 103, 121}, and of c are {900, 820, 73, 295, 220, 241, 4, 19, 79, 319}.

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)2024, Topcoder, Inc. All rights reserved.