# Google Kickstart Round A 2019 - Training

Problem: Training

As the football coach at your local school, you have been tasked with picking a team of exactly P students to represent your school. There are N students for you to pick from. The i-th student has a skill rating Si, which is a positive integer indicating how skilled they are.

You have decided that a team is fair if it has exactly P students on it and they all have the same skill rating. That way, everyone plays as a team. Initially, it might not be possible to pick a fair team, so you will give some of the students one-on-one coaching. It takes one hour of coaching to increase the skill rating of any student by 1.

The competition season is starting very soon (in fact, the first match has already started!), so you'd like to find the minimum number of hours of coaching you need to give before you are able to pick a fair team.

Input

The first line of the input gives the number of test cases, T. T test cases follow. Each test case starts with a line containing the two integers N and P, the number of students and the number of students you need to pick, respectively. Then, another line follows containing N integers Si; the i-th of these is the skill of the i-th student.

Output

For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1) and y is the minimum number of hours of coaching needed, before you can pick a fair team of P students.

Limits

• Time limit: 15 seconds per test set.
• Memory limit: 1 GB.
• 1 ≤ T ≤ 100.
• 1 ≤ Si ≤ 10000, for all i.
• 2 ≤ P ≤ N.
• Test set 1 (Visible)
• 2 ≤ N ≤ 1000.
• Test set 2 (Hidden)
• 2 ≤ N ≤ 105.

Sample

Input

3
4 3
3 1 9 100
6 2
5 5 1 2 3 4
5 5
7 7 1 7 7


Output

Case #1: 14
Case #2: 0
Case #3: 6


In Sample Case #1, you can spend a total of 6 hours training the first student and 8 hours training the second one. This gives the first, second and third students a skill level of 9. This is the minimum time you can spend, so the answer is 14.

In Sample Case #2, you can already pick a fair team (the first and second student) without having to do any coaching, so the answer is 0.

In Sample Case #3, P = N, so every student will be on your team. You have to spend 6 hours training the third student, so that they have a skill of 7, like everyone else. This is the minimum time you can spend, so the answer is 6.

My solution

#include <iostream>
#include <vector>
#include <algorithm>

void getData(int &p, std::vector<int> &skills) {
int n;
std::cin >> n >> p;
skills.reserve(n);
for (int i = 0; i < n; i++) {
int skill = 0;
std::cin >> skill;
skills.emplace_back(skill);
}
}

int minTrainingTime(std::vector<int> &skills, int p) {
std::sort(skills.begin(), skills.end());
int low = 0, high = p - 1;

int currentResult = 0;
for (int i = 0; i < high; i++) {
currentResult += skills[high] - skills[i];
}

int minResult = currentResult;
int remainingPossibilities = skills.size() - p;
for (int i = 0; i < remainingPossibilities; i++) {
currentResult -= skills[++high] - skills[low++];
currentResult += p * (skills[high] - skills[high - 1]);
minResult = std::min(minResult, currentResult);
}

return minResult;
}

int main() {
int t = 0;
std::cin >> t;
for (int testCase = 0; testCase < t; testCase++) {
int p;
std::vector<int> skills;
getData(p, skills);

std::cout << "Case #" << testCase + 1 << ": " << minTrainingTime(skills, p) << std::endl;
}
}


Analysis

Time complexity: $$\O(n\log n)\$$, dominated by sorting

Space complexity: $$\O(1)\$$, not counting the original data given by the problem

First of all, this looks good to me! I have some minor comments.

• Consider compiling with -Wconversion. It will give you a couple of hints where you implicitly convert between std::vector::size_type (usually std::size_t) and int. Whether you work with unsigned data types for skills and quantities might be a matter of taste, but I think you should be aware of the conversion issue. Also, this compiler flags gives you (on my machine)

implicit conversion loses integer precision: unsigned long to int [-Wshorten-64-to-32]

int remainingPossibilities = skills.size() - p;


which should definitely worth tackling even if the problem description specifies input characteristics that make a digit loss impossible.

• Not that this will be an issue for this example, but when you want to be as fast as possible, don't use <iostream>, but <cstdio> instead.

Input handling/parameter types

• When retrieving the input data, don't pass non-const references, but prefer returning by value instead. (N)RVO will make sure there is no overhead. As you have more than one value, define a small, custom type for this. So, I'd suggest going with

struct TestCaseInput {
int nToChoose;
std::vector<int> skills;
};

TestCaseInput getData();
int minTrainingTime(TestCaseInput& input);


cf. the Core Guidelines on this topic, F.20 and F.21

• std::vector::emplace_back makes sense when you can in-place construct an object with given parameters, but when you pass the already existing object to this function, it's probably clearer to use push_back. In the case of an integral value, it doesn't matter anyhow whether you move-construct or copy it. As an alternative, you could also

std::vector<int> skills(n); // Allocates and set all values to zero

for (int i = 0; i < n; i++)
std::cin >> skills[i]; // No temporary variable required


And also have a look at the combination of std::copy_n and std::istream_iterator that @papagaga suggests to eliminate the manual loop here.

Main function minTrainingTime

• In the first loop, you read skills[high] in every iteration, even though this value doesn't change. Instead, just read it once and save it in a variable. Or, leave it as it is and verify that the compiler optimizes this away anyway.

• You can also replace this whole first loop by including <numeric> and using std::accumulate with an initial value high*skills[high] and std::minus<>{} as the binary operation parameter.

• If you can const-qualify a variable, do so:

const int remainingPossibilities = skills.size() - p;

• But if can alternative reduce the scope of such a variable and by that even eliminate another one (the loop counter i), do so instead (as long as the negative influence on the readability is not too big, which I think is ok here):

// remainingPossibilities is now superfluous, just use the for loop for
// the initialization and count differently:
for (int n = skills.size() - p; n != 0; n--) { /* ... */ }

• You might want to consider an additional level of indirection for the function minTrainingTime here, as it can equally well operate on random access iterators instead of indices. This way, you eliminate the dependency of this function on the actual value type that you are using (which also considerably reduces the number of -Wconversion warnings at one go), as well as the dependency on the container type. Using some of the above hints, the resulting function template looks e.g. like this:

template <class RandomAccesIt, class T>
auto minTrainingTime(RandomAccesIt first, RandomAccesIt last, T p)
{
using value_type = typename RandomAccesIt::value_type;
auto low = first, high = std::next(first, p - 1);
const value_type init = std::distance(low, high)*(*high);

value_type currentResult = std::accumulate(first, high, init, std::minus<>{});
value_type minResult = currentResult;

for (auto n = std::distance(first, std::prev(last, p)); n != 0; --n) {
currentResult -= *++high - *low++;
currentResult += p*(*high - *std::prev(high));
minResult = std::min(minResult, currentResult);
}

return minResult;
}


and can be deduced and invoked by minTrainingTime(skills.begin(), skills.end(), p).

• Excellent, I just want to suggest using std::copy_n and an std:istream_iterator in getData rather than an explicit loop: auto get_data(int n) { std::vector<int> skills(n); std::copy_n(std::istream_iterator<int>(std::cin), n, skills.begin()); return skills; } – papagaga Mar 27 at 10:43
• @papagaga Good suggestion! I'll add a hint to your comment in the answer. – lubgr Mar 27 at 10:46
• Good except that advocating <cstdio> for performance here is like advocating using void * instead of objects; probably a dubious fix to a nonexistent problem. – Edward Apr 9 at 10:02
• @Edward I find the comparison a bit drastic, but I do see the point :) – lubgr Apr 9 at 10:09