## A sample problem, from the past online rounds:

# “Scenic Walkway”

*In this page we will show you a sample problem that reflects*

**the type of problems**you will be asked to solve during a typical ITACPC round, and we will also present a possible solution implemented in**Python**, in**Java**and in**C++**. Remember that the tasks will always be presented in a random order (not in increasing order of difficulty!) so it's important to**read all the tasks**to find which tasks are the easiest; the amount of time that your team will take to solve the tasks**will be counted**towards the final ranking!# 📄 Problem Description 🤔

**Time Limit:**2 seconds —

**Memory Limit:**128 MiB

The managers of Gardaland Theme Park are building a new attraction, consisting of a sequence of * N* chambers of horrors, each located at a different height of

* meters. Together with the attraction, they also plan to build a scenic walkway following most of the chambers from the outside.*

**H[i]**In order to maximise the visibility of the new attraction, they need to carefully plan the altitude at which to build the walkway. For this reason they hired Giorgio, who calculated that it would be best if at least **K**** **chambers were clearly visible from the walkway. Given a set of chambers, define its *spread* as the difference between the highest and the lowest chamber in the set. Find the smallest possible spread for a set of * K* chambers!

### Input:

The first line contains the two integers * N* and

*. The second line contains*

**K***integers*

**N***.*

**H[i]**### Output:

You need to write a single line with an integer: the smallest possible spread for a set of * K* chambers.

### Constraints:

**2 ≤***K*≤*N*≤ 1,000,000**0 ≤**for each*H[i] ≤*1,000,000**i=0…***N-1*

### Sample testcases:

**Input:**

`6 2`

`50 60 80 40 10 80`

**Output:**

`0`

**Input:**

`10 3`

`67 90 22 79 95 89 76 21 65 99`

**Output:**

`6`

### Explanation of sample testcases:

In the **first sample case** it's possible to obtain a spread of 0 by choosing K=2 chambers that have the same heights: 80, 80.

Clearly, this is the best result possible (we can't go below 0).

In the **second sample case** it's *not possible* to obtain a spread of 0 because all the chambers have different heights.

However, it's possible to reach a spread of 6 by choosing the chambers with heights: 90, 95, 89.

We can see (e.g. by trying all of them) that *there is no other set *of K=3 chambers that can give us a spread of 5, so the spread 6 is indeed **optimal**!

# 👇 Here is the Solution! 💡

An obvious solution would be to **try all the possible sets of K elements**. We will see that this solution is actually incredibly slow, and it also proves quite difficult to implement in languages such as C++ (in Python it's quite easy because of its rich standard library, see: itertools.combinations).

As it usually happens, “obvious” solutions are often wrong (or too slow). In fact, here the number of possible combinations of K elements from a set of N elements can become **huge**. In the example above, with N=10 and K=3, we only have **120** possible combinations. If we increased to N=30 and K=15 we would have more than **150 million **combinations! Solving such a testcase is probably still feasible within the time limit, but what's the **worst possible** testcase?

From the “Constraints” section of the problem description (and from a quick look at Pascal's triangle) we can see that the worst possible case is when **N=1000000 **and **K=500000**. In that case, the number of combinations will be around **10³⁰¹⁰²⁶**, yes, that number is “1” followed by *301026 *zeroes!

For perspective, the *observable universe* is estimated to “only” have around **10⁸⁰** atoms.

### Let's do it faster

Let's take the example with * N=10* and the following heights (the solution, with spread 6, is marked):

67, **90**, 22, 79, **95, 89**, 76, 21, 65, 99

Let's **sort **the heights in increasing order (but we will see that also decreasing order is OK):

21, 22, 65, 67, 76, 79, **89**, **90**, **95**, 99

Now that the numbers are **sorted**, we can easily see that it's **never a good idea **to choose K chambers which **are not consecutive **in the sorted array. Why is that? Well, because if we chose a non-consecutive set then it would obviously be possible to **reduce its spread **by replacing some chamber!

This leads us to a **much faster **solution: just sort the numbers and then test all the (N-K+1) possible “windows” of K consecutive elements.

## C++ Solution

`#include <bits/stdc++.h>`

`using namespace std;`

`int main() {`

` int N, K;`

` cin >> N >> K;`

` vector<int> v(N);`

` for (int i = 0; i < N; ++i) {`

` cin >> v[i];`

` }`

` sort(v.begin(), v.end());`

` int best = 1000000000;`

` for (int i = 0; i < N - K + 1; ++i) {`

` best = min(best, v[i + K - 1] - v[i]);`

` }`

` cout << best << endl;`

`}`

In our tests, this solution runs in just under 0.5 seconds (and uses 5 MiB of RAM) on the hardest testcases we have.

## Python3 Solution

`N, K = map(int, input().split())`

`v = list(map(int, input().split()))`

`v.sort()`

`best = 10**9`

`for i in range(N - K + 1):`

` best = min(best, v[i + K - 1] - v[i])`

`print(best)`

In our tests, this solution runs in just under 2 seconds (and uses 118 MiB of RAM) on the hardest testcases we have.

## Java Solution

`/* package whatever; // don't place package name! */`

`import java.io.BufferedReader;`

`import java.io.IOException;`

`import java.io.InputStreamReader;`

`import java.util.Arrays;`

`import java.util.StringTokenizer;`

`public class Main // class name should be "Main"`

`{`

` public static void main(String[] args) throws IOException`

` {`

` BufferedReader br = new BufferedReader(new InputStreamReader(System.in));`

` StringTokenizer st;`

` // Read line #1`

` st = new StringTokenizer(br.readLine());`

` int N = Integer.parseInt(st.nextToken());`

` int K = Integer.parseInt(st.nextToken());`

` // Read line #2`

` st = new StringTokenizer(br.readLine());`

` int[] v = new int[N];`

` for (int i = 0; i < N; i++) {`

` v[i] = Integer.parseInt(st.nextToken());`

` }`

` Arrays.sort(v);`

` int best = 1000000000;`

` for (int i = 0; i < N - K + 1; i++) {`

` best = Math.min(best, v[i + K - 1] - v[i]);`

` }`

` System.out.println(best);`

` }`

`}`

In our tests, this solution runs in about 1.5 seconds (and uses 104 MiB of RAM) on the hardest testcases we have.