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

primes less than 100 = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]

and product of them is so high ( > 2* 1018)

Now the main idea is just reduced to -
we have to divide above array into two parts x and y such that product of x is less than 2* 1018 and product of y is less than 2* 1018

So after lot of efforts -

X = [ 3 , 7 , 13 , 29 , 37 , 43 , 53 , 61 , 71 , 79 , 89 , 97] , product = 1971894656414957547
Y = [2, 5 , 11 ,17 , 19 , 23 ,31 , 41 ,47 ,59 ,67 ,73 ,83 ] , product = 1169214570588269810

Now we do bfs over tree and find level of all node and simple for even level node assign value “X” and for odd level nodes assign value " Y " or vice versa

Link : My solution

Ask queries in comments :slight_smile:

Drop a like if u able to understand my approach.

9 Likes

Wow, nice, that was smart!

3 Likes

I was thinking same but ,I was unable to divide prime numbers in two part every time it was overflowing.

yes , I am able to solve in last 5 minutes man , and I m saddened after seeing the solution of BOJACK (div 1 ka 4th and div2 ka 3rd ) :sleepy:

1 Like

How is it different from the editorials solution ?

1 Like

While writing I thought , editorials will come in morning , so i wrote just brief and simple solution .

3 Likes

This… How did you figure out ?

1 Like

after hell lot of combinations :man_shrugging:

Isn’t that obvious i mean just greedily divide all numbers in 2 different sets based on the parity of its index ?

That wont work.

1 Like

nope , one value give me hectic which is 97 , so to adjust it take me more time

Oh yeah! that makes sense

One can brute tho, 2^25 isn’t that slow on your LOCAL pc, then once you get the combination, it is an easy problem

2 Likes

Do we have to divide the array in a specific manner or just to ensure the product is less than 2e18?
I tried with different pair of numers and it kept giving me WA (even though the product was same as in other AC submissions).

divide prime array into two part such that product of each array is less than 2 * 10 18

Ohh Yes !!!

Thanks !!