Author |
Topic: Rising and Falling Problem (Read 399 times) |
|
noMacs
Newbie
Gender: 
Posts: 10
|
 |
Rising and Falling Problem
« on: Feb 9th, 2010, 11:38pm » |
 Quote  Modify
|
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.
|
|
 IP Logged |
|
|
|
nirajpatel
Newbie
Posts: 1
|
|
Re: Rising and Falling Problem
« Reply #1 on: Feb 10th, 2010, 2:15am » |
Quote Modify
|
Can you store local maximas and minima ?
|
|
IP Logged |
|
|
|
noMacs
Newbie
Gender:
Posts: 10
|
|
Re: Rising and Falling Problem
« Reply #2 on: Feb 10th, 2010, 9:01am » |
Quote Modify
|
There are no memory limitations specified in the problem. But I guess it would be good if not more than constant space is used.
|
|
IP Logged |
|
|
|
JohanC
Senior Riddler
Posts: 460
|
|
Re: Rising and Falling Problem
« Reply #3 on: Feb 10th, 2010, 9:35am » |
Quote Modify
|
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:
- 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
|
|
IP Logged |
|
|
|
inexorable
Full Member
Posts: 211
|
|
Re: Rising and Falling Problem
« Reply #4 on: Feb 10th, 2010, 4:59pm » |
Quote Modify
|
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
|
|
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Rising and Falling Problem
« Reply #5 on: Feb 11th, 2010, 1:25am » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print