 # Whats wrong with my approach ? - Kirito in labyrinth

After looking at other approaches for this problem, I realized that it was a simple problem and I was just making it complex. But still, I am unable to find a mistake in my approach.

What I tried to do is, I made a segment tree using the code :

``````void segtree(int node, int b, int e) {
if (b == e){

st[node] = in[b];

}else{
segtree(2 * node + 1, b, (b + e) / 2);
segtree(2 * node + 2, (b + e) / 2 +1, e);
st[node] = (st[2*node+ 1]*st[2*node + 2])/gcd(st[2*node+ 1],st[2*node + 2]);
}
}
``````

Now, in this segment tree, each node contains the factors, contained by both of its child-nodes.

Further then, I started with one of the leaves, and moved through the tree, using recursion, checking if node has gcd(curent_node, the_value_of_the_leaf) > 1. If the condition is true, I enter into the childs of that node.

In this way, I was saving the maximum depth that we can reach from all the leaves, and was saving that into a dp[] array.
For answer I was just taking the max value in the dp[].

The actual code is kind of clumsy but - https://www.codechef.com/viewsolution/12252520

or the code in plain-text form - https://www.codechef.com/viewplaintext/12252520

Hi,
I didn’t checked your entire code,but in the function segtree, the statement

``````st[node] = (st[2*node+ 1]*st[2*node + 2])/gcd(st[2*node+ 1],st[2*node + 2]);
``````

may lead to integer overflow based on the input.

Thanks.

2 Likes

I am not much strong with the concept of segment trees, but reading your explanation of your concept, i can see only thing, although i may be quite wrong.

you said that in each node you are storing the factors of its child nodes, by factors i am thinking the smallest number divisible by both numbers since you are doing this `(a*b)/__gcd(a,b)`. But when you are traversing the segment tree you are applying the required condition `__gcd(a,b) > 1`. Now the child nodes have the value `a*b/__gcd(a,b)` and hence you are again applying the condition `__gcd(a, (a*b)/__gcd(a,b)) > 1` i don’t think this condition would work out for all cases.

again i could be gravely mistaken. But since you were unable to find out your mistake, i thought i could give it a try. Please correct me if i am wrong, or if i misunderstood anything.

//