21 months ago

hardik kapoor 130

Solution

Description

Given an array of N elements, select P independent pairs out of them such that the max of instability for the selected pair is minimised.

Instability is absolute of difference of elements within the pair.

Approach

• As we can see, if we select k to be our max instability, if we can select P pairs with k instability, we can select P pairs with instability more than k.
• Hence, we can apply Binary search on max instability here, where mid denotes max instability atmost mid.
• We can sort the array and take only pairs which are adjacent in the sorted array.
• To select P pairs for max instability k, we can just sort the array, and for a contagious segment in which A(i)-A(i-1) <= k, we can select maximum pairs out of them.
• That is, if pairs (1,2),(2,3),(3,4),(4,5),(7,8),(8,9) have abs difference less than k, we can create an array such that if i belongs to any pair, arr[i]=1, else arr[i]=0. Out of contagious 1's in arr, we can select floor(x/2) pairs if x is the length of the contagious 1s.

C++ Code

int solve(int n,int p,vector<int> a)
{
    sort(a.begin(),a.end());

    int lo=0,hi=2e9+5,ans=-1; // assuming range of ai is 1e9

    while(hi >= lo)
    {
        int mid=(lo+hi)/2;

        vector<int> arr(n);

        for(int i = 1;i < n;i++)
        {
            if(a[i]-a[i-1]<=mid)
            {
                arr[i-1]=1;
                arr[i]=1;
            }
        }

        int numPairs=0;

        for(int i = 0;i < n;i++)
        {
            if(arr[i]==0)
                continue;
            int j=i;

            while(j < n && arr[j]==1)
                j++;

            int cnt=j-i;
            numPairs+=cnt/2;
            i=j;
        }

        if(numPairs < p)
            lo=mid+1;
        else
            ans=mid,hi=mid-1;
    }
    return ans;
}

Time Complexity : O(N*log(1e9))

26 days ago

Rohit Kumar • 40

Raipur

The suggested algorithm doesnot works for this testcase:

1
8 4
0 1 1 4 5 5 6 6

It is giving output as 1 but the answer should be 3.

Even the accepted solution is giving ans as 1.

please help me with this.

2.0 years ago

Sahil • 40

If it is possible to select P pairs with max instability k then it is definitely possible to select P pairs with instability greater than k . Hence we can do binary search on k which will range from 0 to max(A)-min(A) and for each value of k we can greedily check on the sorted array whether it is possible to select P pairs or not . Overall time complexity would be O(nlogn)