0-1 Graph hackerrank

Question 0-1 Graph
The editorial says to do bfs , assign all 1 weights n travel from back and if a value is greater than next, assign min. value from right.
Is there a proof why this works>?
@tourist

2 Likes
  1. Website name is hackerrank not hackerearth.
  2. Why does it work?
    It doesnt work.
    It fails on testcase
5 4
2 5
4 3
1 4
2 4 

Most of the AC soln will print 6 but correct answer is 5.

6 Likes

You tagged tourist for that :joy: :joy: :joy: :joy: :joy:

5 Likes

What should be the solution for that question ?

@aryanc403 do u mean editorial is wrong? If so, pls send correct Sol(your approach) and intituition

I dont know the correct soln. Soln I wrote for an AC is same as editorial. But it is a wrong soln.

I just gave a counter testcase for the soln written in editorial.

4 Likes

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 so as 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);	

}

what should be the solution this question??
@aryanc403
@vijju123

I submitted a solution considering this type of test case. What i simply do is when i am doing bfs i just see if the node im going to has a the number lesser than the node im coming from , if yes then it will have distance of the node im coming from (and not + 1) .And after i have traversed the whole graph and made my dist array. I just make sure that it is non decreasing.

Please learn to read what is written above asking same question again.