Chopping Carrots (Hard Version) (Codeforces 1706D2)
Tags: Greedy, two pointers

This is the hard 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 10^5$$$).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 10^5$$$).It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^5$$$.

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):
import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
t = int(input())
ans = []
inf = pow(10, 9) + 1
for _ in range(t):
    (n, k) = map(int, input().split())
    a = list(map(int, input().split()))
    m = a[-1] + 5
    ma = [0] * m
    for i in a:
        u = [i]
        for j in range(2, k + 1):
            v = i // j
            if u[-1] == v:
                break
            u.append(v)
        v = i // k
        while u[-1] ^ v:
            u.append(u[-1] - 1)
        for j in range(len(u) - 1):
            ma[u[j + 1] + 1] = max(ma[u[j + 1] + 1], u[j])
        ma[0] = max(ma[0], u[-1])
    for i in range(1, m):
        ma[i] = max(ma[i], ma[i - 1])
    ans0 = inf
    for i in range(a[0] + 1):
        ans0 = min(ans0, ma[i] - i)
    ans.append(ans0)
sys.stdout.write('\n'.join(map(str, ans)))

Solution (Python):
import sys
input = sys.stdin.readline
for _ in range(int(input())):
    (n, k) = map(int, input().split())
    w = list(map(int, input().split()))
    d = [0] * (w[-1] + 1)
    for i in w:
        b = i
        j = 2
        while j <= k and j <= i:
            a = i // j
            d[a + 1] = max(b, d[a + 1])
            j = i // b + 1
            b = a
        a = i // j
        d[a + 1] = max(b, d[a + 1])
    c = e = w[-1] // k
    ans = w[-1] - w[0]
    for i in range(1, w[0] + 1):
        c = max(d[i], c)
        ans = min(ans, c - i)
    print(ans)

Solution (Python):
def main():
    t = int(input())
    allans = []
    for _ in range(t):
        (n, k) = readIntArr()
        a = readIntArr()
        ans = int(2000000000.0)
        store = [[] for __ in range(max(a) + 1)]
        currmax = 0
        for x in a:
            v = x // k
            currmax = max(v, x // k)
            store[v].append(x)
        end = False
        for low in range(max(a) + 1):
            if len(store[low]) > 0:
                ans = min(ans, currmax - low)
                while store[low]:
                    num = store[low].pop()
                    next_den = num // (low + 1)
                    if next_den == 0:
                        end = True
                        break
                    v2 = num // next_den
                    currmax = max(currmax, v2)
                    store[v2].append(num)
            if end:
                break
        allans.append(ans)
    multiLineArrayPrint(allans)
    return
import sys
input = sys.stdin.buffer.readline

def oneLineArrayPrint(arr):
    print(' '.join([str(x) for x in arr]))

def multiLineArrayPrint(arr):
    print('\n'.join([str(x) for x in arr]))

def multiLineArrayOfArraysPrint(arr):
    print('\n'.join([' '.join([str(x) for x in y]) for y in arr]))

def readIntArr():
    return [int(x) for x in input().split()]

def makeArr(defaultValFactory, dimensionArr):
    dv = defaultValFactory
    da = dimensionArr
    if len(da) == 1:
        return [dv() for _ in range(da[0])]
    else:
        return [makeArr(dv, da[1:]) for _ in range(da[0])]

def queryInteractive(a, b, c):
    print('? {} {} {}'.format(a, b, c))
    sys.stdout.flush()
    return int(input())

def answerInteractive(x1, x2):
    print('! {} {}'.format(x1, x2))
    sys.stdout.flush()
inf = float('inf')
from math import gcd, floor, ceil
import math
for _abc in range(1):
    main()