898989 wrote:Hi
Can any one describe efficient algorithm for the problem that will pass the system tests.

Think about Range Maximum Query(RMQ), then you can answer each query in O(lg N) operation after O(N lg N) for build the tree. You must transform the problem to RMQ first ^_^.

Timo wrote:Think about Range Maximum Query(RMQ), then you can answer each query in O(lg N) operation after O(N lg N) for build the tree. You must transform the problem to RMQ first ^_^.

O(n log n) preprocessing -> O(log n) query answering? If you use binary trees, I think the preprocessing part is O(n) not O(n log n). The tree you construct has: n + n/2 + n/4 + ... nodes, which sum to 2n, not n log n.

The solution I used during the contest: O(n log n) preprocessing -> O(1) query answering.

Timo wrote:Think about Range Maximum Query(RMQ), then you can answer each query in O(lg N) operation after O(N lg N) for build the tree. You must transform the problem to RMQ first ^_^.

O(n log n) preprocessing -> O(log n) query answering? If you use binary trees, I think the preprocessing part is O(n) not O(n log n). The tree you construct has: n + n/2 + n/4 + ... nodes, which sum to 2n, not n log n.

The solution I used during the contest: O(n log n) preprocessing -> O(1) query answering.

My tree was a bit different ^_^, so the reconstruction will need O(n lg n).
And of course I can answer the query in O(1) same with you ^_^.

I used List to solve this problem, and it seems its fast enough.
O(n) to construct, and almost O(1) for query (Actually, the worst case takes O(root(n))
Before optimizing the I/O, it run with 1.0 ~ sec .(What a huge I/O ...)

ADD : Don't have much confidence in my calculate of time complexity...
----
Rio