ITACPC Sample Problem

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!

Scenic Walkway

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 H[i] meters. Together with the attraction, they also plan to build a scenic walkway following most of the chambers from the outside.

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!

The first line contains the two integers N and K. The second line contains N integers H[i].

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

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

6 2
50 60 80 40 10 80
					

10 3
67 90 22 79 95 89 76 21 65 99
					

0
					

6
					

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.

Let's see some code!

C++ Solution

#include <algorithm>
#include <iostream>
#include <vector>
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.

Python 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

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.