The Coding Culture
Published in

The Coding Culture

KIDEE1: Kids at home

In this blog, we will look at how you could approach the problem “Kids at home” in The Coding Culture’s November Contest “Get Set and Code”.

Understanding the problem statement

The statement reads as follows:

k kids seem to have visited your home for the festival. It seems like the kids had all been fighting with each other, so you decided to keep them as far as possible from each other. You had placed n chairs on the positive number line, each at position xi , 1 ≤ i ≤ n. You can make the kids sit in any of the chairs. Now you want to know the largest possible minimum distance between each kid.

So, we are given n chairs to place a kid on a positive number line at positions x1, x2, x3, x4, …, xn. Lets say we sort this list so that x1 < x2 < x3 < x4 < … < xn. Well, what are we trying to achieve then? Let’s say we place all kids on some chairs, say kid_i is placed at q_i x1, x2, x3, …, xn and q_i != q_j for all i and j (i.e, no two kids can sit at the same chair), lets also arrange q_i in increasing order, then min_{i = 2..k} |q_i — q_{i-1}| is the minimum distance between all the kids.
Our goal is to place the kids in such a way as to maximize this distance.

Key insight #1

The first insight you’ll get after thinking through for a bit is that it is easy to check whether some minimum distance , m, is possible. This can be done through a greedy routine described below:

1. Place a kid on the first chair(x1)
2. Find a chair that is at least m units away from the previous chair, and place another kid there
3. Repeat step 2 till you either run out of kids or run out of chairs
4. If you run out of kids, then that minimum distance is possible. Instead if you run out of chairs, then that minimum distance is not possible.

This insight lets you convert this problem to a searching problem. Now our goal is to search for that m such that m+1is not possible.

Algorithm #1 : O(k max{|x_i — x_1|}) solution

It is easy to see that the above described algorithm takes O(k) time to perform a single query. Performing a linear search in the range of |x_2-x_1| to |x_1- x_n|. This algorithm ends up being too slow tho.

Key insight #2

The next important thing you need to observe is that, our greedy routine to check if a minimum distance is possible is monotonic in nature. That means, say our maximum possible minimum distance is some m, then it is always possible to have a minimum distance less than m and not possible to have minimum distance greater than m. This means you can binary search over our search space. This give you an efficient solution that run on O(k max{|x_i-x_1|}) time.

Final Algorithm / Solution

#include <bits/stdc++.h>
using namespace std;
bool checkForMinDistance(vector<long long> xi, long long k, long long minDistance) {
long long i = xi[0];
k--; // place first kid
for (long long x : xi) {
if (x - i >= minDistance) {
k--;
i = x;
}
if (k == 0)
return true;
}
return false;
}
int main() {
int t;
cin >> t;
while(t--) {
long long n, k;
cin >> n >> k;
vector<long long> xi(n);
for (auto &x : xi) cin >> x;
sort(xi.begin(), xi.end());long long l = 1, r = xi[n - 1];
long long mid = l + (r - l) / 2;
while (r - l > 1) {
if (checkForMinDistance(xi, k, mid) == 1)
l = mid;
else
r = mid;
mid = l + (r - l) / 2;
}
cout << mid << endl;
}
return 0;
}

Further Reading

Errichto’s binary search tutorial: https://www.youtube.com/watch?v=GU7DpgHINWQ

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store