CHEFDIV - Editorial

PROBLEM LINK

Practice
Contest

DIFFICULTY

easy

PREREQUISITES

number theory, prime factorization, segmented sieve

PROBLEM

A divisor tree with value at root N is defined as follows. For each node of the tree, the values at the child nodes will be the proper divisors of x (i.e. divisors except x). The weight of a path in this tree is defined as the sum of degrees of all the nodes in the path. The weight of a tree will be the maximum score of path starting at root.

// Add an example.

You are given two integers A, B. You have to find the sum of weights of all the trees with the values at their root node being in the range A to B, both inclusive.

Finding weight of a divisor tree with value at root N.

As follows from the definition that the number of children of root node will be equal to the number of proper divisors of N. Let us understand the concept of number of divisors of N by taking some examples.

If N is prime, then its only proper divisor will be the number 1. Hence, the tree with value at root N will have only two nodes in it - the root node with value N and the only child node with value 1. The weight for this tree will be equal to 2 (1 (degree of the root node) + 1 (and the node with value 1)).

Except the root node, the degree of each node will be the number of proper divisors of the value at that node (the children) plus one (the parent node). This will be equal to number of all the divisors (including the non-proper divisor too). Hence, the degree at each node (except) is equal to total number of divisors of the value at the node. For sake of simplification, we can assume that this holds true for the root node too. This simplification will make our analysis easier, the only difference being the weight of path will be one more than the actual weight.

The number of divisors of a number N can be calculated by finding its prime factorisation. It is easy to see that for a number N with prime factorization {p_1}^{q_1} \cdot {p_2}^{q_2} \dots {p_k}^{q_k}, the number of divisors will be (q_1 + 1) \cdot (q_2 + 1) \dots {q_k + 1}. Note that the number of divisors depend on the exponent of prime factors (i.e. q_i's), not on their actual values (i.e. p_i's).

Greedy Algorithm

The simplest greedy strategy that comes to our mind could be following. We start with the root node. From the root node, we go to the child node which has maximum degree, and then from that node to its child with maximum degree and so on till we reach a leaf node (a node with value 1 at it).

path = {}
node = root;
while (node is not 1): 
    path.add(node):
    node = child node with the maximum degree
path.add(1);
// path will denote the path with maximum weight.

Proof Of Correctness
Let us first define level of a node. The level of a node denotes its distance from the root node. Thus the level of the root node is 0 and that of its children node will be 1, and that of their children nodes will be 2, and so on.

Number of levels in the tree will be q_1 + q_2 + \dots + q_k, as in the longest path from root to a leaf, we will decrease the one of the exponents q_i by 1.

Claim: The degree of a node in the path choosen by the above greedy algorithm will be greater than or equal to the degree of any other node in the same level.
Proof #1: Assume we are level L. Let v denote the node in the path choosen by the greedy algorithm, and let d(L) denote its degree. Let x be vaulue at any other node in the level L. As disussed before, the sum of exponents in prime factorization of x should be decreased by at least L. We want to find the maximum possible degree of x can have. The exponents in the prime factorization of x will be a_1, a_2, \dots a_k, such that a_i \leq q_i, and a_1 + a_2 + \dots + a_k \leq q_1 + q_2 + \dots + q_k - L. Then maximum possible degree of x will be given (a_1 + 1) \cdot (a_2 + 1) \dots (a_k + 1).


Another Proof of greedy algorithm:
Let the degree of root node be D. When we decrease q_i by 1 in the exponent, the degree of the node will be \frac{D}{(q_i + 1)} \cdot q_i, i.e. the degree of node gets multiplied by \frac{q_i}{(q_i + 1)}. The degree of its child will be multiplied by \frac{q_i - 1}{(q_i)}. So, there will be total q_1 + q_2 + \dots + q_k such terms.

Sum of these terms will be D + D \cdot \frac{q_i}{(q_i + 1)} \, + \, D \cdot \frac{q_i}{(q_i + 1)} \cdot \frac{q_i - 1}{(q_i)} + \, D \cdot \frac{q_i}{(q_i + 1)} \cdot \frac{q_i - 1}{(q_i)} \cdot \frac{q_j}{(q_j + 1)} and so on.

So, the multiplicatands will be of form

\frac{1}{2}, \frac{2}{3}, \dots, \frac{q_1}{q_1 + 1}, \frac{1}{2}, \frac{2}{3}, \dots, \frac{q_2}{q_2 + 1}, \, \dots \, \frac{1}{2}, \frac{2}{3}, \dots, \frac{q_k}{q_k + 1}

We have to find the right order of multiplication of these terms such that sum of the above mentioned term is maximized. You can see that the sum will be maximum when you multiply the D value by as large fractions in the beginning as possible, i.e. multiply by \frac{x}{x + 1} such that x is as large as possible.

For a node with value N, find child with maximum degree.

As defined earlier, (q_1, q_2, \dots q_k) denote the exponents in the prime factorization of N. We want to find the number d that divides N and has highest number of divisors. What should be the exponents in prime factorization of d? One can see that the general form of d can be given by
{p_1}^{a_1} \cdot {p_2}^{a_2} \dots {p_k}^{a_k}, such that a_i \leq q_i for each 1 \leq i \leq k. The number of divisors of d will be given by (a_1 + 1) \cdot (a_2 + 1) \dots (a_k + 1). The number d should have some i such that a_i \neq q_i. Infact, there should be only one such i and q_i - a_i = 1, and q_i should be the largest among q_1, q_2, \dots q_k. You can prove this easily by contradiction.

We can take examples to understand this. Let N = 2^2 \cdot 5^3. Its exponents are (2, 3). Number of its divisors is (2 + 1) * (3 + 1) = 3 * 4 = 12. We have to find its divisor d that has the highest number of divisors? We can pick one of the exponents and subtact 1 from it, and the corresponding number will be a proper divisor of N. For example, in this case, the divisor could be either 2^1 * 5^3 or 2^2 * 5^2. As (1 + 1) * (3 + 1) = 4 and (2 + 1) * (2 + 1) = 9. You can see that 2^2 * 5^2 has more divisors than 2^1 * 5^3. You can prove that you should remove 1 from the highest exponent to get the number d with highest divisors. Let the number N = p^a \cdot q^b. Assume a < b. You can see that (a + 1) \cdot b is greater than a \cdot (b + 1), as the first term is ab + b, and the second ab + a (because b > a). You can extend this observation for more than two exponents.

Implementation of finding weight of a tree.

Let us implement the code for finding weight of a tree with root value N. We find the exponents in the prime factorization of N. Let these exponents be q_1, q_2, \dots q_k. Let s = q_1, q_2, \dots q_k. For s iterations, in each iteration we pick the largest q_i and decrease it by 1, and add the number of divisors for the given exponents in the weight of the path. If we implement this naively, i.e. in each iteration we find the maximum q_i by iterating over all the k q_i's, the time complexity will be \mathcal{O}(s * k).

We can optimize this by using a max heap (priority queue) to store the q values, and finding the top element in \mathcal{O}(log k). The time complexity of this implementation will be \mathcal{O}(s * log(k)).

For a given number N, we can find bounds over s and k in terms of N. With little obseration, you can prove that both k and s will be \mathcal{O}(log(N)). It is left as an exercise for the readers.

Finding prime factorization of numbers in a given range

Given a range of integers [A, B], we have to find prime factorization of each number N in the range [A, B]. We can factorize a number N in \mathcal{O}(sqrt N) time by trying all possible divisors \leq sqrt(N). This will provide a time complexity of \mathcal{O}(|B - A + 1| \cdot sqrt B) in the worst case. This will be sufficient to solve first and third subtasks.

You can using sieve of Eratosthenes to find prime factorization of from 1 to N in time and space equal to \mathcal{O}(N log N). This will be sufficient to solve the second subtask.

A and B can go up to 10^12 in the final subtask, and |B - A| \leq 10^5. We can see that though A and B are large, their difference is not that much. We can use this observation to use segmented sieve algorithm for finding the prime factorisation in \mathcal{sqrt(B) log (B) + |B - A|} time. This was sufficient to solve the full subtask. You can learn about segmented sieve from this stackoverflow answer.

SETTER’S SOLUTION

Will be uploaded soon.

TESTER’S SOLUTION

Can be found here.

5 Likes

@samdcoder Set container won’t keep multiple copies of the same qi’s. You will lose out in case you have multiple qi’s of the same value.

Edit: The question was edited, from ‘set’ to ‘multiset’.

Yes, multiset can be used for this purpose, by iterating from the end of the container each time (assuming sorted in increasing order). But won’t a priority queue come to your mind more intuitively?

2 Likes

Here is the solution of above illustration with more optimisation in Sieve and weight of tree.

1 Like

I still cant understand how to find prime factorization of a big numbers segment, can anyone try to explain it once again?

Can’t see the solutions of tester and setter.

@korec123 You can use the same approach that we use for finding primes using Sieve of Eratosthenes. You need to find prime factors of numbers in the range of A to B. First generate primes using Sieve of Eratosthenes till 106, now we can use these primes to find factors of numbers in the range of A to B. Notice we need to generate primes only till 106 because B <= 10**12. So for each prime, you generated, mark off all the multiples of that prime, i.e. for a prime number p, we mark off all the multiples of p in the range A to B, and for every such multiple of p, we find the number of times p divides the number and store that value. For example, for p = 2, A = 10, B = 20, we start with 10 (value of A), and divide 10 by p (2) until it’s possible. We do this for 12, 14, 16 and so on until B. we repeat this for all the primes pi, such that pi * pi <= B. Hope this helps.

for CHEVDIv problem when finding divisor having max degree can we do

No/(first divisor of no more than 1) = p;

p will always have highest degree among child nodes

example :
no = 12
first divisor other than 1 is 2

12/2 = 6

6 has max degree among leaf nodes

is this approach correct??

Hi Everyone!

I made a video editorial on this problem over here:

Chef And Divisors

alt text

Will be adding more editorials soon!

Cheers :slight_smile:

9 Likes

Thanks for this

1 Like

Hi @korec123 you can use the links mentioned below for better understanding.

Hope it helps.

for CHEVDIv problem when finding divisor having max degree can we do

No/(first divisor of no more than 1) = p;

p will always have highest degree among child nodes

example : no = 12 first divisor other than 1 is 2

12/2 = 6

6 has max degree among leaf nodes

i know i have to use segmented seive instead of seive i only want to know

is this approach of finding divisor with highest degree correct??

if not can u provide a counter example??

here is link to my code with above mentioned approach

https://www.codechef.com/viewsolution/13348793

Hi @chunky_2808 just consider the case of 2^2 * 3^3 = 108. Your logic would give the answer 108 / 2 = 54 but the no with max proper divisor would be 2^2 * 3^(3-1) = 36. Hope you understand.

1 Like

Can someone explain, please. Why in accepted solutions answer for input: 18 18 => 12 ?
I’m getting 11.

@wigor: For 18 18 The only number is 18. 18 can be written as 2^1 * 3^2. Therefore the no of divisors of 18 are (1+1) * (2+1) = 6. Now the proper divisor of 18 with maximum factors is (2^1) * (3 ^ 1) = 6. The no of divisors of 6 are (1+1) * (1+1) = 4. Now the proper divisor of 6 with maximum factors is (2^1) or (3^1) i.e. either 2 or 3. The no of divisors of 2 or 3 is (1+1) = 2. Therefore answer should be 6 + 4 + 2 = 12 not 11.

Other way of explaining:(No of proper divisor of root + degree of nodes upto leaf node).
Here 5 for root(18) + 4 for child with max factors(6) + 2 for child with max factors(2 or 3) + 1 for leaf node 1 = 12.
Hope you understand it. Please upvote if you query is answered.

2 Likes

my code for segmented sieve for those who are getting confused in this part :

1 Like

@coder26548

Now the proper divisor of 18 with maximum factors is (2^1) * (3 ^ 1) = 6

Now I see my mistake - maximum factors instead of maximum divisor :slight_smile:

@coder26548 Thank you. Sorry, I can’t upvote - too few reputation points.

Hi sorry for posting my question here
I have not enough karma cuase I joined this web site right now.
I have a problem with c:i compiled this and get null include <stdio.h> int main (void){ char x; x=='hi'; printf ("%s",x); return 0; }

Thank you

Sorry for my English.

Can someone please explain that in the Tester’s Solution,
How Do we Find The first index for marking the primefactor in Segment sieve
*Particularly I have doubt in the working of [divCeil(low,i)i] where divCeil is (return(a+b-1)/b;)

I have Convinced myself about its working but I wanted to know the exact reason & explanation.It will be great if someone can explain both the use of divCeil and also divCeil(low,i)*i (for deciding the index)

can we store the values in a C++ multiset instead of priority queue and get maximum qi each time?