wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> cs >> Rising and Falling Problem
        
(Message started by: noMacs on Feb 9^th, 2010, 11:38pm)

Title: Rising and Falling Problem
Post by noMacs on Feb 9^th, 2010, 11:38pm

I have several points in the form of a wave. i.e. the points increase to a maximum and then decrease.
However, the peaks may be different. (There is no guarantee that all the subwaves will reach the same MAX and the same MIN before falling or rising respectively). Also, consecutive points on the wave are separated by a constant distance d.
For example, this is a wave with d=1:
1,2,3,4,5,4,3,4,5,6,7,8,9,8,7,6,5,4,3,2,1,2,3,4,5
(It's a 1 dimensional problem - in case wave and points give a feel of 2D)
What is an efficient way of finding out the number of occurrences of a particular Number when you have the set of n points representing the wave. [better than O(n)]
For example '4' occurs 5 times in the example.

Title: Re: Rising and Falling Problem
Post by nirajpatel on Feb 10^th, 2010, 2:15am

Can you store local maximas and minima ?

Title: Re: Rising and Falling Problem
Post by noMacs on Feb 10^th, 2010, 9:01am

There are no memory limitations specified in the problem. But I guess it would be good if not more than constant space is used.

Title: Re: Rising and Falling Problem
Post by JohanC on Feb 10^th, 2010, 9:35am

As there can be O(n) peaks, a general solution would always have O(n) as a worse case.
If, however, you have reason to suspect there usually won't be O(n) peaks, you can do better.
An obvious observation is that you only need to look at half of the numbers, because odd and even are alternating.

A solution with a time complexity proportional to the number of peaks, could be:
[hide]- divide the points into two (almost) equal groups; recursively count the occurences in both parts and sum them
- suppose you have k points to investigatem, M is the point in the middle and P is the point your are counting: if (abs(M-P) > k/2) you know for sure that you won't have any P and you can stop the recursion for this subset
- as we're using recursion, this would need the memory of an O(log(n)) stack[/hide]

Title: Re: Rising and Falling Problem
Post by inexorable on Feb 10^th, 2010, 4:59pm

you can take adjacent pairs of local maxima and minima, construct an interval tree http://en.wikipedia.org/wiki/Interval_tree as a preprocessing step.

Then query with a specific point will be output sensitive i.e O(log n + m) time, with n being the total number of intervals and m being the number of reported results

Title: Re: Rising and Falling Problem
Post by Grimbal on Feb 11^th, 2010, 1:25am

A simple way is to scan the array sequentially, but you move forward by abs(a[i]-p) where p is the number you are counting. If a[i]=p, move by 2.

But I think JohanC's method is more effective at reducing the number of elements tested.