SEATR2 - Editorial

PROBLEM LINK

Practice
Contest

Panel Members

Problem Setter: Sergey Nagin
Problem Tester: Istvan Nagy
Editorialist: Sunny Aggarwal
Contest Admin: Praveen Dhinwa
Russian Translator: Sergey Nagin
Mandarin Translator: Hu Zecong
Vietnamese Translator: VNOI Team
Language Verifier: Rahul Arora

DIFFICULTY:

medium

PREREQUISITES:

Dynamic Programming, Number Theory, Trees

PROBLEM:

Given a rooted tree T consisting of N nodes and an integer M. We are asked to calculate the number of ways of putting integers from range [1, M] in each node of the tree T such that for any pair of nodes \left(A, B\right) ( where A is parent of node B ) the number assigned to node B is divisible by the number assigned to node A. Since this answer can be very large, Print the answer modulo 10^9 + 7.

QUICK EXPLANATION

Number of valid configuration (as mentioned in problem statement) for a tree rooted at a node can be computed from the valid configuration of trees rooted at its children nodes i.e number of ways of assigning a particular number say K to a node say V such that the tree rooted at node V has a valid configuration can be calculated from the number of ways of assigning multiples of number K to the children nodes of V such that trees rooted at children nodes also has a valid configuration.

EXPLANATION

Lets use some notation to make the explanation more understandable. Let us consider that the function F_{\left(V, K\right)} denotes the number of ways of assigning a number K to the node V such that tree rooted at node V has a valid configuration and the function D_{\left(V, K\right)} denotes the number of ways of assigning any multiple of number K to the node V such that tree rooted at node V has a valid configuration.

Therefore,

Required Answer = \bigg(\sum_{\substack{K \in [1, M]}}{F_{\left(1, K\right)}}\bigg) \% 10^9+7

How to compute F_{(V, K)} for all K \in [1, M] for any node V ?

As mentioned above, number of ways of assigning a particular number say K to a node say V such that the tree rooted at node V has a valid configuration can be calculated from the number of ways of assigning multiples of number K to the children nodes of V such that trees rooted at children nodes also has a valid configuration.

For any non leaf node V,

F_{\left(V, K\right)} = \prod_{\substack{U \in children(V)}}{D_{\left(U, K\right)}}

otherwise

F_{\left(V, K\right)} = 1

Note that the function F for a node V depends upon the children nodes of V.

How to compute D_{(V, K)} for all K \in [1, M] for any node V ?

Let us consider that we have already calculated F_{(V, K)} for all K \in [1, M].

Then, For some K \in [1, M]

D_{\left(V, K\right)} = \sum_{\substack{Z \in multiple(K)}}{F_{\left(V, Z\right)}}

Note that the function D for a node V depends upon the function F for the same node V and can be computed using following simple procedure.

int D[M+1];
int F[M+1];
for(int i=1; i<=M; i++) {
	int j = i;
	while( j<=M ) {  // iterating over multiples of i
		D[i] += F[j];
		j += i; 
	}
}

Look at the following C++ code for the better understanding of above explanation:


int N, M;
int F[N+1][M+1];
int D[N+1][M+1];
void dfs(int u, int p = -1) {
	bool isleaf = true;
	for(int i=1; i<adj[u].size(); i++) {
		if( adj[u][i] != p ) {
			isleaf = false;
			dfs(adj[u][i], u);
		}
	}
	if( isleaf ) {
		// leaf node base case
		for(int i=1; i<=m; i++) {
			F[u][i] = 1;
		}
	} else {
		// computing function F as per our recurrence
		for(int j=1; j<=m; j++) {
			int v = 1;
			for(int i=0; i<adj[u].size(); i++) {
				if(adj[u][i] != p) {
					v = 1LL * v * D[adj[u][i]][j]; 
				}
			}
			F[u][j] = v;
		}
	}

	// computing function D using function F.
	for(int i=1; i<=m; i++) {
		int j = i;
		while( j <= m ) {
			D[u][i] += F[u][j];
			j += i;
		}
	}
}

COMPLEXITY

O(NM\log(M)) per test case.

AUTHOR’S AND TESTER’S SOLUTIONS:

The author’s solution can be found here.
The tester’s solution can be found here.
The editorialist’s solution can be found here.

SIMILAR PROBLEMS:

Codeforces Blog Entry

Codeforces round 263 div1 - B

Codeforces Testing round 10 - D

Counting Subgraphs Cook - 63

Counter Strike Contest Codechef

Hackerrank Hack 101

Dynamic Programming on Trees Article

5 Likes

Que.1 How is O(N M log(M)) supposed to pass ?

  N * M * log(M) = 500 * 20000 * log(20000) = 500 * 20000 * 14 = 14 * 10^7
  

  and there were t = 10 test cases which means total complexity = 10 * 14 * 10^7 = 14 * 10^8 = 14 sec, but time limit was 5 sec.

Que.2 Some O(N M log(M)) solutions have had TLE. For example, see my last submission. Was there some trick involved ?

3 Likes

This is my first experience of writing editorials for Codechef. Please provide your suggestions to make them better.

The call to memset() in each test case may be leading to TLE. Also, try to replace modulo with subtractions wherever possible.

Kindly check my solution for this. I used the same approach + Fast I/O. Still got TLE.

Special Thanks for adding similar problem links :smiley:

I used the same approach with simply scanf/printf and it got passed within TL.

My completely recursive code gave TLE then partial recursive and partial iterative gave AC . the constraints should have been less.

nm logm should not. I optimised to make it exactly nm

Did everything possible, still TLE. Constraints are too tight. Though I am still wondering if O(N M log(M)) will pass within 5 sec if extreme input is provided.

1 Like

Please have a look at editorialist solution. It makes use of recursion and still passes all test data in less than 4 sec.

My answer during the contest was broadly inline with the editorial. Marked as AC in 4.29 seconds, which was a little lucky.

With a few simple optimisation steps

  • Don’t calculate remainers %mod unless necessary
  • Remove C++ vector range checking
  • For leaf nodes, optimise the calculation using F(V,k)=1, and D(V,k)=M/k
  • When there is just one child node C of a node V, then F(C,k) = D(V,k)

then run time reduces to 1.19 seconds.

However, I’m beginning to believe that each D(V,k) only ever takes about 2\sqrt M values as K runs from 1 to M, so the problem can be solved much faster. See ACRush solution in 0.62 seconds. Can anyone provide the explanation?

nice editorial, exactly as i thought… but explained in very much detail and lot of mathematical notations… :stuck_out_tongue:

Can anybody help me with TLE : https://www.codechef.com/viewsolution/10161257

//