BINSTR - No Editorial Here xD

I have solved this problem by compressing a Trie (think it is called Radix Tree). Is there other way to solve this problem (with something more simple)?

3 Likes

Please remove the editorial word from question title.

2 Likes

I believe I used a similar algorithm as you. I can try to explain it but it’s hard to articulate.

I didn’t know what it was called but I used something that looks like a poorly implemented radix tree (I failed to properly collapse all types of branch nodes with only one child). Each node in the tree held an array of indices which represent the values on that branch. I kept this so that I could search the indices to make sure that there was at least one within [L, R]. If there was exactly one I returned it’s value. If there was more than one I followed the node. I always tried to follow the node which was the result of the xor for the appropriate bit. If that node wasn’t populated with at least one index in [L, R] then I followed the other node.

https://www.codechef.com/viewsolution/21584591

Change the heading fast or you getting down vote…
Don’t keep such names to attract people to your question

@l_returns done. xD

Okay… :slight_smile:

1 Like

@I_returns It was not my intention, sorry.

When can we expect editorial for this question?

I just asked the editorialist about it… he said he will post it soon (ASAP)…

1 Like

Been a lot of time. This actually takes away the eagerness to know the solution. We don’t expect a fancy editorial everytime, a normal text editorial would do.

1 Like

Agree with you… I also wanted to see it…

Looks like it’s never gonna see the light of day

1 Like
//