Here is the link to the problem.
My solution was a Brute force approach.
First thing i’ve did is , got rid of all leading zeroes in input strings. then for each different size in A , i made a trie . It’s not hard to see that there could be O(\sqrt{10^6}) different size string in A. So now you have a trie of height x means , there is at least one number whose x’th bit is set. so if a query string has size smaller than x , you definitely gonna find you answer on that trie.
But , there is a problem with range queries . So , I need my trie which will only contain the strings from L to R. This is very easy to deal if you make your trie persistent. But i m pretty much sure there is other ways. In my solution , i keep a version of all trie for each indices. root_{size[k]}[i]=root_{size[k]}[i-1] unless A_i.size()==size[k] , in that case i took the previous trie and insert A_i in it , take the new root ans as root_{size[k]}[i] . On each trie node , i had two information ,
- How many leaf node bellow ? same as how many string goes through this node during insertion?
- Which A_i is responsible for creating this node ? ( the index i )
With this two information , i can have my imaginary trie. For instance if root_{size[k]}[R].count - root_{size[k]}[L-1].count > 0 , that means there is some string of size[k] in ranges [L,R].
So, we have our tries, we have a particular trie to query when query string is smaller . but what about large query string ? well , every trie has one (and only ) edges from root , since we dont have leading zeros. and if we do padding (by math , not physically ) , each trie will either turn off corresponding bit of query string or turns it on while taking the xor. we want our results to be maximum. so i want my deepest trie who turn on the corresponding bit.
{okay by corresponding , i mean , suppose query string is n bit and trie has x bit string in it, all of them has first bit ‘ON’. then qs[n-i] if the bit in query string which is corresponds to the first bit of each string in the trie.}
we can found our largest trie who makes a positive changes , if none of them exist , we just found our answer with smallest one.
So now we have one perticular trie to query in any given cases But, It’s possible that we need to query on the largest trie every time . I think that’s the problem all about. I dont know what compress trie mean , but what i did was using binary search for next non bracing node. How did i do that?
for any string i inserted , i reserve a continues segments of nodes for them (from a array of nodes) , so i can have random access . so with random access on one path to the leaf from current node, and information we have stored on each node , we can use BS to find next bracing node and BOOM.
See my solution to clarify more technical details.