OJ Board

I tried so many inputs and all of them seems to be right. but i am having WA.
can anybody give some tricky test cases
thanks

This one maybe is a bit tricky. Output: 3

If it didn't help, you could write a simple brute force solution and cross-check its output with your solution on random cases.

i got 3 also thanks

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

Try thinking along the lines of divide and conquer.

A clever bruteforce is also enough to pass the time limit.

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 ^_^.

sohel wrote:A clever bruteforce is also enough to pass the time limit.

I can't think of anything other than a simple O(nlogn) solution, and even my modest solution takes around 4 secs.

I use static binary heap to solve this.

I used interval tree, but that's basically implemented like a heap.

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.

Hadi wrote:

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 ^_^.

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

Can you tell about your solution?

There is a famous paper about it.
http://citeseer.ist.psu.edu/bender00lca.html

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