Lost array

Submit solution

Points: 100 (partial)
Time limit: 1.0s
Python 3 8.0s
Memory limit: 256M

Problem type

In this problem an array \(A\) of \(N\) integers (possibly negative) is hidden from you. We will give you instead an array \(S\) such that \(S_i = \sum_{j = 0}^{k-1} A_{i+j}\). We want you to output the difference between the largest and smallest elements of \(A\).

Because there is a lot of possible answers, we want you to output the one minimizing that difference.

Input Specification

The first line of the input file contains one integer \( 1 \leq T \leq 30 \): the number of test cases.

Each test case starts with a line with two integers \(N\) and \(K\) (\(1\leq K \leq N \leq 10^5\)).

The second line contains \(N - K + 1\) space separated integers \(S_i\) (\( -10^6 \leq S_i \leq 10^6\)).

Output Specification

For each test case output one line containing the answer to the problem.


  • (\(30\) points) \(N ≤ 100\).
  • (\(30\) points) \(N ≤ 1000\).
  • (\(40\) points) No additional constraint.

Sample Input

5 2
1 0 0 1
4 3
1 0

Sample Output



One possible array \(A\) corresponding to the first test case is : \([1,0,0,0,1]\) and to the second one : \([1,0,0,0]\).

The array \([2,0,-1,1]\) corresponds to the array \(S\) of the second sample, but it does not minimize the difference between the largest and smallest elements.


There are no comments at the moment.