PATHETIC - Editorial

[machone]

@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!

[yashx]

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.

[anon42270878]

Yeah

[ssrivastava990]

Nope u did wrong man , if u wanna divide it by 4 what it means , it means there is a path whose length is 4 right?

consider this graph-

           1
        /  | \
       2   3  4
               \
                5

now assign values to nodes for even level assign P1 and for odd level assign p2

consider path from 2 to 5 ie . 2 -> 1- > 4 - > 5 (length is 4 ) u can check now product of all nodes is divisible by 4 .

Hope u understand.

[ssrivastava990]

and what if path length is 37 ?

[ssrivastava990]

PATHETIC - Unoffical editorial (July cookoff 2020 )

Question - Div1 Div2 Link : My solution We want to assign values to node in such a way the product of all nodes is always divisible by the path length, but how we can do it? Let think in term of prime suppose a path has prime length (lets take 7) now the product of all node is divisible by 7 (prime) , means there is any node which is multiple of 7 . One can think ( I also think ) we can assign a node 2 and for remaining node all prime number products less than 100 , but it will be wrong as …

@sumit_saraff

[yashx]

So one of every 37 nodes will have a value that will be a multiple of 37.
Input

2
6
1 2
2 3
1 4
5 1
6 5
2
1 2

Output

1 2 3 24 30 6
1 2

As u can see one of every 5th node has a multiple of 5, One of every 6th node has a multiple of 6 and so on!!

[ssrivastava990]

isn’t it will overflow ?

lets take a graph like this
1-2-3-4-5-6-7-8-9-------97 ?
now what’s your answer ?

[sumit_saraff]

how did you divided prime numbers to get these two p1 and p2?

[sumit_saraff]

thanks

[anirudh_achal]

I did the same and got AC. Was this approach not intended to get accepted?
[My submission] (CodeChef: Practical coding for everyone)

[akashbhalotia]

Going backwards works. Iterate from 100 to 1, and each time multiply the prime to the smaller value of p1 and p2.

[prabhu04]

@abc1233 CodeChef: Practical coding for everyone
Can u pls check this soln, I’ve used dfs instead but getting WA

[jai_dewani]

Daam! just need the 4th observation for a conclusive AC.
Interesting question and amazing editorial!!

[ssrivastava990]

shit man I have to try backward, it will save so much of time

[abc1233]

You are right your solution is absolutely right , algorithm is same. Just the mistake you did is that the vertex value/colour was to be printed in order from 1 to N.
That is you have to put values in order of vertices. 1 2 3 …N vertices.

DFs you may start from vertex. 1 but suppose instead of vertex 2 , vertex 3 was adjacent to vertex 1 . Thus the values printed are not in sequential order of 1 to N. In your solution. Just order the colour and print it later to solve the bug.

[prabhu04]

Thanq so much for the quick reply

[rajarshi_basu]

See Observation 5

[sjshohag]

I actually like a constructive problem if it can be solved in multiple ways because not everyone thinks in the same way. You may notice that this contest have 3 constructive problems and all of them have multiple solutions.

[sid9406]

What’s the problem with this approach : For all nodes , calculate distance from all the leaf nodes to this node then the node value is simply the lcm of all these distances .
code : CodeChef: Practical coding for everyone