Binary Jumping

Binary Jumping

Tutorial

Solution

To solve this problem, we can use a standard binary lifting implementation where jmp(int x, int d) corresponds to the $d$-th ancestor of $x$.

In our jmp(int x, int d) if our final value of $x$ is $0$, then such a node does not exist and we can simply return $-1$. This is because the lowest number a node can be is $1$ (the root of the tree).

In our implementation, we test if we jump in powers of two by using the $\&$ operator. If the $i$th bit on the right is toggled, then we jump. For example, a jump of $13$ would correspond to the binary number $1101$. We would jump 3 times on bits $0, 2, 3$ (in that order) counting from the right.

To calculate the rows required for the int up[MS][MX] array, use the formula $\lceil \log_2{N} \rceil$ which in our case simplifies to $\lceil \log_2{(2\cdot 10^5)}\rceil = 18$.

#include <bits/stdc++.h>

using namespace std;

#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define FORE(i, a, b) for(int i = (a); i <= (b); i++)
#define F0R(i, a) for(int i = 0; i < (a); i++)
#define trav(a, x) for (auto& a : x)

int N, Q;

Problems

Lowest Common Ancestor

Tutorial

Implementation

Problems

USACO

General