0

I have the folowing problem:

Farmer John has built a new long barn, with N (2 <= N <= 100,000) stalls. The stalls are located along a straight line at positions x1,...,xN (0 <= xi <= 1,000,000,000).

His C (2 <= C <= N) cows don't like this barn layout and become aggressive towards each other once put into a stall. To prevent the cows from hurting each other, FJ wants to assign the cows to the stalls, such that the minimum distance between any two of them is as large as possible. What is the largest minimum distance?

Input

t – the number of test cases, then t test cases follows. * Line 1: Two space-separated integers: N and C * Lines 2..N+1: Line i+1 contains an integer stall location, xi

Output

For each test case output one integer: the largest minimum distance.

Example

Input:

1
5 3
1
2
8
4
9

Output:

3 Output details:

FJ can put his 3 cows in the stalls at positions 1, 4 and 8, resulting in a minimum distance of 3. Submit solution!

My approach was to pick some pair which has a certain gap and check if there are enough elements in the array to satisfy the need of all the cows. To find these elements,I used binary search.

When I find an element , I reset my left to mid so I can continue based on the number of cows left.

My code:

#include <iostream>

int bsearch(int arr[],int l,int r,int gap , int n,int c){
    int stat = 0;
    for (int i = 1;i <= c; ++i) {
        while(l <= r) {
            int mid = (l+r)/2;
            int x = n+(i*gap);
            if (arr[mid] > x && arr[mid-1] < x) {
                l = mid;
                ++stat;
                break;
            }
            if(arr[mid] < x) {
                l = mid + 1;
            }
            if (arr[mid] > x) {
                r = mid - 1;
            }
        }
    }
    if (stat == c) {
        return 0;
    }
    else {
        return -1;
    }

}
int calc(int arr[],int n , int c) {
    int max = 0;
    for (int i = 0; i < n; ++i) {
        for (int j = i+1;j < n; ++j) {
            int gap = arr[j] - arr[i];
            if (gap > max) {
                if (bsearch(arr,j,n-1,gap,arr[j],c) == 0) {
                    max = gap; 
                }
            }
        }
    }
    return max;
}
using namespace std;
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int t , n ,c;
    cin >> t;
    for(int i = 0 ; i < t; ++i) {
        cin >> n >> c;
        int arr[n];
        for (int z = 0 ; z < n; ++z) {
            cin >> arr[z];
        }
        sort(arr,arr+n);
        //Output;
        int ans = calc(arr,n,c);
        cout << ans;
    }
    return 0;
}

Problem Page: https://www.spoj.com/problems/AGGRCOW/

  • 1
    Fyi, there's this thing called [`std::lower_bound`](https://en.cppreference.com/w/cpp/algorithm/lower_bound) provided by the standard library, the use of which would throw about 1/3rd of this code away. – WhozCraig Nov 18 '18 at 18:14
  • @WhozCraig I know but it wouldn't take a number EQUAL to the value that I am looking for. –  Nov 18 '18 at 18:20
  • Did you *read* the link I provided ? `lower_bound` finds the first element that is *not* less than (i.e. is greater **or equal**) to the search element. After return, test the iterator for (a) non-sequence end and (b) equal. Or maybe I just misunderstand that function? One sees `bsearch` and, you know, thinks "binary *search*". – WhozCraig Nov 18 '18 at 18:24
  • Oh sry, I stand corrected.Although I could make it work ,what is wrong in the approach illustrated in my code if its fundamentally the same thing? –  Nov 18 '18 at 18:33
  • Stuff like `int arr[n]` isn't valid C++, because [C++ doesn't have variable length arrays](https://stackoverflow.com/q/1887097/9254539). Your code only compiles because of a GCC non-standard extension. You should use an `std::vector` instead to make your code portable and avoid blowing out the stack. – eesiraed Nov 18 '18 at 19:30
  • Your algorithm is wrong. It runs in at least `O(n^2)` because of the nested loop in your `calc()` function, which is too slow. The solution involves using a binary search in a different way. – eesiraed Nov 18 '18 at 19:37

0 Answers0