Whats wrong with my approach ? - Kirito in labyrinth

general
1

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 - CodeChef: Practical coding for everyone

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

2

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
3

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.