Connection Status:
Competition Arena > CoverTreePaths

CoverTreePaths

TCO19 SRM 744 · 2018-12-13 · by boba5551

TCO19 SRM 744 · 2018-12-13 · by boba5551 · Greedy
Class Name: CoverTreePaths
Return Type: long
Method Name: minimumCost
Arg Types: (int, vector<int>, vector<int>, vector<int>, vector<int>)
Problem Statement

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])

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
0)
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.

1)
4
{0, 1, 2}
{2, 2, 1, 3}
{9, 4, 3, 2}
{1, 1, 1, 1, 1, 1, 1, 1}
Returns: 20
2)
6
{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.

3)
10
{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
4)
5
{0, 1, 2, 3}
{1, 2, 3, 4, 5}
{5, 4, 3, 2, 1}
{1, 1, 1, 1, 1, 1, 1, 1}
Returns: 15
90)
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}.

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

Coding Area

Language: C++17 · define a public class CoverTreePaths with a public method long long minimumCost(int n, vector<int> p, vector<int> d, vector<int> c, vector<int> params) · 92 test cases · 2 s / 256 MB per case

Submitting as anonymous