You are not logged in. Please login at www.codechef.com to post your questions!

×

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

asked 17 Nov '15, 03:08

ma5termind's gravatar image

3★ma5termind
1.7k11630
accept rate: 11%

edited 09 Feb '16, 16:07

admin's gravatar image

0★admin ♦♦
19.7k350498541

Special Thanks for adding similar problem links :D

(23 Nov '15, 00:31) vsp46★

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 ?

link
This answer is marked "community wiki".

answered 23 Nov '15, 00:11

m_17's gravatar image

6★m_17
5616
accept rate: 0%

edited 23 Nov '15, 00:19

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

(23 Nov '15, 00:29) sanchit_h6★
1

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.

(23 Nov '15, 01:16) m_176★

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

link

answered 23 Nov '15, 00:16

ma5termind's gravatar image

3★ma5termind
1.7k11630
accept rate: 11%

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

link

answered 23 Nov '15, 00:31

priyanshu2501's gravatar image

4★priyanshu2501
9115
accept rate: 0%

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

link

answered 23 Nov '15, 00:36

ma5termind's gravatar image

3★ma5termind
1.7k11630
accept rate: 11%

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

(23 Nov '15, 00:41) kevind1★

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

link

answered 23 Nov '15, 00:41

rajat1603's gravatar image

7★rajat1603
1.0k113
accept rate: 4%

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

(23 Nov '15, 03:17) ma5termind3★

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?

link

answered 23 Nov '15, 05:42

john_smith_3's gravatar image

5★john_smith_3
57517
accept rate: 27%

edited 23 Nov '15, 05:43

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

link

answered 22 Jan '16, 22:08

rohanagarwal's gravatar image

5★rohanagarwal
1009
accept rate: 5%

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

link

answered 26 May '16, 12:04

apptica's gravatar image

5★apptica
939210
accept rate: 17%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×15,497
×2,559
×2,093
×1,176
×699
×95
×3

question asked: 17 Nov '15, 03:08

question was seen: 3,673 times

last updated: 26 May '16, 12:04