Chopping Carrots (Easy Version) (Codeforces 1706D1)
Tags: Greedy, number theory

This is the easy version of the problem. The only difference between the versions is the constraints on $$$n$$$, $$$k$$$, $$$a_i$$$, and the sum of $$$n$$$ over all test cases. You can make hacks only if both versions of the problem are solved.Note the unusual memory limit.You are given an array of integers $$$a_1, a_2, \ldots, a_n$$$ of length $$$n$$$, and an integer $$$k$$$.The cost of an array of integers $$$p_1, p_2, \ldots, p_n$$$ of length $$$n$$$ is $$$$$$\max\limits_{1 \le i \le n}\left(\left \lfloor \frac{a_i}{p_i} \right \rfloor \right) - \min\limits_{1 \le i \le n}\left(\left \lfloor \frac{a_i}{p_i} \right \rfloor \right).$$$$$$Here, $$$\lfloor \frac{x}{y} \rfloor$$$ denotes the integer part of the division of $$$x$$$ by $$$y$$$. Find the minimum cost of an array $$$p$$$ such that $$$1 \le p_i \le k$$$ for all $$$1 \le i \le n$$$.

Input: The first line contains a single integer $$$t$$$ ($$$1 \le t \le 100$$$) — the number of test cases.The first line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le n, k \le 3000$$$).The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_1 \le a_2 \le \ldots \le a_n \le 3000$$$).It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$3000$$$.

Output: For each test case, print a single integer — the minimum possible cost of an array $$$p$$$ satisfying the condition above.

Note: In the first test case, the optimal array is $$$p = [1, 1, 1, 2, 2]$$$. The resulting array of values of $$$\lfloor \frac{a_i}{p_i} \rfloor$$$ is $$$[4, 5, 6, 4, 5]$$$. The cost of $$$p$$$ is $$$\max\limits_{1 \le i \le n}(\lfloor \frac{a_i}{p_i} \rfloor) - \min\limits_{1 \le i \le n}(\lfloor \frac{a_i}{p_i} \rfloor) = 6 - 4 = 2$$$. We can show that there is no array (satisfying the condition from the statement) with a smaller cost.In the second test case, one of the optimal arrays is $$$p = [12, 12, 12, 12, 12]$$$, which results in all $$$\lfloor \frac{a_i}{p_i} \rfloor$$$ being $$$0$$$.In the third test case, the only possible array is $$$p = [1, 1, 1]$$$.

Sample Inputs:
7
5 2
4 5 6 8 11
5 12
4 5 6 8 11
3 1
2 9 15
7 3
2 3 5 5 6 9 10
6 56
54 286 527 1436 2450 2681
3 95
16 340 2241
2 2
1 3

Sample Outputs:
2
0
13
1
4
7
0

Solution (Python):
for _ in range(int(input())):
    (N, K) = map(int, input().split())
    a = [*map(int, input().split())]
    ps = [0] * (10 ** 5 + 10)
    for i in range(N):
        (pv, j) = (10 ** 9, 1)
        while j <= min(a[i], K):
            nv = a[i] // j
            ps[nv + 1] = max(ps[nv + 1], pv)
            pv = nv
            j = a[i] // (a[i] // j) + 1
        ps[0] = max(ps[0], pv)
    (ans, cm) = (10 ** 9, 0)
    for i in range(a[0] + 1):
        cm = max(cm, ps[i])
        ans = min(ans, cm - i)
    print(ans)

Solution (Python):
def compute(a, p):
    s = [a[i] // p[i] for i in range(len(a))]
    return max(s) - min(s)
for _ in range(int(input())):
    (n, k) = map(int, input().split())
    a = list(map(int, input().split()))
    m = max(a)
    l = min(a)
    t = m // k
    if k >= m:
        print(0)
    elif k == 1:
        print(max(a) - min(a))
    else:
        t = m // k
        temp = 3000
        for l in range(t + 1, 2 * t + 2):
            p = [a[i] // l + 1 for i in range(n)]
            ss = compute(a, p)
            temp = min(temp, ss)
            if temp == 0:
                break
        print(temp)

Solution (Python):
import sys
input = lambda : sys.stdin.readline().rstrip()
from collections import defaultdict, deque
from bisect import *
for _ in range(int(input())):
    (N, K) = map(int, input().split())
    A = list(map(int, input().split()))
    lib = [set() for _ in range(N)]
    for i in range(N):
        for j in range(1, K + 1):
            lib[i].add(A[i] // j)

    def check(l, r):
        for i in range(N):
            ok = False
            for a in lib[i]:
                if l <= a <= r:
                    ok = True
                    break
            if not ok:
                return False
        return True

    def deal(m):
        for i in range(0, A[-1] - m + 1):
            (l, r) = (i, i + m)
            if check(l, r):
                return True
        return False
    (l, r) = (-1, A[-1] + 1)
    while l + 1 < r:
        m = (l + r) // 2
        if deal(m):
            r = m
        else:
            l = m
    print(r)