July 18- Problem Discussion

U need mod Inverse there… as “retval” is moduloed…

(8/2)%7
is not equal to
((8%7)/(2%7) )%7
advice: avoid nCr method where u need division…

Refer here- Disjoint Set Union - Algorithms for Competitive Programming

1 Like

https://cp-algorithms.com/data_structures/disjoint_set_union.html#toc-tgt-11

The code given works as it is, and the explanation is pretty neat.

It does. We do not use / in mod, we find the modular inverse for that. If mod is prime like {10}^{9}+7, modular inverse of k is {k}^{mod-2}. Read Fermat’s Little Theorem for this.

So the main idea is to realize is that whenever you get a component with odd length cycle, it gets stuck.Hence every unstuck component has only cycles of even length. It can be shown that Bipartite <=> Graph with even cycles only. That’s how the problem gets reduced to maintaining a DSU of bipartite components.

1 Like

Can you provide the test case in which storing 2 edges instead of 3 will fail!

If you have something like u -- 1 -- v -- (1,2,3) -- w -- 2 -- x , then if we store only 2 then we can get a sub optimal answer. But storing 3 makes sure that it’s always possible to mitigate it

Basically if you take the log of g(z), you can eliminate the factor of ci or m.

Refer to my answer for NMNMX. Then solve the question which I gave there, i.e. 3-tower coloring. If unable to solve, look at its editorial. The answer lies there- Discover it yourself for best benefits :slight_smile:

consider test case

n=7 m=6
edges (1,2),(1,3),(1,4),(2,5),(3,6),(4,7)

root has 3 children. each children have 1 children.

size of max clique is 2 but the answer for this is 3. Even I thought of max clique but rejected it because of this example. can someone explain what’s the correct answer?

The ans for any tree is 2

like in ur case i would place a cat at node 1,so now the cat can be in {2,5},{3,6},{4,7}

Lets say it was at 2,then i could place the second cat at 2,

similarly other cases can be handled as well

Basically at each time we restrict the mouse in a subtree

@aviroop123 I see. Although I feel that my code would exceed TL in even more files if I tried this.

@vijju123 First thanks for the letting us know the new question 3-tower (atleast new for me) and I have done it. While going through your NMNMX editorial below I was not able to figure out how the total number of ways are {n-1} \choose {k-1}

Try the one at cp algorithm. :slight_smile:

My bad I didn’t know that cats can see position of jerry. Maybe they should’ve given a test case to explain that.

1 Like

You have N elements out of which you have to choose k for sequence. Say I want to count contribution of an element A_i, then it means A_i MUST be in sequence. Now I have rest of N-1 elements out of which I have to choose k-1. This is (n-1)C(k-1) by definition.

1 Like

@megatron_64 : I am not fully convinced with this answer of yours.
Your entire explanation is based on an assumption: “Lets give vector 1 a magnitude of k/2 After the we have k - k/2 = k/2 magnitude left to be divided into n vectors.”

you can see fermets little theorem for mod-1 query

I have one question here how come one reaches to the conclusion that they have to use this way to proceed for the answer. I mean what’s the intution behind the solution?