ACM CodeFest 2.0 - RICK ON GRAPH Editorial

editorial
, , , ,
1

PROBLEM LINK:

RICK ON GRAPH | CodeChef
Author: kkdrummer

DIFFICULTY:

medium-hard

PREREQUISITES:

Bipartite Graphs , Miller-Rabin Primality Test

SOLUTION:

Consider two numbers a and b. For them to follow the two given conditions , exactly one of them must be zero and other greater than zero. Since these values(a and b) are the proper divisors of some number excluding 1 , we can say that one of the two numbers must be prime(having F(x)=0) and the other composite(having F(x)>0). Generally, if there is an edge between nodes u and v having values p and q respectively , then either p is prime and q is composite , or vice versa. Let the number of primes in array A be pn and composite be cn.

So yes, we have to colour the graph and divide the nodes into two sets such that there is no edge between two nodes belonging to the same set. Now ,if the graph is bipartite and colouring is possible let the number of type1 nodes be n1 and number of type2 nodes be n2, then if :

  1. if (pn==n1 and cn==n2) or (pn==n2 and cn==n1) :

    (i)Answer is (pn!*cn!) , if n1 \neq n2.

    (ii)Answer is 2*(pn!*cn!) , if n1== n2 ,because you can assign primes to both type1 and type2 nodes.

  2. Not possible otherwise(if the graph is not bipartite or the above condition doesn’t satisfy) . Answer is 0 in this case.

  3. Since the values in array A are very large, we will use Miller-Rabin Strong Primality test for determining the primes in array A. Here are the Resources you can refer for understanding Miller-Rabin: L26 : Miller-Rabin Primality Test | Number Theory Course - YouTube Primality tests - Competitive Programming Algorithms (cp-algorithms.com) . The sole intension of giving such high constraints was to introduce this concept to those who are already not aware about this test for checking the primality of big numbers.

Code Link: Rick On Graph Solution

1 Like