How to solve pathetic-products problem from July-Cookoff 2020 ?

Question

Link to problem : https://www.codechef.com/COOK120A/problems/PATHETIC

Answer 1

 

We will use the fact that each integer has a prime decomposition. We only need to consider prime numbers. We need to make sure that for any prime pp that any path with pp nodes containss at least one value that is divisible by pp. We will assign these nodes that are divisble by pp using a depth first search. We initialize all values as 1. If the distance from the root is a multiple of p/2p/2 we will multiply the value of that node by pp. We don’t do this for the root as otherwise it would become too large. The p/2p/2 is needed to take branches into account, see the sketch below as an example

p=3
        O-#
       /
O-O-#-O
       \
        O-#

The left node is the root. O is a root that is not multiplied by pp, # is a node that is. We notice that by spacing the depths by 3 we have accidentally created a path of length 3 that contains no multiples of pp. Using p/2p/2 as the depth interval solves this problem