Every year the cows hold an event featuring a peculiar version of hopscotch that involves carefully jumping from rock to rock in a river. The excitement takes place on a long, straight river with a rock at the start and another rock at the end, L units away from the start (1 <= L <= 1,000,000,000). Along the river between the starting and ending rocks, N (0 <= N <= 50,000) more rocks appear, each at an integral distance Di from the start (0 < Di < L).

To play the game, each cow in turn starts at the starting rock and tries to reach the finish at the ending rock, jumping only from rock to rock. Of course, less agile cows never make it to the final rock, ending up instead in the river.

Farmer John is proud of his cows and watches this event each year. But as time goes by, he tires of watching the timid cows of the other farmers limp across the short distances between rocks placed too closely together. He plans to remove several rocks in order to increase the shortest distance a cow will have to jump to reach the end. He knows he cannot remove the starting and ending rocks, but he calculates that he has enough resources to remove up to M rocks (0 <= M <= N).

FJ wants to know exactly how much he can increase the shortest distance *before* he starts removing the rocks. Help Farmer John determine the greatest possible shortest distance a cow has to jump after removing the optimal set of M rocks.

INPUT FORMAT:

Line 1: Three space-separated integers: L, N, and M

Lines 2..N+1: Each line contains a single integer indicating how far some rock is away from the starting rock. No two rocks share the same position.

OUTPUT FORMAT:

Line 1: A single integer that is the maximum of the shortest distance a cow has to jump after removing M rocks

SAMPLE INPUT:

25 5 2
2
14
11
21
17

SAMPLE OUTPUT:

4

This is also a binary search question, if you think about it; if you know that every rocks are at least d distance apart after removing some rocks, then if the amount of rocks you remove are smaller than M, then the maximum d you can obtain would be the answer for this question.

Here’s my code:

//
//  main.cpp
//  제자리 멀리뛰기
//
//  Created by Shin Lee on 24/03/2020.
//  Copyright © 2020 Shin Lee. All rights reserved.
//

#include <bits/stdc++.h>
using namespace std;
int n, d, m; int arr[50005];int dist[50005];
int main(){
    cin >> d >> n >> m;
    for(int i=0;i<n;i++){
        cin >> arr[i];
    }
    arr[n]=0; arr[n+1]=d;
    sort(arr,arr+n+2);
    
    int hi = d, lo = 1;
    while(hi>lo){
       // printf("hi = %d, lo = %d\n",hi,lo);
        int mid = (hi+lo+1)/2;
        int pos=0;int cnt=0;
        for(int i=1;i<=n+1;i++){
            if(arr[i]-arr[pos]<mid){

                cnt++;
            }else {
                pos = i;
            }
        }
        if(cnt<=m){
            lo = mid;
        }else hi = mid-1;
        
    }
    cout << lo;
    
}

Farmer John is hosting a new bovine grass-eating convention at his farm!

Cows from all over the world are arriving at the local airport to attend the convention and eat grass. Specifically, there are N cows arriving at the airport (1≤N≤10^5) and cow ii arrives at time Ti (0≤Ti≤10^9). Farmer John has arranged M (1≤M≤10^5) buses to transport the cows from the airport. Each bus can hold up to C cows in it (1≤C≤N). Farmer John is waiting with the buses at the airport and would like to assign the arriving cows to the buses. A bus can leave at the time when the last cow on it arrives. Farmer John wants to be a good host and so does not want to keep the arriving cows waiting at the airport too long. What is the smallest possible value of the maximum waiting time of any one arriving cow if Farmer John coordinates his buses optimally? A cow’s waiting time is the difference between her arrival time and the departure of her assigned bus.

It is guaranteed that MC≥N.

INPUT FORMAT (file convention.in):

The first line contains three space separated integers N, M, and C. The next line contains N space separated integers representing the arrival time of each cow.

OUTPUT FORMAT (file convention.out):

Please write one line containing the optimal minimum maximum waiting time for any one arriving cow.

SAMPLE INPUT:

6 3 2
1 1 10 14 4 3

SAMPLE OUTPUT:

4

If the two cows arriving at time 1 go in one bus, cows arriving at times 3 and 4 in the second, and cows arriving at times 10 and 14 in the third, the longest time a cow has to wait is 4 time units (the cow arriving at time 10 waits from time 10 to time 14).

Problem credits: Grace Cai

This one was another question where I couldn’t directly think of the solution at the first look. There are a lot of questions that blind me like this… 😦

At first, I was focusing on how I was going to divide the cows into cars; and coding that way might work, but for me it was way too overworking.

The solution that I used, eventually, was Binary Search; if we search through numbers and look for the minimum maximum amount of time the cow will wait, we’ll be able to solve the problem.

Here’s the code that I wrote:

//
//  main.cpp
//  convention
//
//  Created by Shin Lee on 03/01/2020.
//  Copyright © 2020 Shin Lee. All rights reserved.
//

#include <bits/stdc++.h>
using namespace std;
int n, m, c;
const int SIZE = 1e5+5;
int arr[SIZE];
int main() {
    //freopen("convention.in","r",stdin);
    //freopen("convention.out","w",stdout);
    cin >> n >> m >> c;
    for(int i=0;i<n;i++){
        cin >> arr[i];
    }
    sort(arr,arr+n);
    
    
    int low = 0, hi = 1e9;
    while(low<hi){
        
        int cnt=1, ans=1, cur=arr[0], mid = (low+hi)/2;
        //printf("looking at %d\n",mid);
        
        
        
        for(int i=1;i<n;i++){
            //printf("looking at pos %d\n",arr[i]);
            
            if(cnt>=c){
                //printf("over capacity\n");
                ans++;
                cur = arr[i];
                cnt=1;
            }
            else if(arr[i]-cur<=mid){
                cnt++;
            }
            else{
                //printf("over range\n");
                ans++;
                cur=arr[i];
                cnt=1;
            }
            
            
            
            
            
            //printf("ans = %d, cnt = %d\n",ans,cnt);
        }
        
        //printf("final ans at %d is %d\n",mid,ans);
        if(ans<=m){
            hi = mid;
        }else low = mid+1;
        //printf("\n\n\n");
    }
    
    cout << low;
    return 0;
}