Problem G
Tree Shopping

Source: Cliparts

Andy is going holiday shopping and needs to buy several Christmas trees. At the store, there is a row of Christmas trees of various heights. Andy is only allowed to buy trees that are next to each other, i.e. trees that are contiguous within the row. He also wants to make sure that the shortest tree he buys and the tallest tree he buys are as close in height as possible. What is the smallest height difference he can get given the constraints?


The input consists of two lines. The first line contains two integers $n$ and $k$ ($2 \leq k \leq n \leq 200\, 000$), representing the number of trees in the row and the number of trees Andy needs to buy, respectively. The second line consists of $n$ integers $a_1, a_2, \ldots , a_ n$ where $1 \leq a_ i \leq 100$, representing the height of each tree.


Output the minimum height difference between the shortest and tallest trees of any contiguous subrange of $k$ trees.

Sample Input 1 Sample Output 1
10 2
1 3 5 7 9 11 13 15 17 16
Sample Input 2 Sample Output 2
5 4
1 1 3 5 6
CPU Time limit 2 seconds
Memory limit 1024 MB
Statistics Show
Andrew Ahnn
Source 2019 Virginia Tech High School Programming Contest (Practice)
License Creative Commons License (cc by-sa)

Please log in to submit a solution to this problem

Log in