Help needed in FGTREE (June Long Challenge)

How to solve FGTREE?
I barely managed to get 40 points by solving it with recursion:)

I would suggest you wait for the editorial. I was going to share my solution but while writing it, I realised it is fairly complicated and I will have to write a lot.
I’m not sure if the worst case for my approach will fit in 300 queries but it did pass so I’ll explain it here. I really hope that there is a much easier solution than mine.

Anyway, here is an overview of my solution:
My idea was to solve it branch by branch.
Basically find out parents of all nodes on the leftmost branch and solve the remaining tree recursively.
Example: Consider the tree with 10 nodes and ‘parent sequence’ \text{2 4 2 6 4 -1 9 7 6 9}. The branches here would be \text{1; 3, 2; 5, 4; 8, 7; 10, 9, 6;}
Observations:

  • Any finite tree must have a leaf ( node with no children ).
  • If the node numbered L is a leaf then \text{Q L L L} will be “Yes” ( because subtree of L contains only L ).
  • The leaf of the leftmost branch will have the smallest number out of all leaves.
  • If L is a leaf, L+1 will be its first ancestor who has left child belonging to current branch.
  • You also need to calculate and store a[I] ( as defined in the question ) for each I whose parent you have determined so far.
  • Using some queries you can find out parents of all nodes in the current branch till the left child of L+1
  • Now either L+1 is part of the current branch or not. If L+1 does not have a right subtree ( which can be checked using \text{Q L+1 a[L+1] L+1} ) then it is part of the current branch so you can recursively build up considering L+1 as the leftmost leaf of the unsolved tree, otherwise L+1 is not part of the current branch and recursively solve the rest of the tree ( because the current branch is done ).
  • It is also important if L+1 is root or not but this is already complicated enough.

Using all this you can find parents of every node in the tree.
Complexity O(n).
I know it is very vague and probably useless but again, I suggest wait for the editorial.

4 Likes

Thanks for the effort you took. :slight_smile:
Although, I didn’t get much.

I have updated it to include more and you can probably arrive at my solution after putting some effort.

I did it in exactly 2*n - 1 queries whatever the tree may be. I have written a small pseudo code like steps in my solution. You can check that https://www.codechef.com/viewsolution/24738864 . And also it is better to wait for editorial as all those steps are hard to explain for me.

1 Like

I found an efficient solution to FGTREE (Forgotten Tree 9), which can solve rapidly with about 3N/2 queries per test case.

The solution works with sub-trees, where a sub-tree has any node X as its root, and left-most descendent A and right-most descendant B. All nodes in the range A <= X <= B lie in the sub-tree, and no other nodes.

Consequently a query of the form ‘Q X A B’ enquires whether node X is the root of a sub-tree spanning nodes A to B.

With each node we store the left-most descendent A and right-most descendant B, as well as the parent X. Initially A and B are set equal to X, and the parent to 0 meaning that it is not yet known.

First we identify all leaves of the tree. A node J may be identified as a leaf by issuing a query ‘Q J J J’. Note that if node J is a leaf, then node J + 1 cannot also be a leaf, because any consecutive pair of nodes cannot both be leaves.
For example we may have 13 nodes with the following leaves.

      +      +      +      +      +
      3      5      7      9     11

Place these leaves in an array of roots of sub-trees.

Work through these sub-tree roots from left to right. First check whether we have finished, with only one root which extends over the entire tree with A = 1 and B = N. From each sub-tree root we may ascend the tree in one of three ways, or none.
As we ascend the tree we set the parent(s) of the root being replaced, and the extent A, B of the sub-tree of the new root.

  1. If the node Y to the left of the left-most descendant A of the current root X is one to the right of the right-most descendant of the sub-tree Z to the left,
    check whether we can combine them into a single sub-tree with root Y.
    We can do this without further checking if X and Z extend over the entire tree with AZ = 1 and BX = N. Otherwise check by a query ‘Q Y AZ BX’. If successful, remove X from the array and replace Z by Y.

  2. If this is the first sub-tree and A > 1, or the node Y to the left of the left-most descendant A of the current root X is at least two to the right of the right-most descendant of the sub-tree Z to the left, check whether we can climb left from X to Y. We can do this without further checking if there is only one subtree and B = N. Otherwise check by a query ‘Q Y Y B’. If successful, replace Z by Y.

  3. If this is the last sub-tree and B < N, or the node Y to the right of the right-most descendant B of the current root X is at least two to the left of the left-most descendant of the sub-tree Z to the right, check whether we can climb right from X to Y. We can do this without further checking if there is only one subtree and A = 1. Otherwise check by a query ‘Q A Y Y’. If successful, replace Z by Y.

If any of these is successful, check if we can ascend further from Y by any of these three methods. If unsuccessful, move on to the next subtree to the right.

Here is an example, starting from the leaves above, in a tree with 13 nodes:

Query whether we can climb left from 3 to 2. We can.
Query whether we can climb left from 2 to 1. We can.
We cannot climb further yet. Move on to node 5.

Query whether we can combine node 5 with 1 at 4. We cannot. Move on to node 7.

Query whether we can combine node 7 with 5 at 6. We cannot. Move on to node 9.

Query whether we can combine node 9 with 7 at 8. We can. The tree now looks like this:

+
1\
  \
   +                   +
   2\                 /8\
     \               /   \
      +      +      +     +      +
      3      5      7     9     11

Query whether we can combine node 8 with 5 at 6. We can.

Query whether we can combine node 6 with 1 at 4. We can.

Query whether we can combine node 4 with 11 at 10. We cannot. Move on to node 11.

Query whether we can climb right from 11 to 12. We can.

Query whether we can combine node 4 with 12 at 10. We can.

Climb right from 10 to 13 without the need for a query. The final tree looks like this:

                               - - - +
                             /      13
                            /
               - - - - - - +-
           /              10  \
          /                    \
    - -  + - -                  \
  /      4\     \                |
 /         \     \               |
+           |     +              |
1\          |     6\             |
  \         |       \            |
   +        |        +           +
   2\       |       /8\         /12
     \      |      /   \       /
      +     +     +     +     +
      3     5     7     9    11

This tree is completed with 18 queries. The number of queries needed is typically about 3 N / 2.

You can see my implementation of this solution at https://www.codechef.com/viewsolution/24834837
It passed in 0.11 seconds. In the code I call a root of a sub-tree a top_node.

4 Likes

If you want a hint, here is where I started. The tree is clearly a Binary Search Tree. If you got that then think about leaf nodes and properties of BST. Any sub-tree in a BST holds nodes with values in a contiguous range. Everything after this observation is a play on checking leaf nodes, whether something is a proper sub-tree in the BST.

The queries also need the smallest value in the sub-tree, largest value in the sub-tree and the root of that sub-tree. That is good enough to represent what contiguous range it stores in the BST (smallest to largest). Then I came up with an idea which based on successors and where they can be placed in BST (either in the right child sub-tree is the node has one, or somewhere up the tree through the parent edges).

Try to inspect the sub-tree of 1 (it clearly can’t have a left child), then try to inspect stuff about 2 and so on. As you will know everything about the previous nodes you will know whats going on. I think its a nice problem that you will like (nay love) to solve on your own, so I’m just writing the key insights and basic ideas.

Happy solving :wink:

4 Likes

My approach was also the same. I started from node 1 then check if it has a right (Surely it does not contain left child) subtree or not. If it contains a right child then solve for the right subtree and return the max node of the subtree.
Let’s assume 1 has a right child. How do I solve the right subtree?
In the subtree I started checking with node 2 the same way I did for node 1.
My objection in this subtree was to find its root. When I found the root I assigned
Parent[root] = 1(for this case it is 1 as I branched off from node 1) and returned the biggest node of the subtree.
Now I know the biggest (rightmost) node b of right subtree of 1. So parent[1] = b + 1, as it is a BST.

2 Likes