Max Min · Coding Gym

Solutions

The problem reduces to choosing K consecutive numbers in a sorted list for which the value of D is minimum. Which can be easily done by sorting the given number and calculating D for each group of K consecutive number.

Here is a possible C++ Solution:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24


#include <iterator>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <climits>
using namespace std;

int main()
{
    int N, K; cin >> N >> K;
    vector<int> v(N);
    copy_n(istream_iterator<int>(cin), N, begin(v));
    sort(begin(v), end(v));
    auto tail = 0; auto head = K-1;
    auto unfairness = INT_MAX;
    while (head<N)
    {
        unfairness = min(unfairness, v[head]-v[tail]);
        tail++;
        head++;
    }
    cout << unfairness;
}

This results in a combination of zip | map | reduce patterns that in C++ can be written in terms of inner_product:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20


#include <iterator>
#include <vector>
#include <iostream>
#include <algorithm>
#include <numeric>
using namespace std;

int main()
{
    int N, K; cin >> N >> K;
    vector<int> v; v.reserve(N);
    copy_n(istream_iterator<int>(cin), N, back_inserter(v));
    sort(begin(v), end(v));
    K-=1;
    cout << inner_product(
                v.begin()+K, v.end(),
                v.begin(), numeric_limits<int>::max(),
                [](auto... a) { return min(a...); },
                std::minus<int>() );
}

This haskell solution creates N-K+1 sublists of length K, and calculate the minimum and the maximum of each sublist. The complexity is K * (N - K + 1) and some tests fail due to timeout.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


import Data.List (sort)

sublists k xs =
  take k xs :
  if length xs > k
    then sublists k (tail xs)
    else []

unfairness ys = maximum ys - minimum ys

minUnfairness k xs = minimum $ unfairness <$> sublists k xs

main = do
  _:k:xs <- fmap read . lines <$> getContents
  print $ minUnfairness k (sort xs)

This haskell solution take advantage of the sorted list. We don’t need to keep all the items in the sublists, but only extremities, of which one element is the minimum and the other is the maximum.

To do this, we zip the sorted list, with a copy where the first K-1 elements are missing.

Example with k=3

1
2
3
4
5


    ------  10  20  30 100  200 300 1000
    10  20  30 100 200 300 1000 --------

            20  80 170 200  800
            ^^

zipWith (-) generates a new list with the difference of the two lists. When we have such list, we just need to find the minimum.

1
2
3
4
5
6
7


import Data.List (sort)

minUnfairness k xs = minimum $ zipWith (-) (drop (k - 1) xs) xs

main = do
  _:k:xs <- fmap read . lines <$> getContents
  print $ minUnfairness k (sort xs)

patterns sort functional