Doubt - 0-1 Graph (Hackerrank Hack the Interview VI)

The problem is here. All the test cases are available if you solve the problem (you might not be able to access that link). The official editorial is here.
My solution gets WA in three of fourteen tests.

My logic is:
Each graph can be transformed to a tree which will have the same solution. This tree is constructed such that each vertex > parent of this vertex.
Initially, the tree is linear ie 1 <- 2 <- 3 <- … <- n. Then, go through the edges of the graph. For each edge (a, b) where a < b, set tree[b] = min(tree[b], a). Then, we traverse the array in reverse manner reducing values to make it a non-decreasing array. But the values are not distances, they are parent vertices. The last loop calculates the sum of distances.

void solve()
{
ll n, nf_edges;
scan(n);scan(nf_edges);

vector<ll> tree(n + 1);
for (ll i = 1; i <= n; ++i)
{
	tree[i] = i - 1;
}
//print_container(tree);

ll one, two, large, small;
while (nf_edges --)
{
	scan(one); scan(two);
	large = max(one, two);
	small = min(one, two);
	tree[large] = min(tree[large], small);
}

//print_container(tree);

for (ll i = n, level = n; i > 1; i--)
{
	if (level > tree[i])
	{
		level = tree[i];
	}
	else
	{
		tree[i] = level;
	}
}
    //print_container(tree);

ll summ = 0;
for (ll i = 2, mul = 0; i <= n; ++i)
{
	if (tree[i - 1] != tree[i])
	{
		mul++;
	}
	summ += mul;
}

pnl(summ);	

}

I’d like an explanation for why this approach is incorrect or a small test case for which my approach fails.

Doubt has been resolved. It turns out the editorial was incorrect.

Hello,

I am Darshan, I manage content on HackerRank. We would like to apologize for the issues in this challenge in our latest contest.

For the complete correctness of the challenge, our author’s greedy solution does not suffice, as indicated correctly by you.

We benchmark our challenges through multiple coders, and with this specific challenge, a corner case was not discovered by us which resulted in providing an incorrect challenge.

We are carefully evaluating our internal practices in order to avoid such issues in the future.

The Greedy Solution provided as part of the Problem Setters solution missed on this key test case, we will be updating the solution here soon.

We are really sorry for the inconvenience caused and as a result, we have decided to not consider this challenge in the contest to calibrate the results and will update the leaderboard accordingly. We are working on making our problems more robust every day. Your feedback is much appreciated and will help us improve our challenge quality.

Hope to see you again in future contests! Thank you.

1 Like