SEATR2 - Editorial

cook64
dynamic-programming
editorial
maths
medium
seatr2
tree

#1

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* += 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.size(); i++) {
		if( adj* != p ) {
			isleaf = false;
			dfs(adj*, u);
		}
	}
	if( isleaf ) {
		// leaf node base case
		for(int i=1; i<=m; i++) {
			F* = 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.size(); i++) {
				if(adj* != p) {
					v = 1LL * v * D[adj*][j]; 
				}
			}
			F[j] = v;
		}
	}

	// computing function D using function F.
	for(int i=1; i<=m; i++) {
		int j = i;
		while( j <= m ) {
			D* += F[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


#2

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

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


#4

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


#5

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


#6

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


#7

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?


#8

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


#9

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


#10

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


#11

Special Thanks for adding similar problem links :smiley:


#12

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


#13

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.


#14

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