## 11235 - Frequent values

All about problems in Volume 112. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

rushel
Learning poster
Posts: 67
Joined: Sat Jan 22, 2005 5:57 am

### 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
mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:
This one maybe is a bit tricky.

Code: Select all

``````7 1
1 2 2 2 2 2 3
3 5
0
``````
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.
rushel
Learning poster
Posts: 67
Joined: Sat Jan 22, 2005 5:57 am
i got 3 also thanks
Last edited by rushel on Sun Jul 08, 2007 4:11 am, edited 1 time in total.
898989
Learning poster
Posts: 83
Joined: Wed Feb 01, 2006 12:59 pm
Location: (Fci-cu) Egypt
Contact:
Hi
Can any one describe efficient algorithm for the problem that will pass the system tests.
Sleep enough after death, it is the time to work.
sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:
Try thinking along the lines of divide and conquer.
sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York
A clever bruteforce is also enough to pass the time limit.
Timo
Learning poster
Posts: 70
Joined: Tue Oct 11, 2005 2:44 am
Location: Indonesia
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 ^_^.
"Life is more beautiful with algorithm"
sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:
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.
rushel
Learning poster
Posts: 67
Joined: Sat Jan 22, 2005 5:57 am
I use static binary heap to solve this.
sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:
I used interval tree, but that's basically implemented like a heap.
Learning poster
Posts: 63
Joined: Mon Aug 29, 2005 8:13 am
Location: Tebriz
Contact:
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
Learning poster
Posts: 70
Joined: Tue Oct 11, 2005 2:44 am
Location: Indonesia
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 ^_^.
"Life is more beautiful with algorithm"
cmd
New poster
Posts: 4
Joined: Sun Jul 08, 2007 12:44 am
Hadi wrote: The solution I used during the contest: O(n log n) preprocessing -> O(1) query answering.
mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:
There is a famous paper about it.
http://citeseer.ist.psu.edu/bender00lca.html
rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan
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