# SEATR2 - Editorial

#1

### 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

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;
}
}
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…

#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

#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.