Connection Status:
Competition Arena > ETSums

ETSums

SRM 763 · 2019-07-16 · by abdullahkool768

SRM 763 · 2019-07-16 · by abdullahkool768 · Graph Theory, Math, Recursion
Class Name: ETSums
Return Type: int
Method Name: findSumOfETSums
Arg Types: (int, vector<int>, vector<int>, int, int, int)
Problem Statement

Problem Statement

You are given a rooted tree on N nodes. The nodes are numbered from 0 to N-1 with node 0 being the root. Each node x has three associated values: its parent P[x], its cost C[x], and its timestamp T[x].

You are given the parents and the costs of all nodes. The timestamps correspond to the order in which a depth-first search discovers the nodes of the tree. Formally, the timestamps can be computed using the following pseudocode: 

counter = 1
define dfs(current_id):
    T[ current_id ] = counter
    counter += 1
    for each child_id such that P[child_id] = current_id:
        dfs(child_id)

// note that the children of a node are always processed in increasing order of their IDs
// in order to compute all timestamps, call:
dfs(0)

For each node x we will now define a new number: it's ET value, denoted ET[x].

Let the nodes on the (unique) simple path from the root to x be the nodes 0 = v0, v1, v2, ..., vk = x. The value ET[x] is defined as follows:

ET[x] = sumi C[vi] * i^T[x]

The sum is over all valid indices i, that is, 0 <= i <= k. The symbol ^ denotes exponentiation (i to the power of T[x]).

Find and return the sum of ET-values of all nodes in the tree, modulo 10^9+7.


In order to keep the test data small, the input for this problem is given in the following form: You are given the int N, the int[]s parent and cost, and the ints D, seed, and MX. Use the following pseudocode to generate the arrays P and C: 

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

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

C = cost
for i = size(cost) to N-1:
	C[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 parent will between 1 and min(N, 100), inclusive.
  • parent[0] will be equal to -1, representing the fact that node 0 has no parent.
  • For each i, parent[i] will be less than i.
  • Number of elements in cost will between 0 and min(N, 100), inclusive.
  • Each element of cost 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,000,000, inclusive.
Examples
0)
2
{-1}
{}
114575
304655178
1000000000
Returns: 125568817
1)
5
{-1}
{}
48772
383616353
1000000000
Returns: 77279466
2)
7
{-1}
{}
190629
682098057
1000000000
Returns: 328481118
3)
2
{-1}
{}
7775
685975157
1000000000
Returns: 654132376
4)
22
{-1}
{}
4784
1269929825
1000000000
Returns: 447446552
199)
4
{-1,0,1,2}
{4,3,3,4}
1
0
5
Returns: 405

This tree is a path 0 -> 1 -> 2 -> 3. All values of P and C are given. The values of T are {1,2,3,4}. The ET values look as follows: ET[0] = 4*0^1 = 0 ET[1] = 4*0^2 + 3*1^2 = 3 ET[2] = 4*0^3 + 3*1^3 + 3*2^3 = 27 ET[3] = 4*0^4 + 3*1^4 + 3*2^4 + 4*3^4 = 375 Therefore the sum of all ET values is 0 + 3 + 27 + 375 = 405.

200)
5
{-1,0,0,1,3}
{5,0,3,2,3}
1
0
6
Returns: 294

The tree looks as follows: 0 / \ 1 2 / 3 / 4 Timestamps are T = {1, 2, 5, 3, 4}. ET values are as follows: ET[0] = 5*0^1 = 0 ET[1] = 5*0^2 + 0*1^2= 0 ET[2] = 5*0^5 + 3*1^5 = 3 ET[3] = 5*0^3 + 0*1^3 + 2*2^3 = 16 ET[4] = 5*0^4 + 0*1^4 + 2*2^4 + 3*3^4 = 275 Finally, the sum will be 0 + 0 + 3 + 16 + 275 = 294.

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

In this tree each node other than 0 is its child. The timestamps are T = {1,2,3,4} again, and the ET values are {0, 2, 3, 0}.

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

Coding Area

Language: C++17 · define a public class ETSums with a public method int findSumOfETSums(int N, vector<int> parent, vector<int> cost, int D, int seed, int MX) · 208 test cases · 2 s / 256 MB per case

Submitting as anonymous