27 lantimilan NA 847.00 52 12
After pass 10/11 in xorkey, I moved myself to 27, a career high.
However, my interval tree must have some problem since I got both 10/11 in xorkey and quadrant, both of which are range query problems and use the same data structure. There is almost no algorithm involved except maintain the data structure, which is interval tree or range tree or augmented binary tree. Now I am not sure which name is the appropriate one.
The idea for xorkey is to maintain a sorted subseq in each interval and then query bit-by-bit. However keep a vector inside a node is too expensive, as I got bad_alloc in local test. Instead put all data into a big array and only maintain a pointer to the start and stop index in that array.
Name Language Result Submission Status Submission time
XOR key C++
Time Limit Exceeded
10/11 testcases passed
40 Point(s) View Submission Processed 2012-01-15 21:21 UTC
XOR key C++
Time Limit Exceeded
1/11 testcases passed
2 Point(s) View Submission Processed 2012-01-15 19:31 UTC
XOR key C++
Time Limit Exceeded
1/11 testcases passed
2 Point(s) View Submission Processed 2012-01-14 20:56 UTC
Subscribe to:
Post Comments (Atom)
I was fine with using vectors. Instead of using an actual tree, I used the trick where you store a binary tree in an array. (Node i has children 2*i, 2*i+1, and parent i/2.)
ReplyDeleteThen I declared
vector tree[65536];
where tree[v+32768] stored all the indices i where x[i] = v.
Doing the bit-by-bit range queries with this structure felt more natural to me than actually using a real tree.
I have been trying different approaches on this problem for a couple of weeks, but haven't been successful. I have a few queries regarding your approach. How does vector tree[65536] help? If the input is ai, pi, qi (usual notations from the question), what i understand is i need an x[j], j =[pi, qi] such that bits(higher) of ai and x[j] differ. I can't get how do you do bit by bit range queries using this structure of 65536 vectors.
DeleteWe say a node i 'governs' a range [a,b) if tree[i] stores all the indices k, where x[k] is in [a,b).
DeleteNow construct a complete binary tree in the following manner:
- Node 1 governs the range [0,65536=2^16).
- Node i has children j=2*i and and k=2*i+1, which govern the lower and upper halves of i's range, respectively.
Does this make sense?
This comment has been removed by the author.
ReplyDeleteI am having a hard time solving this problem. Can u explain in detail how "interval tree" solves this problem and what do you mean by querying bit-by-bit ?
ReplyDeleteHello guys im working on this problem also i put my code on gist , https://gist.github.com/4193213 it is based on segment tree and i only passed 1st test , others test are failed because of bad:alloc (terminate called after throwing an instance of 'std::bad_alloc'
ReplyDeletewhat(): std::bad_alloc) i coded that in Java and C++
would you check my code on gist and tell me where i am wrong.