Author |
Topic: select k to maximize the minimum (Read 3088 times) |
|
inexorable
Full Member
Posts: 211
|
 |
select k to maximize the minimum
« on: Apr 6th, 2011, 11:20am » |
 Quote  Modify
|
Given a sorted array of n integers, pick up k elements so that the minimum difference between consecutive elements is maximum (that is choose the elements to maximize the quantity min(a[i+1] - a[i]))
when k=2 the elements are a[0] and a[n-1]
how do you choose when k>2?
For example:-
If the given array is (1,3,4,5,7) and k = 4
If we choose (1,4,5,7) the min difference between elements is 1.
If we choose (1,3,5,7) the min difference is 2.
|
|
 IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender: 
Posts: 7527
|
|
Re: select k to maximize the minimum
« Reply #1 on: Apr 7th, 2011, 1:27am » |
Quote Modify
|
The first idea would be a binary search.
Choose a value di for the minimum delta and see how many items you can pick with at least that difference. (that step is is O(n)).
Adjust the delta by choosing successive di until you get the largest value d that allows k elements or more.
To speed up things, when testing di, record the largest d'<di that woudl change the set and the largest d">di that would not change the set. (d" is the maximum of differences you see in the set you pick).
If di is too large (you cannot pick k elements) then you need to search for di+1 <= d'. If not, you need to search for di+1 >= d"
|
|
IP Logged |
|
|
|
inexorable
Full Member
Posts: 211
|
|
Re: select k to maximize the minimum
« Reply #2 on: Apr 7th, 2011, 4:25pm » |
Quote Modify
|
Thank you Grimbal.
complexity would be O(nlog(a[n-1],a[0]))
But if a[n-1] -a[0] is very high, complexity could be high?
The code for the above could look like this.
Code:
#include<iostream>
#include<vector>
using namespace std;
int countK(vector<int> &V, int diff)
{
int count=1;
for(int i=1,j=0;i<V.size();i++)
{
if(V[i]-V[j]>=diff)
{
j=i;count++;
}
}
return count;
}
void getKelements(vector<int> &V, int k, vector<int> &Result)
{
int min=INT_MAX;
for(int i=0;i<V.size()-1;i++)
{
if(V[i+1]-V[i] < min)
min=V[i+1]-V[i];
}
int max=V[V.size()-1]-V[0];
int low=min,high=max;
while(low < high)
{
int mid=low+ (high-1ow)/2;
int numelem=countK(V,mid);
if(numelem < k)
high=mid-1;
else
low=mid;
}
giveK(V,low,Result);
}
void giveK(vector<int> &V, int diff, vector<int> &Result)
{
int count=1;
Result.push_back(V[0]);
for(int i=1,j=0;i<V.size()&&count<K;i++)
{
if(V[i]-V[j]>=diff)
{
Result.push_back(V[i]);
j=i;count++;
}
}
return;
}
|
|
|
|
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: select k to maximize the minimum
« Reply #3 on: Apr 8th, 2011, 6:25am » |
Quote Modify
|
That's what I said in my second paragraph.
When you count the size of the valid set, you should also record the smallest difference that was >=diff and the largest difference that was <diff.
Say d- = max(V[i]-V[j] | V[i]-V[j]<diff)
and d+ = min(V[i]-V[j] | V[i]-V[j]>=diff)
Then you continue with high=d- or with low=d+.
|
|
IP Logged |
|
|
|
spicy
Newbie
Gender: 
Posts: 8
|
|
Re: select k to maximize the minimum
« Reply #4 on: Apr 10th, 2011, 3:50am » |
Quote Modify
|
We could also create/use Max max Heap to pic next element from it. Whenever we select/pop Max element from it, just insert (B-A)/2 nearest element from left and right side in HEap
so initially a[n-1]-a[0]/2 nearest element in Heap, then insert two elements one is center from left and another one is on right ide , everytime one pop and 2 inserts,
so total complexity would be K[log N + log N] (here N would be will shrink as K will increase but still upper bound will be K logN
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print