Practice
Author: Vidit Jain
Difficulty
MediumHard
Explanation
The approach of the solution given is along the right path, but due to the implementation of one of the sections, we get a wrong answer on some types of test cases.
while ((l >= 0) && (find_set(l) != find_set(i)) && (arr[i] % arr[l] == 0))
l;
l++;
while ((r < n) && (find_set(r) != find_set(i)) && (arr[i] % arr[r] == 0))
r++;
r;
edges += r  l;
mstCost += 1ll * (r  l) * val;
for (int j = l; j <= r; j++)
union_sets(i, j);
The error can be best explained with an example
5 100
8 4 2 6 3
Going through the steps of the algorithm we’ll see the edges being selected as follows. (Assume 1Indexed)

Value  2, Index  3
No edges will be created

Value  3, Index  5
No edges will be created

Value  4, Index  2
An edge will be constructed between indices 2, 3
Edges Taken  \{(2, 3)\}

Value  6, Index  4
An edge will be created between indices 3, 4 and 4, 5
Edges Taken  \{(2, 3), (3, 4), (4, 5)\}

Value  8, Index  1
An edge will be created between indices 1, 2.
However, we don’t account for the fact that after taking this edge, indices 1, 3 are already connected as the edges taken will be \{(2, 3), (3, 4), (4, 5), (1, 2)\}. This occurs as we don’t perform the
unify()
function after taking an edge immediately. Hence, we end up taking an extra edge between indices 1, 3 , making the edges taken \{(2, 3), (3, 4), (4, 5), (1, 2), (1, 3)\}.
As a result of taking an extra edge, another error pops up in the line
mstCost += 1ll * ((n  1)  edges) * k;
Since the value of edges
is n
, we’ll end up further incorrectly subtracting 100 from the mstCost
.