GodFather - Code wars (Need Help)

1

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
works correctly on given test cases, please help where I am wrong in logic or implementation

2 Likes
2

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

3

For problem E, you can take help from here

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

2 Likes
4

You can check this for problem D

MY SUBMISSION :CodeChef: Practical coding for everyone

1 Like
5

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

2 Likes
6

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
7

Can you explain how to solve simple LCM ?

8

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
Can you please give me counter example for your statement
Thanks

2 Likes
9

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
10

I can help you in simple modification…I did starting A, B, C and E

2 Likes
11

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

2 Likes
12

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++){
int v = adjList[u].get(i); //adjList[u][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
13

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

1 Like
14

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

2 Likes
15

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
16

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

1 Like
17

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

3 Likes
18

Yup it is correct! Here

2 Likes
19

Can you brief your logic for simple LCM ?

20

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