Xtreme 10.0 Walking Dogs

This is an interesting question. Without going around I will just quote the question from Hackerrank.

Your friend, Alice, is starting a dog walking business. She already has K dog walkers employed, and today there are N dogs that need to be walked. Each dog walker can walk multiple dogs at the same time, so the dogs will be arranged into K nonempty groups, and each group will then be walked by a single dog walker. However, smaller dogs can be aggressive towards larger dogs, and that makes it harder to walk them together.

More formally, if the smallest dog in a group has size a, and the largest dog in the group has size b, then the range of the group is defined as b-a. In particular, the range of a group consisting of a single dog is 0. The smaller the range of a group is, the easier it is to walk that particular group. Hence Alice would like to distribute the dogs among the dog walkers so that the sum of ranges of the groups is minimized. Also, since she doesn’t want any of the dog walkers to feel left out, she makes sure each dog walker gets to walk at least one dog.

Given N, K and the sizes of the dogs, can you help Alice determine what is the minimum sum of ranges over the K groups if the dogs are arranged optimally?

Input Format

The first line of input contains t, 1 ≤ t ≤ 5, which gives the number of test cases.

Each test case starts with a line containing two integers N, the number of dogs, and K, the number of employees, separated by a single space. Then N lines follow, one for each dog, containing an integer x representing the size of the corresponding dog.

Constraints

1 ≤ K ≤ N ≤ 10⁵, 0 ≤ x ≤ 10⁹

Output Format

For each test case, you should output, on a line by itself, the minimum sum of ranges over the K groups if the dogs are arranged optimally.

Link to the above question(You may need to sign up to the IEEE practice community): https://www.hackerrank.com/contests/ieeextreme-challenges/challenges/dog-walking

So go ahead try it by yourself, and come back here later, if you can’t find the solution! (unless you have tried it already!)

If you haven’t tried to solve the above question by yourself I strongly recommend not to read any further. Go away!

Okay, you are still reading that means you are prepared for the risk.

Let me warn you again, once you read the answer you don’t have much to think of… :(

The Solution

Please mind that what I am writing here is the way I solved it, there may exist better solutions.

The idea is to divide the given set of numbers(dogs) into groups while minimizing the sum of ranges.

One way is to make all possible groups using the given sets of dogs and check their sum of ranges and find their minimum one and print it! Unfortunately people here , don’t like small numbers. Simply they don’t work with small amount of dogs. If you check the above example the number of dogs can be gone up to 10⁵. If you think of the possible number of groups for that it will be almost infinity ;)

Let me ask you something, if the number of possible groups is 1 what is the answer? Then we can make only one group, that means the range of that group is the answer.

What if we make two groups, we got to divide above group into two groups optimally. From where do we break the group into two?

To answer that we need to sort dogs(numbers). Let’s think our sorted list of numbers looks like below,

A1, A2, A3, …… Ai, A(i+1)….. An

• A1 — Size of the smallest dog
• An — Size of the largest dog

Number of groups is 1: Sum of ranges(S): S=An-A1

Number of groups is 2: We have to split the above list into two lists. Let’s think if we divide it from Ai, A(i+1). New sum of ranges will be,

S = (Ai-A1) + (An-A(i+1))

If we re arrange the above equation like following,

S = (An-A1)- (A(i+1)-Ai)

What this equation says is that new sum of ranges will be equal to previous sum of ranges minus the difference between A(i+1) and Ai. This gives you a very clear statement on where to split. If we want to reduce the sum of range we have to split it from the place where the A(i+1)-Ai is maximum.

Number of groups is 3:

Let sizes be like,

A1, A2…. Ai, A(i+1),…. Aj, A(j+1),….An

S = (Ai-A1) + (Aj-A(i+1)) + (An-A(j+1))

When we simplify,

S = (An-A1)-((A(i+1)-Ai)+(A(j+1)-Aj))

To minimize S we need to maximize A(i+1)-Ai as well as A(j+1)-Aj. So to solve the above question what you have to do is to find the places which has maximum differences. Find the maximum values for A(i+1)-Ai and reduce them from the An-A1.

Steps

• Sort the list of sizes of dogs.
• Calculate the differences of each consecutive values in the list. You will get an array of size n-1. Let me call this difference list.
• Sort the difference list.
• If the number of groups required is G. Take G-1 maximum values from the difference list.
• Calculate the sum of maximum values.
• Reduce if from An-A1.
• You are done!

Here is my code,

Example

2
4 2
3
5
1
1
5 4
30
40
20
41
50

Consider the 2nd test case. There are 5 dogs and we have to divide them into 4 groups.

Sizes: 30, 40, 20, 41, 50

Sort them first,

Sizes(Sorted): 20, 30, 40, 41, 50

Calculate differences,

Differences: 10, 10, 1, 9

Sort Differences,

Differences(sorted): 1, 9, 10, 10

Since we have to make 4 groups, we need to take the highest 3 values (4–1=3) from the sorted difference list and reduce it from the maximum range(50–20).

Answer = (50 - 20) - sum(9,10,10)
       = 30 - 29
       = 1

Lets see how groups are distributed. We split at 9, 10, 10. That means, splits happen at,

• 20|30
• 30|40
• 41|50.

So groups are,

(20), (30), (40, 41), (50)

That’s it then,

Hope you have enjoyed the post! and thank you very much for reading.