TCS mockvita 2018 round

Hey guys,

To the people who have participated in TCS mockvita 2018. If anyone has solved problem C (Height of Students) ,can you please help me by providing your idea and solution?

Maybe this is not the right place to ask but I really want to know the solution as tcs does not provide editorials. Thanks in advance :slight_smile:

Can you provide link to the questions?

The link for the ques : Mockvita_C - Google Docs

If you solve it let me know your solution :slight_smile:

I think it can be solved by building a DAG and sorting it in topological order. My solution goes like this:(Not sure if its correct as there is no link to submit)

Suppose one of the photograph gives the following list : D,C,E,F,G,H.
Then the DAG for this is H->G->F->E->C->D.
Similarly add edges from all given photographs.
Now start topo sort by queue method. If at any instant there are more than 1 nodes of zero indegree, then we need to know the heights of those nodes.

1 Like

Thank you for your reply :)… I will think about this approach and try to prove correctness :slight_smile:

@amulyagaur i think you meant those nodes who contribute indegree more than one to a node

I meant those nodes which have indegree 0 that is those nodes which do not have any edge incident on it.

@romok did you solved any in that practice round? I was unable to solve any. Problem B and D is all I tried but don’t know why they were giving WA, can you provide your approach for them.

here is the code I tried but not working.