103503A — Make Sum Great Again

Author: Gheal

103503B — Binary Search Search

Author: Gheal

This binary tree was generated by starting with the root $$$m=\lfloor \frac{n+1}{2} \rfloor=6$$$. Each node $$$m=\lfloor \frac{l+r}{2}\rfloor$$$ has up to two children: $$$m_1=\lfloor \frac{l+(m-1)}{2} \rfloor$$$ and $$$m_2=\lfloor \frac{r+(m+1)}{2} \rfloor$$$.

If our given integer $$$k$$$ is in a complete layer, then we can employ a binary search-type algorithm to find the position of $$$k$$$:

\begin{lstlisting} l = 1, r = n, position = 1, visited_nodes = 1 while(visited_nodes<=n){ m = (l + r) / 2

if(k==m){
    print position
    return
}

if(k<m) position = position * 2
else position = position * 2 + 1

visited_nodes = visited_nodes * 2 + 1

} \end{lstlisting}

This algorithm has the added benefit of not printing anything if $$$k$$$ is not in a complete layer. In this case, the position of $$$k$$$ in the last layer can be determined from $$$position$$$, although this isn't as straightforward. If the binary tree were complete, then the position of $$$k$$$ in the last layer would be $$$position-\frac{\text{visited_nodes}-1}{2}$$$, since there are $$$\frac{\text{visited_nodes}-1}{2}$$$ nodes on the other layers, all of which will be printed before $$$k$$$.

By looking at the missing nodes from the binary tree for $$$n=12$$$, one may make the crucial observation that the general case position for $$$k$$$ in the last layer is equal to $$$k-(position-\frac{\text{visited_nodes}-1}{2})$$$.

In conclusion, the final position for $$$k$$$ will be $$$k-(position-\frac{\text{visited_nodes}-1}{2})+\frac{\text{visited_nodes}-1}{2}=k+\text{visited_nodes}-position-1$$$.

Time complexity per testcase: $$$O(log n)$$$