Connection Status:
Competition Arena > RootItRight

RootItRight

SRM 763 · 2019-07-16 · by abdullahkool768

SRM 763 · 2019-07-16 · by abdullahkool768 · Dynamic Programming, Graph Theory, Math
Class Name: RootItRight
Return Type: long
Method Name: findMinimumTotalCost
Arg Types: (int, vector<int>, vector<int>, int, int, int)
Problem Statement

Problem Statement

You are given an undirected tree on N nodes, numbered from 0 to N-1. Each node x has some value V[x]. Below we define how to compute the cost of rooting the tree at some node r. Your task is to find the root for which that cost is minimized and to return that minimal cost.

When we root the tree at the node r, each node x will require some payment C[r,x]. The cost of rooting the tree at r is the sum of C[r,x] over all x. The value C[r,x] is defined as follows:

Let the nodes on the (unique) simple path from the root r to x be the nodes r = s0, s1, s2, ..., sk = x. Then, C[r,x] = V[s0] * 0 + V[s1] * 1 + ... + V[sk] * k.


You are given the int N, the int[]s edge and val, and the ints D, seed, and MX. Use the pseudocode below to generate the edges of the tree and the values of all its nodes. 

A[0] = seed
for i = 1 to 2*N-1:
    A[i] = (A[i-1] * 1103515245 + 12345) modulo 2147483648

E = edge
for i = size(edge) to N-1:
    E[i] = (A[i] modulo min(i,D)) + i - min(i,D) 

for i = 1 to N-1:
    the tree contains an edge between i and E[i]

V = val
for i = size(val) to N-1:
    V[i] = A[N+i] modulo MX

Notes

  • Be careful to avoid potential overflows.
  • The reference solution would correctly solve any case that matches the constraints. It does not depend on the properties of the pseudorandom generator.

Constraints

  • N will be between 1 and 200,000, inclusive.
  • The number of elements in edge will between 1 and min(N, 100), inclusive.
  • edge[0] will be equal to -1.
  • For i > 0, edge[i] will be between 0 and i-1, inclusive.
  • The number of elements in val will between 0 and min(N, 100), inclusive.
  • Each element of val will be between 0 and MX-1, inclusive.
  • D will be between 1 and 200,000, inclusive.
  • seed will be between 0 and 2,147,483,647, inclusive.
  • MX will be between 1 and 1,000, inclusive.
Examples
0)
2
{-1}
{}
114575
304655178
1000
Returns: 688
1)
5
{-1}
{}
48772
383616353
1000
Returns: 2300
2)
7
{-1}
{}
190629
682098057
1000
Returns: 3866
3)
2
{-1}
{}
7775
685975157
1000
Returns: 376
4)
22
{-1}
{}
4784
1269929825
1000
Returns: 62245
200)
4
{-1,0,1,2}
{4,3,3,4}
1
0
5
Returns: 18

The tree is a path 0-1-2-3. If we root it at 0 or 3, the cost is 33. If we root it at 1 or 2, the cost is only 18. Thus, the correct return value is 18. When we root the tree at node 1, the payments for the individual nodes are as follows: C[1,0] = 3*0 + 4*1 = 4 C[1,1] = 3*0 = 0 C[1,2] = 3*0 + 3*1 = 3 C[1,3] = 3*0 + 3*1 + 4*2 = 11

201)
4
{-1,0,0,0}
{3,2,3,0}
1
0
4
Returns: 5

This tree is a star with node 0 in the center. Node 0 is also the optimal root. The payments are C[0,0] = 0, C[0,1] = 2, C[0,2] = 3, and C[0,3] = 0, thus the total cost of rooting the tree at node 0 is 0+2+3+0 = 5.

202)
5
{-1,0,0,1,3}
{5,0,3,2,3}
1
0
6
Returns: 20

Again, an optimal root for this tree is node 0. The total cost is the sum of the following payments: C[0,0] = 5*0 = 0 C[0,1] = 5*0 + 0*1 = 0 C[0,2] = 5*0 + 3*1 = 3 C[0,3] = 5*0 + 0*1 + 2*2 = 4 C[0,4] = 5*0 + 0*1 + 2*2 + 3*3 = 13

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

Coding Area

Language: C++17 · define a public class RootItRight with a public method long long findMinimumTotalCost(int N, vector<int> edge, vector<int> val, int D, int seed, int MX) · 209 test cases · 2 s / 256 MB per case

Submitting as anonymous