AIO 2021 Q4: Social Distancing

Contest Source: AIO 2021

This problem can be done using greedy. Sort the dishes, then place the first hippo on the leftmost dish, the second hippo on the first dish that is K away from the first hippo, the third hippo on the first dish that is K away from the second hippo, and so on. Repeat this until there are no more valid dishes, and return the number of hippos placed as the optimal number of hippos. This runs in \(O(N)\) time.

The reason why this works is as follows. Consider any valid optimal assignment of hippos to dishes (not necessarily using our greedy method). Then if the first hippo from the left is not on the first dish already, then he can be moved so that he is on the first dish without breaking social distancing rules. Afterwards, the second hippo then can also be moved to the first dish that is of distance \(K\) from the first hippos new location without breaking social distance laws. We can repeat this for the third, fourth, fifth hippos and so on, until all hippos are ‘aligned to the left’. In other words, any optimal assignment of hippos can always be transformed into the assignment given by our greedy algorithm, so we know our greedy algorithm is optimal.

#include <bits/stdc++.h>
using namespace std;

int main () {
    freopen("distin.txt", "r", stdin);
    freopen("distout.txt", "w", stdout);

    int N, K;
    cin >> N >> K;

    int dishes[N];
    for (int i = 0; i < N; i++) cin >> dishes[i];

    // sort dishes from left to right
    sort(dishes, dishes+N);

    // greedily assign as many hippos as possible
    int cnt = 0;
    int last_hippo = INT_MIN/2; // our 'last hippo' is at negative infinity
    for (int i = 0; i < N; i++) {
        if (dishes[i]-last_hippo >= K) {
            // if current dish is far enough away from the last hippo, place the new hippo here
            last_hippo = dishes[i];
            cnt++;
        }
    }

    printf("%d\n", cnt);
}