Problem : You are given an array of integers, anytime you can pick two numbers from it and divide them both by some common factor of them. Your goal is to find the minimal possible product of the numbers of an array after performing a number of such operations.
Explanation :
Let’s decompose each number into the product of primes, that is, let’s find it’s factorisation.
We know that Ai is not greater than 109. So, if there is a prime factor that is greater than, say 40000 (virtually, greater than the square root of 109), it will appear only once in the decomposition. So, each prime number greater than 40000 will appear in the final product of the array elements no more than once. Each number from the array may or may not have this prime factor in its prime decomposition but if it has, this prime factor will appear only once in this number’s decomposition. So, for each prime divisor greater than 40000 if it appears in the even number of the array elements, then it is possible to split the numbers that have this divisor into pairs and to get rid of it completely. If it appears in the odd number of the array elements, then we can pair up all but one numbers that have this factor in their prime decomposition. So, it will appear once in the final product in the array elements.
For the rest of prime numbers, that is, those that are smaller than 40000, we can solve the problem separately, and the solution here is a greedy one:
For each prime factor let’s write out the list of occurences in every array element.
Then, delete all zeroes from this list.
Anytime we will pick two maximal numbers from the list and decrease them by one. That corresponds to divising some two numbers for this prime factor.
If after the desreasing some elements became zeroes, we just throw them away.
When there remains only one number (nonzero one), we stop our algo.
In order to pick two maximal numbers and to change them we can use the STL priority queue. But there is also an alternative to store something like the amount of every list’s number occurences in the array, like Amount[X] the number of X’s in the list. That makes the implementation easier for Pascal coders.
can someone tell me what is wrong with my code ?. i was submitting it for the smaller part but was getting WA on the last case …plz tell me what is wrong
Here is the proof that I did while setting the problem, just for the part why the greedy step is correct. It might wave a little away from the editorial’s context; any suggestions are welcome.
First of all we can treat each prime separately. So prime factorize the numbers and treat the prime powers individually.
For powers of a prime P, we take the largest two, divide by P and insert it back to the list. Proof that this greedy step is correct :
Consider an optimal solution, which is a list of pairs of indices, such that if ith element of the list is (a_i, b_i) that means the ith operation was to divide A[a_i] and A[b_i] by P. It is easy to see that division by higher powers of P can be reduced to multiple elements in the list (division by P^2 can be converted to two divisions by P).
Also note that the list is permutable, the operation in the list can be performed in any order, the product would still be the same.
Let l1 and l2 be the indices of the largest two powers of P. We have to show that there is an optimal list which has (l1,l2) in it.
Suppose there is no such optimal list. Then there are these cases:
There are separate indices l3 and l4 such that (l1,l3) and (l2,l4) are in the list. Then replacing them by (l1,l2) and (l3,l4) would make another optimal solution.
l1 and l2 always occur with a same index, ie, only time l1 and l2 come are with some l3 (as (l1,l3) and (l2,l3)). Since in an optimal solution only one element in the end can be >1 (else can still divide by P), one of l1 and l2 will be >1 (because A[l1] >= A[l3] and A[l2]>=A[l3] therefore A[l1]*A[l2] > A[l3]).
Without loss of generalization, let l1 remain > 1. Then could have made l3 remain >1 by replacing one of (l2,l3) by (l1,l2).
Both l1 and l2 never come in the list. Then (l1,l2) can be inserted to get a better solution.
Only one of l1 and l2 comes in the list, eg, (l1,l3) is there but l2 is never there. Then we can replace this by (l1,l3), because final product cannot get worse, in fact if l2 >= P^2 then both (l1,l2) and (l2,l3) can be inserted.
Hence by contradiction there is always an optimal solution that has (l1,l2) in it.
i guess we should try finding the highest common factor for each pair of elements and divide both these numbers by the HCF found… if we repeatedly do this then probably at the end we can get min prod… plz suggest