Maximum "split" operations on an array
Given an array of n
positive integers a [1], a [2], ..., a [n] and m
good pairs of integers (i 1, j <sub> 1sub>), (g <sub> 2sub>, J <sub> 2sub>), ..., (i <sub> tsub>, J <sub> m), where 1 ≤ i k <j k ≤ n, n <= 100 and m <= 100 </p>
EDIT: every good pair (ik, jk) satisfies 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 (i k, j k) and some integer v (v> 1) that divides both numbers a [i k] and [j k] and divide both numbers by v.
Determine the maximum number of operations that you can sequentially perform on a given array. Note that one pair can be used multiple times in the described operations.
My approach:
I started with the first simple factorization of each number in the array. Given one good pair (ik, jk), we can divide both numbers A [ik] and A [jk] by their common prime powers, ie If A[ik]=2^5 * 3^4
and A[jk]=2^3 * 3^7
, then we can divide them both by 2 a total of 3 times and divide by 3 a total of 4 times. The number of operations increases by the minimum of common simple degrees, i.e. At 7.
At the same time, the total number of operations can be taken as the sum over all common prime powers for all good pairs.
However, my code doesn't work 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 cardinality 2, the 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 total cardinality 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
Handling every good pair, my code gives the answer as 28 .
However, the correct answer is 31 . I need help understanding how the result was achieved and the approach to solving this issue.
PS: The problem is problem E of Div2 Round 284 code combinations.
Problem link: http://codeforces.com/contest/499/problem/E
source to share
This problem can be solved by finding the maximum matching on the following graph. For each value of the array x, for each prime factor x, create a new vertex. If, for example, x = 12, then we create two two vertices and one 3 vertices. Make edges between pairs of vertices that match the same base ratio of the array values, making a good pair. For example, at the entrance
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 ribs
{{A2a, B2a}, {A2a, B2b}, {A2b, B2a}, {A2b, B2b}, {A2c, B2a}, {A2c, B2b}, {B2a, C2}, {B2b, C2}, {B3, C3a}, {B3, C3b}}.
The point of taking an edge {A2c, B2a}
, for example, is that we split the array records with labels A
and B
by 2
. The order of operations does not matter.
There are now algorithms for finding the best overall match, but they are complex, and I was surprised that the programming competition would include them. As it turns out, you left out an important constraint, namely that good pairs add up to odd numbers, which ensures that the graph is bipartite and therefore lends itself to simpler algorithms. Depending on how the instances look, it may also be beneficial to go from two-way matching to maximum flow, allowing for example five vertices and six edges for 2
factors A
and B
replaced with two vertices and one edge with three capacity units.
source to share
I strongly suspect you need to do a rollback. How do you choose "good couples"? What happens if you don't choose the sequence of "good pairs" that allows for the longest possible replacement chain?
You can think of the original array as a "state":
// using JSON notation; in C use structs, in Java use classes...
initialState = {
numbers: [67108864 8 2 131072 268435456 256 16384 128 8 128],
pairs: [[9, 4], [5,10], [6,9], [9, 10]], // several missing
depth: 0
}
Then you can try one of the substitutions pairs.length
to go into "child" states (where you divide the selected numbers by a common factor and increase the "depth" cone); but it is possible that doing one of these substitutions removes the possibility of performing another, different substitution: for example, I can connect 9 to 4 or to 10 or to 6 ... This means that it is usually possible to reach a "dead end", which is not the deepest impasse.
Use http://en.wikipedia.org/wiki/Backtracking to find the correct answer. If it's too slow, you can try pruning: avoid visiting the same state more than once by keeping track of unique arrays of numbers used.
source to share