How to approach this problem?

#1

I don’t think I can apply binary search in array here , as there can be many combinations , how should i proceed??

#2

really need some help with these problems

#3

@bhavik911,

sample test case:
5 3
1 2 8 4 9

arranged in sorted order, index of stall available:
1 2 4 8 9

Now possible arrangement of 3 cows (3 is given in the question):
1 2 4 //min distance between adjacent cows = 1
1 2 8 // 1
1 2 9 // 1
1 4 8 // 3
1 4 9 // 3
1 8 9 // 1
2 8 4 // 2
…
4 8 9 // 1

The largest among all the min distance = 3.
That’s the output and our final answer.

Approach:

For this problem, fix one cow at the first position and then move ahead.

So create a minimum Distance function which basically calculates a mid point and treats that as the minimum distance to place a cow. If we have a position greater than or equal to this distance, we fix the cow at that position.

Now call another Function which takes as input the the minimum distance (or the mid point), number of cows, the array of stall positions and size of the array

#4

Hey I solved the problem but I was facing a situation that my left and right were not converging , for all the questions I solved till now they were converging , I changed my code after a lot of debugging and got the right one . But then I checked but the editorial and find out they have mentioned a similar issue of doing s+1<e;
can you please explain why we have to do this , I am really confused . Please explain

Capture
Capture794×317 7.26 KB

#5 
package Arrays;

import java.util.Arrays;
import java.util.Scanner;

public class AggresiveCows {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n1 = scanner.nextInt();
        int cows = scanner.nextInt();
        int[] arr = new int[n1];
        for (int i = 0; i < n1; i++) {
            arr[i] = scanner.nextInt();
        }
        Arrays.sort(arr);
        System.out.println(binaryCow(arr,cows));
    }

    public static boolean cowAssign(int[] arr, int cows, int gap) {
        int count = cows-1; // one cow already at index 0 or 1st stall
        int pointer = 1;
        int lo = 0;//start to check from 1st index
        while(count>0 && lo +pointer<arr.length ){
            if(arr[lo+pointer]-arr[lo]>=gap){
                count--;
                lo = lo + pointer;
                pointer =0;
            }
            pointer++;

        }
        if(count==0){
            return true;
        }else {
            return  false;
        }

    }

    public static int binaryCow(int[]arr, int cows){
        int lo = 0;
        int high = arr[arr.length-1] -arr[0];// binary search always applied on search space and not the elements
        int ans = 0;
        while(lo<=high){
            int mid = lo + (high - lo )/2;
            if(!cowAssign(arr, cows,mid)){
                high = mid-1;
            }else{
                ans = mid;
                lo = mid +1;
            }
        }
        return ans;

    }

}

HERE IS MY CODE

lo<=high

FACING SITUATION HERE

#6

Please reply( just appraoching character limit)

#7

@bhavik911,
I see that you have the correct answer on this one. Do you have any further doubts?

#8

Hey I solved the problem but I was facing a situation that my left and right were not converging , for all the questions I solved till now they were converging , I changed my code after a lot of debugging and got the right one . But then I checked but the editorial and find out they have mentioned a similar issue of doing s+1<e ;
can you please explain why we have to do this , I am really confused . Please explain

This one , I posted it above too with a image

#9

@bhavik911,
In case the condition is true and value of mid i.e. (s+e)/2 remains constant and s<e. This condition (s<e) will always be true.

if s =3, e=4, and it is valid, mid will be 3 and s will keep on setting to 3 while e=4. Hence TLE error

#10

So how should I keep this in mind always?
Like till now I never used s+1<e,
Should i check in each case whether it will cause TLE?

#11

if it causes TLE, no harm in trying for s+1<e

#12

So before approaching should I always check for this till now I was only doing lo<=high
??

#13

this is just a one off case to give you a sense that low<=high might now always work. Don’t worry, it will be rare but it can happen

1 Like
#14

okay cool thanks(abcdefg)