Problem Link
Author: Alexandru Valeanu
Tester: Hasan Jaddouh
Editorialist: Bhuvnesh Jain
Difficulty
HARD
Prerequisites
Centroid Decomposition(Divide & Conquer), Prime Sieve, Hashing
Problem
You are given a tree consisting of N nodes, each having a number written on it. You are required to find the path with maximum number of nodes in it such that product of numbers written on the nodes in the path is a perfect cube i.e \prod_{x \in path(u, v)} value[x] = {k}^{3}, for some integer k.
Explanation
Subtask - 1
In this subtask, N = 10. We also notice that the product of all number in worst case can be {50}^{10} ~ {10}^{17}, which easily can be stored in programming languages. Thus we can iterate over all paths, find the product of the number in naive way and just check whether the number is a cube or not.
Pseudo code in C++ (for checking whether number is perfect cube or not):
long long x = (long long)round(cbrt(num));
return (num == x * x * x)
The complexity of this case would be O(N^2) which is too slow for last 2 subtask. But for second subtask, the method of checking cubes should be optimised as product of numbers can be very large to be stored in data types present in C++/Java.
Subtask - 2
The approach is similar to above, just we will find some other way of checking whether product of numbers is cube or not. The technique used below would be helpful for full solution as well.
A number is said to be a cubic number iff the exponent of all its prime divisors are multiple of 3. Thus, instead of storing the number itself we store the prime decomposition of the number. Also, to efficiently calculate the prime decomposition of a number in O(\log n) after modifying prime sieve, one can refer to this tutorial on codeforces.
Also, one more trick which one can use here is that we should store the exponent of primes modulo 3 only. Storing the exact exponent is not required. This optimisation may not be useful for this subtask, but is used in the full solution of the problem.
The above can be easily implemented using N DFS calls staring from each vertex and using prime factorisation of the number. The editorialist code for it can be found below.
The complexity of this approach is O(N^2 \log{VALUE}).
Subtask - 3 and 4
For cracking the full solution of the problem, it is required you know about Divide and Conquer on tree, also known as Centroid Decomposition. If you don’t know about it, you can read it from here.
In short let us first list down the major parts in Centroid Decomposition:
- Decompose the Tree into centroid Tree such that each subtree size is less than half the number of nodes below that node.
- Find the answer to all the nodes below the every centroid.
- Store some important information, which can be used to efficiently recover answer for path between 2 nodes which lie in different subtrees on the centroid.
The first part in the solution is fairly easy after you have gone through the above tutorial. The second part is similar to the approach used in above subtask, i.e. using prime decomposition of numbers.
Now let us consider when we traverse from centroid, X, to a node, Y, below it we have the prime decomposition of the product of numbers as Q = {p_1}^{a_1} * {p_2}^{a_2} \dots {p_m}^{a_m}. Now to find whether there exist some other node, Z, in the other subtree of the centroid, such that product of number is a cube, we need to check whether product of numbers from X to Z is Q' = {p_1}^{3-a_1} * {p_2}^{3-a_2} \dots {p_m}^{3-a_m}.
To implement the above approach, we can easily use hashing to store the possible products and also compute complement (i.e Q') and just check whether the complement is present in the hash table or not.
For example : Let us assume our centroid tree is
The number written on some of the nodes are what we are going to examine. The number (in compressed form where each exponent of prime is reduced modulo 3) will be as follows :
C_2 = {2}^{1} * {5}^{1}, C_4 = {2}^{2} * {5}^{1}, C_6 = {2}^{1}, C_{11} = {2}^{2} * {5}^{1}
See in C6, prime 3 was ignored in factorisation.
If we take the product of path C_4 to C_{11}, we see that it will give a cubic number. To check cases like this, we simply store the product of C_2 to C_4 into our hash table and also the product C_2 to C_{11} in our hash table. Now since, the product of hash value of C_2 to C_4 is complement of C_6 to C_{11} (we removed C_2 to make sure it is accounted in product only once), we should update our answer.
For more details, you can refer to the author and tester’s implementation below.
Time Complexity
O(N \log{N} \log{VALUE}), assuming all hashes are O(1).
O(VALUE \log{\log{VALUE}}) for precomputing the prime sieve.
Solution Links
Setter’s solution
Tester’s solution
Editorialist solution - For Subtask 1 & 2