 Kth Ancestor Hackerrank Problem

Hello Everyone I was trying to solve Kth Ancestor problem of HackerRank and I am using binary lifting by storing 2^i th parent of every node u in a 2D dp table p[u][i]. I don’t understand after days of my own research why i am getting wrong answer in 7 Test cases (6,8,9,10,11,12,14). I found a solution almost identical to mine which got accepted he just used transpose of my dp table in his solution. He stored every 2^ith parent of node u in a dp table parent[i][u]. I will be highly grateful if anyone can tell me what is wrong with my code

My code

#include <iostream>
#include <bits/stdc++.h>
#define N 100001
using namespace std;
vector<vector<int>> p(N,vector<int>(18,-1));      //initialized all parents to -1 initially

//Add all 2^i th parents of a node to dp table p
void add(int u, int par){
p[u]=par;
for(int j=1; j<18; j++){
p[u][j]=p[p[u][j-1]][j-1];
if(p[u][j] == -1) break;             //Ones 2^j th parent becomes -1 (does not exits) all parents above it will also not exist
}
}

//This function deletes all parent of a given node (assign them to -1)
void del(int u){
for(int j=0; j<18; j++){
p[u][j]=-1;
}
}

//Method 1 for finding kth node

//int kParent(int node, int k){
//    int curr = node;
//    int l=0;
//    for(l;(1<<l)<=k;l++);                             //Finding maximum i so that 2^i is less than or equal to k
//    l--;
//    for(int i=l; i>=0; i--){
//        if((1<<i)<=k){
//            curr = p[curr][i];
//            k-=(1<<i);
//            if(curr==-1) break;
//        }
//    }
//    return curr;
//}

//Method 2 for finding kth parent
int kParent(int node, int k) {
int current = node;
for (int i = 0; i < 18; i++) {
if (((1 << i) & k) != 0) {             //Checking ith binary digit of k from left to right is 1 or 0
current = p[current][i];          //If ith binary digit of k is 1 move current to its 2^ith parent

if(current == -1)break;
}
}
return current;
}

int main() {
int t;
scanf("%d",&t);
while (t) {
int p, x, y, q, qt;
scanf("%d",&p);
for (int i = 0; i < p; i++) scanf("%d %d",&x,&y), add(x, y);
scanf("%d",&q);
for (int i = 0; i < q; i++) {
scanf("%d",&qt);
if (qt == 0) {
scanf("%d %d",&x,&y);
} else if (qt == 1) {
scanf("%d",&x);
del(x);
} else if (qt == 2) {
int k;
scanf("%d %d",&x,&k);
int current = kParent(x,k);
if (current == -1) printf("0\n");
else printf("%d\n", current);
}
}
t--;
}
return 0;
}

Code which is passing all test cases

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;

int parents;

inline void add(int child, int parent) {
parents[child] = parent;

for (int i = 1; i < 18; i++) {
parents[i][child] = parents[i - 1][parents[i - 1][child]];

if (parents[i][child] == -1) break;
}
}

inline void remove (int leaf) {
for (int i = 0; i < 18; i++)
parents[i][leaf] = -1;
}

inline int kParent(int node, int k) {
int current = node;
for (int i = 0; i < 18; i++) {
if (((1 << i) & k) != 0) {
current = parents[i][current];

if (current == -1) break;
}
}

return current;
}

int main() {
int tests, n, child, parent, type, node, k;
//cin >> tests;
scanf("%d", &tests);

for (int t = 0; t < tests; t++) {

for (int i = 0; i < 18; i++)
for (int j = 0; j < 100001; j++)
parents[i][j] = -1;

//cin >> n;
scanf("%d", &n);
for (int i = 0; i < n; i++) {
//cin >> child >> parent;
scanf("%d %d", &child, &parent);

}

//cin >> n;
scanf("%d", &n);
for (int i = 0; i < n; i++) {
//cin >> type;
scanf("%d", &type);

if (type == 0) { // X Y, Y child of X
//cin >> parent >> child;
scanf("%d %d", &parent, &child);

} else if (type == 1) { // node (leaf) remove me
//cin >> node;
scanf("%d", &node);

remove(node);
} else if (type == 2) {
//cin >> node >> k;
scanf("%d %d", &node, &k);

int current = kParent(node, k);

if (current == -1)  printf("0\n");
else                printf("%d\n", current);
}
}

}

return 0;
}
2 Likes

Hello Guys, I finally figured out what is wrong with my solution. I was using 2D vector as 2D dp table in my solution. I replaced it with int 2d int array(int p[N]) and my solution got accepted. I don’t why it is happening but i am happy that i figured it out. If you guys know the reason why using 2D vector instead of 2D int array giving wrong answer please let me know

2 Likes

They are multiple rules and ways to use a vector. So when we don’t use it properly, we can / may get wrong results Really want to know how?

Har jagah PBDS nhi bhai Yes I know about it. For me it’s is like set with some additional features. But don’t know how t I use it in this question. Can you tell?

I know the question which you are talking about Even @samarthtandon knows I guess!

Is am I violating any code of conduct? And see this post is not created by me and I am also not off topic and I am just asking how this kth ancestor problem can be solved using pbds, what’s wrong in this?

Bhai mai majaak kar rha tha, tu kabse itna serious hone laga lol You know me . Kbse? 1 Like