BinaryDistance
SRM 768 · 2019-10-09 · by Errichto
Problem Statement
There is a binary tree with N vertices, numbered 1 through N. For each x from 2 to N, there is an edge between vertex x and vertex x/2 (rounded down). For example, this is what the tree looks like for N = 6:
1
___/ \___
/ \
2 3
/ \ /
/ \ /
4 5 6
The distance between two vertices is defined as the number of edges on the unique simple path between them. Given some vertex V, your task is to find the maximum distance between V and some other vertex.
Constraints
- N will be between 2 and 10^9, inclusive.
- V will be between 1 and N, inclusive.
6 2 Returns: 3
In the tree with N = 6 vertices, the farthest we can get from vertex 2 is vertex 6 and the distance is 3.
6 6 Returns: 4
In the tree with N = 6 vertices, the farthest we can get from vertex 6 is vertex 4 (or vertex 5) and the distance is 4.
5 4 Returns: 3
2 2 Returns: 1
1000000000 1 Returns: 29
Submissions are judged against all 152 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class BinaryDistance with a public method int maxDist(int N, int V) · 152 test cases · 2 s / 256 MB per case