SimulateBST | Topcoder Archive

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 int[] Sprefix with p elements: the values S(0), ..., S(p-1). Each of the following elements of S is computed as follows: S(i) = (a * S(i-p) + D(S(i-1)) + 1) modulo m.

Definition

Class:: SimulateBST
Method:: checksum
Parameters:: int, int[], int, int
Returns:: int
Method signature:: int checksum(int n, int[] Sprefix, int a, int m)
(be sure your method is public)

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.

Examples

```
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.

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.