At first, I tried to solve this problem with a persistent trie and a segment tree, but got a TLE. (Source Code)
Then, I replaced the segment tree with a sparse table, and do some other constant optimizations to turn the TLE into AC. (Source Code)
The time complexity of my solution is \mathcal O(n\log n+(n+q)\log v_i).
So, I wonder if there are solutions with lower time complexity, or we just need to reduce constant factors to fit the time limit.
Yes, I too guess this problem required some smart optimizations with the constant factors playing a big role!.
Even my own Java soln TLE’d, maybe due to overload operations with ArrayList.
But later I came to know the test cases for this problems where not too heavy.
This soln : CodeChef: Practical coding for everyone , has a time complexity of O(q * n) in worst case , no doubt this soln had the expected implementation of persistent segment trie.
See a lot of O(N * Q) solutions out there passing, they did not have any test case with all numbers same and all queries as 1 to N. I hope these test cases are added in the practice section.
My soln was O(n logn log ai + q log ai).
Where log ai = 20 in this case.
Hey everyone,
Sorry about the weak testcases. This is first my problem. I will make sure this never happens again. I will add some testcases in the practice section. And about the timelimit, my idea was to use persistent trie for each subtree. This can be built by first building persistent tries of all child subtrees and then adding all nodes in subtrees of small children to trie of big child. This takes O(n logn logMAXN) to create and for each query it takes O(Q logMAXN). My solution took 1.17s to run. So I kept timelimit to 2s. Sorry for that. Here is my solution for reference: My solution
why editorials are taking so long
am eagerly waiting for it
Because they take long time after every contest.
And If they provide editorials on time then someone may say that they are breaking their third tradition. CodeChef Traditions (Unoffical)
I can understand such instances…
That why advice to keep time limit a bit lenient… My solution( for CCIRCLES) was passing in 0.05 secs while people did the exactly same code and just replaced long long int by double and it took 0.80 secs for them.
Luckily I kept time limit 1 sec.
So it is sometimes unpredictable (for noob problem setters like me at least 
)
where can I learn about this Trie implementation? Just reading the code isn’t enough for me.
