Given an array of n positive integers a[1], a[2], ..., a[n] and m good pairs of integers (i1, j1), (i2, j2), ..., (im, jm) where 1 ≤ ik < jk ≤ n ,
n<=100 & m<=100
EDIT: Each good pair (ik, jk) meets the following conditions: ik + jk is an odd number and 1 ≤ ik < jk ≤ n.
In one operation you can perform a sequence of actions: Take one of the good pairs (ik, jk) and some integer v (v > 1), which divides both numbers a[ik] and a[jk] and divide both numbers by v.
Determine the maximum number of operations you can sequentially perform on the given array. Note that one pair may be used several times in the described operations.
My approach :
I began by first prime-factorizing each number of the array.
Given one good-pair (ik,jk) we can divide both numbers A[ik] and A[jk] by their common prime powers i.e if A[ik]=2^5 * 3^4 and A[jk]=2^3 * 3^7 then we can divid both of them by 2 a total of 3 times and divide by 3 a total number of 4 times. The number of operations increase by the minimum of the common prime powers i.e by 7.
Total number of operations can then be taken as the sum over all common prime powers for all good pair given.
However my code fails for the following test case:
N=10
M=9
A[]=67108864 8 2 131072 268435456 256 16384 128 8 128
Good Pairs :
4 9
5 10
6 9
9 10
1 4
3 8
8 9
1 2
4 5
The array has each element as a different power of 2.
In terms of power of 2, array can be written as :
B[]= 26 3 1 17 28 8 14 7 3 7 //A[i] = 2^B[i]
Selecting each good pair and subtracting the common power of 2 , my answer progresses for each good pair as :
26 3 1 14 28 8 14 7 0 7 ans 3
26 3 1 14 21 8 14 7 0 0 ans 10
26 3 1 14 21 8 14 7 0 0 ans 10
26 3 1 14 21 8 14 7 0 0 ans 10
12 3 1 0 21 8 14 7 0 0 ans 24
12 3 0 0 21 8 14 6 0 0 ans 25
12 3 0 0 21 8 14 6 0 0 ans 25
9 0 0 0 21 8 14 6 0 0 ans 28
9 0 0 0 21 8 14 6 0 0 ans 28
Processing each good pair, my code gives the answer as 28.
However the correct answer is 31. I need help in understanding how the output came to be 31 and the approach to solve this question.
PS: The problem is problem E of codeforces Div2 Round 284.
Link to the problem: http://codeforces.com/contest/499/problem/E
This problem can be solved by finding a maximum matching in the following graph. For each array value x, for each prime factor of x with multiplicity, make a new vertex. If x = 12, for example, then we create two 2 vertices and one 3 vertex. Make edges between pairs of vertices that correspond to the same prime factor of array values forming a good pair. For example, on the input
A B C # array indexes
8 12 18 # array
A B # good pairs
B C,
the graph has vertices
{A2a, A2b, A2c, B2a, B2b, B3, C2, C3a, C3b}
and edges
{{A2a, B2a}, {A2a, B2b}, {A2b, B2a}, {A2b, B2b}, {A2c, B2a}, {A2c, B2b},
{B2a, C2}, {B2b, C2},
{B3, C3a}, {B3, C3b}}.
The meaning of taking the edge {A2c, B2a}, for example, is that we divide the array entries labeled A and B by 2. The order of operations does not matter.
Now, there are algorithms for finding a maximum general matching, but they're complicated, and I was surprised that a programming contest would feature them. As it turns out, you've left out an important constraint, namely, that the good pairs sum to odd numbers, which guarantees that the graph will be bipartite and hence amenable to simpler algorithms. Depending on what the instances look like, it may be profitable also to switch from bipartite matching to maximum flow, which allows, for example, the five vertices and six edges for the 2 factors of A and B to be replaced by two vertices and one edge with three units of capacity.