PROBLEM LINK:
Author: Aniket Marlapalle
Tester: Harsh Shah
Editorialist: Aniket Marlapalle
DIFFICULTY:
medium
PREREQUISITES:
graphs edge-cover bipartite-graph prime-sieve
PROBLEM:
You have a set of numbers. Assign these numbers to some minimum no of pairs such that following conditions are satisfied.
- Every person gets a number.
- A number can be used any number of times.
- Sum of numbers of a pair must be a prime.
- Every number must be used at least once.
EXPLANATION:
In given problem every given number had constraints of 1<=Ai<=105. Lets first solve the problem for Ai>=2.
Algorithm:
If sum of numbers of a pair has to be a prime then it is an odd prime greater than 3. To make sum equal to an odd number we need one even and one odd number. Lets first find all the primes less than 2*105. And create a bipartite graph with even numbers on one side and odd numbers on one side. Add edge between 2 vertices if sum of their values is a prime number. Now this boils down to a standard problem of finding minimum-edge-cover in a bipartite graph
(Referhere).
The solution to this problem is maximum-matching + no of unmatched vertices (which is equivalent to V(G)-(max-matching(G)) in this case). So we can use any std max-matching algorithm to find the answer. If there is any vertex which doesn’t have any edge incident on it then it is impossible to satisfy all the conditions therefore print “-1”.
Now we need to take care of a special case of Ai=1 because 1+1=2 which is also a prime number. So in this case if there is any other number X!=1 such that (1+X) is a prime then use the above algorithm else take one pair as (1,1) and remove 1 from the list to use the above algorithm and increment the final answer by 1.
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here