SimulateBST
TCO19 SRM 750 · 2019-01-09 · by misof
Problem Statement
This problem is about ordinary binary search trees (BSTs). Your task is simple: just simulate a sequence of n insertions.
Inserting an element into a BST is simple: Inserting into an empty BST produces a BST with a single node, containing the inserted value. If we already have a nonempty BST, inserting X is done as follows: Search for X in the BST. If you find it, do nothing. If you don't find it, create a new node containing X and attach it as a leaf to the existing BST in the only valid way.
For example, if we start with an empty BST and insert the values { 40, 20, 60, 70, 80, 30, 10, 30, 90 } in this order, we will get the following tree:
40
/ \
20 60
/ \ \
10 30 70
\
80
\
90
The depth of a node is defined as 1 plus the depth of its parent, with the depth of the root being 0. Let D(x) denote the depth of the node that contains the number x.
Your task will be to insert the values S(0), S(1), ..., S(n-1) and to return the following checksum: sum( D(S(i)) * 10^(5*i) ) modulo (10^9 + 7).
In order to keep the input size small and to force you to process the elements of S one at a time, the sequence S is defined recursively.
You are given a
Constraints
- n will be between 1 and 500,000, inclusive.
- m will be between 1 and 1,000,000,007, inclusive.
- a will be between 0 and m-1, inclusive.
- Sprefix will have between 1 and min(200,n) elements, inclusive.
- Each element of Sprefix will be between 0 and m-1, inclusive.
3
{10, 20, 30}
0
100
Returns: 99860
The resulting tree looks as follows: 10 \ 20 \ 30 The inserted values appear in the depths {0, 1, 2}, in this order. Thus, the correct checksum to return is (0 * 10^0 + 1 * 10^5 + 2 * 10^10) modulo 1,000,000,007.
3
{10, 10, 10}
0
100
Returns: 0
The resulting tree looks as follows: 10 The inserted values appear in the depths {0, 0, 0}, in this order. Thus, the correct checksum to return is (0 * 10^0 + 0 * 10^5 + 0 * 10^10) modulo 1,000,000,007.
3
{20, 10, 30}
0
100
Returns: 99930
The resulting tree looks as follows: 20 / \ 10 30 The inserted values appear in the depths {0, 1, 1}, in this order. Thus, the correct checksum to return is (0 * 10^0 + 1 * 10^5 + 1 * 10^10) modulo 1,000,000,007.
9
{40, 20, 60, 70, 80, 30, 10, 30, 90}
0
100
Returns: 461469106
The example shown in the ASCII art drawing in the problem statement.
15
{10, 20, 30}
100
1000000007
Returns: 149719615
The inserted values, in order: 10 20 30 1003 2004 3005 100306 200407 300508 10030609 20040710 30050811 3060905 4070997 5081091.
Submissions are judged against all 149 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class SimulateBST with a public method int checksum(int n, vector<int> Sprefix, int a, int m) · 149 test cases · 2 s / 256 MB per case