no_life's blog

By no_life, history, 6 months ago, ,

This problem came on TCS mockvita 2018.Here is a link to problem — https://www.programminggeek.in/2018/07/mockvita-2018-problem-heights-of.html?m=1

Any idea how to solve this?

 » 6 months ago, # |   +3 I think this should work: For each List **L** of the **k** lists, lets denote this List **L** like one tuple (ui, ui + 1, ..., un) of vertices, then create one edge from ui to ui + 1. Now after builded this graph you can run one dfs starting from each vertice (source), and in the DFS you need mark in a table **T**, let **s** be the source vertice, so for all others vertices **v** visited in the DFS mark **T[source][s] = T[s][source] = true**, this mean that you know the relative order between the two vertices. After runned the DFS over all sources loop over all pairs of vertices **(u, v)** and if **T[u][v]** is false, you need to ask the heights of **u** and **v**. e.g n = 8, k = 2 **List1 = {A, C, D, E}** **List2 = {F, G, A, B, H}** **** **Edges = {A -> C, C -> D, D -> E, F -> G, G -> A, A -> B, B -> H}** So in the DFS starting in A you can mark: T[A][C] = T[C][A] = true T[A][D] = T[D][A] = true T[A][E] = T[E][A] = true Now starting from B you can mark T[B][H] = T[H][B] = true Now from C T[C][D] = T[D][C] = true T[C][E] = T[E][C] = true repeat this process until the last vertice, and you can see that in the end: T[A][B] = T[B][A] = false T[A][H] = T[H][A] = false T[C][B] = T[B][C] = false T[C][H] = T[H][C] = false T[D][B] = T[B][D] = false T[D][H] = T[H][D] = false T[E][B] = T[B][E] = false T[E][H] = T[H][E] = false So you need ask the heights of A, B, C, D, E, H. 
•  » » 6 months ago, # ^ |   0 Great approach. I thought one topological sort will work after adding all the edges. But your approach looks like to be correct.