Max-Flow and Maths.
You are given two arrays denoted by A1,A2…AN and B1,B2…BN.
Let us maintain two sets S1 and S2 which are empty initially. In one move , pick a pair of indexes (i, j) such that it’s already not present in S1. Also, Bj > Ai and GCD(Ai,Bj) is not 1. Further,pick another pair of indices (p, q) such that it’s already not present in S2. Also, Bp < Aq and GCD(Aq,Bp) is not 1. Also, GCD(Aq,Bp) should not be coprime to GCD(Ai,Bj). Then add both pair of indices to S1 and S2, respectively.
Find the largest number of moves that can be performed?
Let us first find (i,j) pairs which satisfy the property that they are unique [ i.e. (i,j) is considered once ] and Bj > Ai and GCD(Ai,Bj) is not 1. Let us store gcd of each pair in vector U.
Let us now find (p,q) pairs which satisfy the property that they are unique [ i.e. (p,q) is considered once ] and Bp < Aq and GCD(Aq,Bp) is not 1. Let us store gcd of each pair in vector V.
You would have realized that we are not interested in the pair (i,j) but we are interested in their gcd.
So , we are given 2 arrays U and V , we need to find pairs ( U[x] , V[y] ) , such that GCD ( U[x] , V[y] ) is not 1 and x is choosen atmost once and similarly y is choosen atmost once. Our target is to maximise such pairs.
The above stated problem is indeed we need to solve. The condition “x is choosen atmost once” ensures that pair (i,j) is not repeated , and similarly for y. The condition “GCD ( U[x] , V[y] ) is not 1” ensures " GCD(Aq,Bp) should not be coprime to GCD(Ai,Bj)" is fulfilled.
This is a classical max-flow problem.Consider the nodes as (U + V + source + sink) and consider adding edges from source to each index of U with capacity 1 ,add edges from x to y if gcd of U[x] and V[y] is not 1 , and edges from each index of V to sink with capacity 1.
Calculating max-flow of this graph will give us the solution.
But Wait we are not done with the solution!
The Above solution is sure to get time out.
Size of the vector U in the worst case will be 400 * 400 , and the size of the vector V in worst case will be 400 * 400. So total number of edges between U and V can go upto 400 * 400 * 400 * 400 , which is too high.
I will urge readers to read the problem statement once again and make a small observation which will be the key to solve the problem.
Can we do some observation on the line “add an edge from x to y if gcd of U[x] and V[y] is not 1” ? .
Our only aim is to ensure that the gcd is not 1 , so we can introduce some dummy vertex , which will denote prime factor of some number from the array U or V.
What will be the bound on such vertices ?
Such vertices are bounded by 9* ( sizeof(U) + sizeof(V) ). You can quickly realise that the maximum prime factor a number <= 1e9 is 9 ( Reason : 2 * 3 * 5 * 7 * 11 * 13 * 17 * 19 * 23 * 29 > 1e9 ).
How will one use such vertices to fullfill the aim of the problem ?
Let’s consider the graph ( Nodes , Edges ) where Nodes = U + V + source + sink + dummy vertices , and Edges = E1 + E2 + E3 + E4
E1 : Edges from source to each index of U with capacity 1 [ same as described above ]
E2 : Edges from each index of V to sink with capacity 1 [ same as described above ]
E3 : Edges from index x of vector U to those dummy vertices which divides U[x] with Infinite capacity.
E4 : Edges from those dummy vertices to index x of vector V , which dividex V[x] with Infinite capacity .
Number of Edges in this graph <= 400 * 400 + 9 * 400 * 400 + 9 * 400 * 400 + 400 * 400
Number of Nodes in this graph <= 1 + 400 * 400 + 9 * 400 * 400 + 9 * 400 * 400 + 400 * 400 + 1
You need to proof that the max-flow in this graph is indeed same as the max-flow in the previous graph.