Connection Status:
Competition Arena > TwoDistance

TwoDistance

SRM 786 · 2020-05-14 · by vivek1998299

SRM 786 · 2020-05-14 · by vivek1998299 · Greedy, Recursion, Sorting
Class Name: TwoDistance
Return Type: long
Method Name: findMinValue
Arg Types: (int, vector<int>, vector<int>, int, int)
Problem Statement

Problem Statement

This problem has a non-standard time limit: 5 seconds.

You are given an undirected tree on N nodes numbered from 0 to N-1. Each node x has some value V[x]. These values are then used to compute the cost of each node. Your task is to find the sum of costs of all nodes in the tree.

The cost of a node x is defined as follows:

Let's say the set of nodes at distance 2 from node x is set S. The cost of this node is the minimum value of abs(V[a]-V[b]) where a and b belong to S and a != b. If size of set S is less than 2, then the cost of node x is 0.

You are given the int N, the int[]s edge and int[]s val, and the ints D, seed. 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

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

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

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

Notes

  • The distance between two nodes is the number of edges in the shortest path between the two nodes.

Constraints

  • N will be between 3 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 2,147,483,647, inclusive.
  • D will be between 1 and N, inclusive.
  • seed will be between 0 and 2,147,483,647, inclusive.
Examples
0)
3
{-1}
{}
1
1
Returns: 0
1)
10
{-1}
{}
9
340406567
Returns: 6115640787
2)
5
{-1}
{}
3
1088687237
Returns: 1157676346
3)
8
{-1}
{}
4
1660459886
Returns: 1380655965
4)
6
{-1}
{}
1
1259879209
Returns: 1719981821
152)
3
{-1, 0, 1}
{}
3
2
Returns: 0

Here, we can see that no node will have greater than 1 nodes at a distance of 2. Hence answer is 0.

153)
5
{-1}
{1, 2, 3, 4, 5}
3
4
Returns: 6

Here we will obtain E array as {-1, 0, 1, 2, 2} and hence the edges as 0-1, 1-2, 2-3, 2-4. For node 0, only node 2 is at a distance of 2, hence cost for node 0 is 0. For node 1, it has nodes 3 and 4 at a distance of 2, hence cost for node 1 is abs(V[3]-V[4]) = 1 For node 2, again cost is 0. For node 3, nodes 1 and 4 are at a distance 2, hence cost is abs(V[1]-V[4]) = 3. Similarly for node 4, cost is 2. Hence answer is 1 + 2 + 3 = 6.

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

Coding Area

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

Submitting as anonymous