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 » Sat Jul 07, 2007 8:08 pm

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 » Sat Jul 07, 2007 8:26 pm

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 » Sat Jul 07, 2007 8:29 pm

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 » Sat Jul 07, 2007 10:50 pm

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 » Sun Jul 08, 2007 7:08 am

Try thinking along the lines of divide and conquer.

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

Post by sohel » Sun Jul 08, 2007 8:21 am

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 » Sun Jul 08, 2007 9:05 am

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 » Sun Jul 08, 2007 9:30 am

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 » Sun Jul 08, 2007 10:40 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:

Post by sclo » Sun Jul 08, 2007 1:09 pm

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

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

Post by Hadi » Sun Jul 08, 2007 5:12 pm

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 » Mon Jul 09, 2007 3:02 am

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 » Tue Jul 10, 2007 12:46 am

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 » Tue Jul 10, 2007 1:08 am

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

User avatar
rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan

Post by rio » Tue Jul 10, 2007 9:16 am

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)”