11235 - Frequent values
Moderator: Board moderators
11235 - Frequent values
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
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.
Code: Select all
7 1
1 2 2 2 2 2 3
3 5
0
If it didn't help, you could write a simple brute force solution and cross-check its output with your solution on random cases.
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 ^_^.898989 wrote:Hi
Can any one describe efficient algorithm for the problem that will pass the system tests.
"Life is more beautiful with algorithm"
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.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 ^_^.
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).Hadi wrote: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.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 ^_^.
The solution I used during the contest: O(n log n) preprocessing -> O(1) query answering.
And of course I can answer the query in O(1) same with you ^_^.
"Life is more beautiful with algorithm"
There is a famous paper about it.
http://citeseer.ist.psu.edu/bender00lca.html
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
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