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

Post by rushel »

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:

Post by mf »

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

Post by rushel »

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:

Post by 898989 »

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.
Mostafa Saad

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:

Post by sclo »

Try thinking along the lines of divide and conquer.

sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

Post by sohel »

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

Post by Timo »

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:

Post by sclo »

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

Post by rushel »

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:

Post by sclo »

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

Hadi
Learning poster
Posts: 63
Joined: Mon Aug 29, 2005 8:13 am
Location: Tebriz
Contact:

Post by Hadi »

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

Post by Timo »

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 ^_^.
"Life is more beautiful with algorithm"

cmd
New poster
Posts: 4
Joined: Sun Jul 08, 2007 12:44 am

Post by cmd »

Hadi wrote: The solution I used during the contest: O(n log n) preprocessing -> O(1) query answering.
Can you tell about your solution?

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by mf »

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

Post by rio »

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

Post Reply

Return to “Volume 112 (11200-11299)”