PATHETIC - Editorial

editorial
, , , , , ,
33

In the constraints
1≤N≤100 ,
so its bit convenient to select 0 as the root;
with no interference of N

34

Can anyone explain this?
Why assigning depths to particular node from any leaf node would not work?

35

What if i allot every node value of n! and print it.
For calculating factorial of large numbers like 100 you can refer to Find the Factorial of a large number - GeeksforGeeks

36

But 100! is greater than the constraint for each node value.

1 Like
37

amazing problem!!!

38

Suppose the following case

        O-#
       /
R-O-#-O
       \
        O-#

The #'s are at depths 3 and 6 and therefore the only ones that are divisible by 3. Now notice that that at the branch there is a sequence of 3 O’s who’se product is not divisible by 3

1 Like
39

Okay…i see. :+1:

40

The logic is totally correct bhai
just those authors constraint will meddle around.

but theres no loophole in your logic,

1 Like
41

And what if we repeat the process for every leaf node?

42

Then I think the values could become too large. But please try it as I’m not entirely sure.

43

It doesn’t matter. Take any node as “root”. Try on pen-paper taking other root than “0” (0-indexing) or “1” (1-indexing). You will get a valid solution.

1 Like
44

This indeed works, the maximum sequence of nodes that is not divisible by p would be p-2 which satisfies the conditions. I am curious if the setter (@sjshohag ) was not aware of this solution, as it would imply that N could be increased to around 10^7.

45

How to choose p1 and p2 anyone? I tried adding alternate primes in each set but it exceeds 2e18

46

@rajarshi_basu This should be explained in the editorial. Both the setter and tester use a “greedy” approach that might not be entirely obvious

3 Likes
47

can you please explain your logic…on what basis you are assigning the values
Thanks in advance…

48

How did you make these products? What are the primes of p1? Thanks in advance.

49

This is how rds_98’s solution works

We assign each node a value based on it’s distance from a root node.
Because of this case we need to make sure that roughly every p/2 levels of depth will have a value divisble by p (where p prime). The formula (2d)(2d+1) will satisfy this condition.

Suppose p divides 2d(2d+1). Then p divides 2d or p divides 2d+1. This can be rewritten as np = 2d or np=2d+1. With some rewriting we then get d=n\frac p2 or d=n\frac p2 -\frac12. From this we can see that every p/2 depths will be divisble by p.

In particular the maximum depth difference between nodes that are divisible by p will be \frac {p+1}2 which ensures that the maximum path of nodes not divisible by p will be p-2

2 Likes
50

I specifically left that part out for readers to think on it. It’s not hard at all to figure out a way (or even hardcode it), but will maybe make newbies think a bit. IMO good editorials should keep some parts of the problem for the reader to put a bit of thought into.

2 Likes
52

@rajarshi_basu please explain me that the two values p1=1816798556036292277
p2=1269027849171992910 which we get after some precomputation, the product of these two numbers is not divisible by 4,8,16,64,9,27,81,25,49 so how the solution is valid if |S| takes these values. It would be very helpful if you can please explain it to me! :slightly_smiling_face:

53

I had the same thing in mind. So I used another approach . I thought of assigning every value x to every x-th node. So for eg. Every 3rd node will have a value of
node_val *=3. So now if we consider any simple path of length 3 , we have the product to be divisible by 3.But I am still getting a WA. Can someone tell me what is wrong in my logic .
Link.