# GodFather - Code wars (Need Help)

https://www.codechef.com/viewsolution/32399872
This is my submission
My logic - used binary lifting to find the LCA of all the given nodes in the set, if LCA is present in the set then print LCA otherwise print -1

2 Likes

I also need help in last four questions. Anyone if you can explain then please help me with those last four questions.

For problem E, you can take help from here

and my solution
https://www.codechef.com/viewsolution/32403265

2 Likes

You can check this for problem D

MY SUBMISSION :CodeChef: Practical coding for everyone

1 Like

can you tell me , is my logic correct or not?

2 Likes

No, you need to first sort the vertices in order of their dfs order, then take consecutive LCA to get LCA of all vertices.

2 Likes

Can you explain how to solve simple LCM ?

but at the end I guess LCA of all nodes will be same if if find out in any orderâ€¦
I am not sure about it but looks like order doesnâ€™t matter in finding LCA
Thanks

2 Likes

There should be some problem in your implementation I have used exactly same logic and got AC
https://www.codechef.com/viewsolution/32404229

1 Like

I can help you in simple modificationâ€¦I did starting A, B, C and E

2 Likes

Isnâ€™t it good enough to check whether there is a unique highest node that is an ancestor of all other nodes?

2 Likes

void dfs(int u, int par)
{
l[u] = ++cur;
ID[cur] = u;
for (int i = 1; i < LN; i++) DP[i][u] = DP[i - 1][DP[i - 1][u]];
for (int i = 0; i < adjList[u].size(); i++){
if (v == par) continue;
LVL[v] = LVL[u] + 1;
DP[0][v] = u;
dfs(v, u);
}
r[u] = ++cur; ID[cur] = u;
}

``````  int lca(int u, int v)
{
if (LVL[u] > LVL[v]) { int temp=u; u=v; v=temp;}
for (int i = LN - 1; i >= 0; i--)
if (LVL[v] - (1 << i) >= LVL[u]) v = DP[i][v];
if (u == v) return u;
for (int i = LN - 1; i >= 0; i--){
if (DP[i][u] != DP[i][v]){
u = DP[i][u];
v = DP[i][v];
}
}
return DP[0][u];
}
``````

use these two functions
in every query take a set store all the vertices and find lca for them one by one
after that check whether final lca is there in the hashset or not

2 Likes

Yeah, exactly. Just check for the one with the least height.

1 Like

so you mean just using simple intime[] and exittime[] arrays?

2 Likes

I also got E,If you can help with the LCM one and your logic seems correct to me for D maybe there is some problem with the implementation

1 Like

Yes. Let me finish implementing to check whether it is correct.
It is

1 Like

yeah looks like i have done some mistake in LCA implementation. I will look into it myself

3 Likes

Yup it is correct! Here

2 Likes

Can you brief your logic for simple LCM ?

I looked into all 6-7 star guys who got rank from 1 to 5, almost everyone has write O(n^2) solution. I donâ€™t know how they know that it will pass under such constraints

2 Likes