Connection Status:
Competition Arena > BinaryHeapLeaf

BinaryHeapLeaf

SRM 776 · 2020-01-23 · by misof

SRM 776 · 2020-01-23 · by misof · Math
Class Name: BinaryHeapLeaf
Return Type: int[]
Method Name: maxDiff
Arg Types: (int)
Problem Statement

Problem Statement

A binary heap with the maximum in the root is a heap data structure that takes the form of a binary tree with two additional constraints:

  • Shape property: a binary heap is a complete binary tree; that is, all levels of the tree, except possibly the last one (deepest) are fully filled, and, if the last level of the tree is not complete, the nodes of that level are filled from left to right.
  • Heap property: the key stored in each node is greater than each of the keys in the node's children. (In this problem the keys stored in a heap are always pairwise distinct.)

The ASCII art below shows one possible binary heap with 9 vertices. The numbers represent the keys stored in the vertices of the heap. Note that all heaps with 9 vertices have this exact shape, only the placement of keys into vertices may be different. 

         100
       /     \
     19       36
    /  \     /  \
  17    3  25    1
 /  \
2    7

Given a heap H, let maxleaf(H) denote the largest key that is stored in one of the leaves of the heap H. E.g., for the heap shown above we have maxleaf(H) = max(2,7,3,25,1) = 25.

You are given the int N. Consider all possible binary heaps with maximum in the root that contain the set of keys {1, 2, ..., N}. Suppose we compute the value maxleaf() for each of these heaps. Let S be the smallest and L the largest among these values. Return the int[] { S, L }.

Constraints

  • N will be between 2 and 10^6, inclusive.
Examples
0)
2
Returns: {1, 1 }

The only maximum binary heap with the keys {1, 2} looks as follows: 2 / 1 The only leaf of this heap contains the value 1, so maxleaf(this heap) = 1 and the correct answer is {1, 1}.

1)
3
Returns: {2, 2 }

There are two different maximum binary heaps with the keys {1, 2, 3}: 3 3 / \ and / \ 1 2 2 1 Clearly, both of them have maxleaf = 2, hence the correct answer to this test case is {2, 2}.

2)
4
Returns: {2, 3 }

For N = 4 we have three distinct heaps: 4 4 4 / \ / \ / \ 2 3 3 2 3 1 / / / 1 1 2 The second and third of these heaps have maxleaf = 2, but the one on the left has maxleaf = 3. Thus, the smallest possible value of maxleaf is 2 and the largest is 3, and therefore we should return {2, 3}.

3)
7
Returns: {4, 5 }

Below is one possible heap with maxleaf=4 and one with maxleaf=5. 7 7 / \ / \ 6 5 6 4 / \ / \ / \ / \ 4 1 2 3 3 5 1 2

4)
47
Returns: {24, 43 }

Submissions are judged against all 35 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class BinaryHeapLeaf with a public method vector<int> maxDiff(int N) · 35 test cases · 2 s / 256 MB per case

Submitting as anonymous