Longest chain that can be arranged

Question

I found this problem somewhere in a contest and haven't been able to come up with a solution yet.

I have the positive integers. I have to find longest subset that among each two neighbour elements one divides another.

What I'm doing is: I'm creating the graph.Then I'm connecting nodes in which numbers divides each others. After that I'm using DFS (one node can be connected with two nodes).

But not all test cases are true in system. Do I have to sort the array before using DFS? Maybe there is special (Dynamic) algorithm?

Failing test cases:

N = 5
1 1 3 7 13

My code gives the output 4. But if I arrange this array like this:

3 1 7 1 13

The output is 5 and it's the true answer.

I also used recursive method. But I need something faster.

Answer 1

You forget to reinit some variables: used and kol. Moreover DFS doesn't restore used[i] at end for next calls.

Try to avoid global variables, it make the code less clear. Try also to reduce the scope of variable.

Code may look at something like:

void DFS(int (&used)[20], const int (&m)[20][20], int c, int& maxn, int k, int v) {
    used[v] = 1;
    k += 1;
    if(k > maxn)
        maxn = k;
    for(int i = 0; i < c; ++i) {
        if(!used[i] && m[v][i] == 1) {
            DFS(used, m, c, maxn, k, i);
        }
    }
    used[v] = 0;
}

and in main:

int m[20][20];
memset(m, 0, sizeof(m));

for(int i = 0; i < c; ++i) {
    for(int j = i + 1; j < c; ++j) {
        if( (a[i] % a[j] == 0) || (a[j] % a[i] == 0) ) {
            m[i][j] = m[j][i] = 1; // Creating 2D array
        }
    }
}

int maxn = 0;
for(int i = 0; i < c; ++i) {
    int used[20];
    int k = 0;
    memset(used, 0, sizeof(used));
    DFS(used, m, c, maxn, k, i);
}
std::cout << maxn << std::endl;

Live Demo

Code may be simplified even more (use vector, ...)

Answer 2

This is longest path, slightly disguised. We can solve this problem as longest path by preparing a graph where two vertices are adjacent if and only if they satisfy a divisibility relation. See below the horizontal rule for a pointer to the intended answer.

The reduction is (roughly), given an undirected graph in which we would like to find the longest simple path, assign each vertex a distinct prime number. Emit these prime numbers, together with, for each edge, the semiprime that is the product of its endpoints. (We also need two more prime numbers and their 2|V| products with the vertex primes to preserve the objective additively.)

For example, if we have a graph

*---*
|  /|
| / |
|/  |
*---*,

then we can label

2---3
|  /|
| / |
|/  |
5---7,

and then the input is

2, 3, 5, 7,  # vertices
2*3, 2*5, 3*5, 3*7, 5*7,  # edges
11*2, 11*3, 11*5, 11*7,  # sentinels at one end
2*13, 3*13, 5*13, 7*13,  # sentinels at the other end

and (e.g.) the longest path 2, 3, 5, 7 corresponds to the longest sequence 11*2, 2, 2*3, 3, 3*5, 5, 5*7, 7, 7*13 (and three other variants involving reversal and swapping 11 and 13).

---

Longest path is NP-hard, so nhahtdh's comment about an O(2^n poly(n))-time dynamic program is right on the money -- see this question and the accepted answer: Longest path in unweighted undirected graph.