Veronica Mars and the Binary Search Tree
With the help of Mac, Veronica Mars just came up with a new way of numbering Binary Search Tree(BST) nodes! She assigns the number 11 to the root node, and any node indexed as ii will have a left child indexed as 2⋅i2⋅i and a right child indexed as 2⋅i+12⋅i+1.
1
/ \
/ \
/ \
/ \
2 3
/ \ / \
/ \ / \
4 5 6 7
and so on...
Veronica tells this new numbering scheme to her dad, Keith, and and then inserts nn distinct numbers, a0,a1,…,an−1a0,a1,…,an−1, into a BST in increasing order of indices. Because he's better at hitting bad guys than hitting books, Keith promptly forgets the numbering scheme and asks for your help!
For each number aiai, print the index of the node where it's located in the BST. See the Explanationsection for more detail.
Input Format
The first line contains a single integer, nn, denoting the number of nodes in the tree.
The second line contains nn space-separated integers describing the respective integer elements, a0a0through an−1an−1.
Constraints
1≤ai≤1091≤ai≤109
1≤n≤1031≤n≤103 for 30%30% of the test cases.
1≤n≤3×1051≤n≤3×105 for 100%100% of the test cases.
Output Format
Print a single line of nn space-separated integers where the ithith number denotes the node index where number aiai is present in the BST. As these numbers may be large, output them modulo 109+7109+7.
Sample Input 0
4
5 3 6 2
Sample Output 0
1 2 3 4
Sample Input 1
3
1 2 3
Sample Output 1
1 3 7
Explanation
Sample Case 0:
The BST formed is:
5(1)
/ \
/ \
3(2) 6(3)
/
2(4)
* The node indices are written in parentheses.
Sample Case 1:
The BST formed is
1(1)
\
\
2(3)
\
\
3(7)
* The node indices are written in parentheses.
-------------------------------------EDITORIAL---------------------------------------------------------------------
Approach 1(Brute Force):
In this approach you keep building the Binary Search Tree in a simple way. That is, you insert a new value in O(h)O(h)where h=h= current height of BST.
Worst case complexity of such an approach is O(n2)O(n2), because worst case height of BST can be O(n)O(n).
Approach 2(Intelligent):
For each position where a new number can be inserted, we can define a range of valid numbers that can be inserted at that poisition. For example, in this BST:
5
/ \
2 8
\
19
/
10
For left child of 2, the range is (−inf,2)(−inf,2) where (a,b)(a,b) denotes all valid integers in range aa to bb(excluding both aaand bb). Similarly, for right child the range is (2,5)(2,5).
For left child of 8, the range is (5,8)(5,8). For right left child of 10, the range is (8,10)(8,10) and for right child the range is (10,19)(10,19). For right child of 19 the range is (19,inf)(19,inf).
So, all the ranges are (−inf,2)(−inf,2), (2,5)(2,5), (5,8)(5,8), (8,10)(8,10), (10,19)(10,19), (19,inf)(19,inf). Another interesting observation is that all these ranges are disjoint and the break points of these ranges are the values that already exist in the BST.
Now, with these ranges we can also associate the new index a number will have if it's inserted into the tree. So, in this case, the mappings from ranges to indexes will be:
inf, 2 : 4
2, 5 : 5
5, 8 : 6
8, 10 : 28
10, 19 : 29
19, inf : 15
Now, let's say you want to insert x=9x=9, in the BST. You know that it occurs in the range (8,10)(8,10) so, index of xx will be 29. Now, this range has been destroyed and two new ranges (8,9)(8,9) and (9,10)(9,10) have been created with indexes2∗282∗28 and 2∗28+12∗28+1, respectively.
Implementation:
How do we actually implement this? We maintain a map from ranges to indexes as shown in example above. Let's say we get a value xx, how do we find the range in which it lies. Since break points of ranges are the values already existing in the BST and all ranges are disjoint, the range of xx is (x1,x2)(x1,x2), where x1x1 is the largest number smaller than xx in the BST and x2x2 is the smallest number larger than xx in the BST. These two values can be easily found via a set in C++. Now, we search for the range in the map, print the answer for xx and remove the existing range and update two new ranges in the map.
Overall complexity is O(NlogN)O(NlogN).
Set by darkshadows
Problem Setter's code :
#include<bits/stdc++.h>
#define assn(n,a,b) assert(n<=b && n>=a)
using namespace std;
#define pb push_back
#define mp make_pair
#define clr(x) x.clear()
#define sz(x) ((int)(x).size())
#define F first
#define S second
#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,b) for(i=0;i<b;i++)
#define rep1(i,b) for(i=1;i<=b;i++)
#define pdn(n) printf("%d\n",n)
#define sl(n) scanf("%lld",&n)
#define sd(n) scanf("%d",&n)
#define pn printf("\n")
typedef pair<int,int> PII;
typedef vector<PII> VPII;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef long long LL;
#define MOD 1000000007ll
LL mpow(LL a, LL n)
{LL ret=1;LL b=a;while(n) {if(n&1)
ret=(ret*b)%MOD;b=(b*b)%MOD;n>>=1;}
return (LL)ret;}
int main()
{
//map of ranges
map <pair<int,int> , LL > mymap;
map <pair<int,int> , LL >::iterator itt;
//set of values inserted into BST
set<int> myset;
set<int> myn;
set<int>::iterator it;
int n;
//define range for root
mymap[mp(INT_MIN,INT_MAX)]=1;
//scan n
sd(n);
assert(n>=1&&n<=300000);
for(int i=0; i<n; i++){
int x,l,r;
//scan A_i
sd(x);
assert(x>=1&&x<=1000000000);
//find the range in which it lies ie. (x1, x2)
myset.insert(x);
it=myset.find(x);
if(it==myset.begin())l=INT_MIN;
else{
it--;
l=*it;
it++;
}
it++;
if(it==myset.end())r=INT_MAX;
else r=*it;
//search for the range in map
itt=mymap.find(mp(l,r));
assert(itt!=mymap.end());
//insert two new ranges into the map
mymap[mp(l,x)]=(2ll*itt->S)%MOD;
mymap[mp(x,r)]=(2ll*itt->S+1ll)%MOD;
//output answer
cout << itt->S;
if(i!=n-1)cout << " ";
else cout << endl;
//erase existing range from the map
mymap.erase(itt);
}
return 0;
}
No comments:
Post a Comment