VINTRBL - Editorial

editorial
, ,
1

Practice
Author: Vidit Jain

Difficulty

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