 # VINTRBL - Editorial

Practice
Author: Vidit Jain

Medium-Hard

## 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 1-Indexed)

1. Value - 2, Index - 3

No edges will be created

2. Value - 3, Index - 5

No edges will be created

3. Value - 4, Index - 2

An edge will be constructed between indices 2, 3

Edges Taken - \{(2, 3)\}

4. Value - 6, Index - 4

An edge will be created between indices 3, 4 and 4, 5

Edges Taken - \{(2, 3), (3, 4), (4, 5)\}

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`.

1 Like