Temporary Temperature
Source: codechef
Difficulty: 1516

Temporary Temperature
Chef is cooking his finest dish yet. The recipe calls for a series of$N$steps, where the$i$-th step is recommended to be performed at a temperature of$A_i$.
The steps must be performed in order from$1$to$N$.
The further away from the recommended temperature Chef gets, the worse the dish tastes.
Suppose Chef performs the$i$-th step at a temperature of$B_i$.
The
unsavoriness
of the dish is then defined to be$\max_{i=1}^N |A_i - B_i|$That is, the unsavoriness is the maximum temperature difference across all the steps.
Note that$|x|$refers to the
absolute value
of$x$.
Chef can choose to perform each step at any temperature he wishes - i.e. he can choose the array$B$freely.
However, he doesn't want to change the temperature too often from one step to the next.
A temperature change happens at step$i$(where$2 \leq i \leq N$) if$B_i \neq B_{i-1}$.
For example, if$B = [1, 1, 2, 2, 6, 3]$, there are three temperature changes: at steps$3, 5,$and$6$.
You are the given the array$A$denoting recommended temperatures.
If Chef can choose the array$B$freely, and change temperature
at most$K$times from one step to the next, what's the
minimum
possible
unsavoriness
of the dish?
Input Format
The first line of input will contain a single integer$T$, denoting the number of test cases.
Each test case consists of two lines of input.
The first line of each test case contains two space-separated integers$N$and$K$— the number of steps in the recipe and the maximum allowed number of temperature changes, respectively.
The second line contains$N$space-separated integers$A_1, A_2, \ldots, A_N$, the recommended  temperature of the$N$steps.
Output Format
For each test case, output on a new line one integer: the minimum possible unsavoriness.
Constraints$1 \leq T \leq 10^5$$1 \leq N \leq 2\cdot 10^5$$0 \leq K \leq N$$1 \leq A_i \leq 10^9$The sum of$N$over all test cases won't exceed$2\cdot 10^5$.
Sample 1:
Explanation:
Test case$1$:$K = 0$, so there cannot be any temperature changes.
It's optimal for Chef to choose$B = [2, 2, 2]$.
This gives:$|A_1 - B_1| = |1 - 2| = 1$$|A_2 - B_2| = |3 - 2| = 1$$|A_3 - B_3| = |3 - 2| = 1$All differences are$1$, so the unsavoriness - the maximum difference - is$1$. This is optimal.
Test case$2$:
Same as the previous case, but$K = 1$so one temperature change is allowed.
Chef can choose$B = [1, 3, 3]$, the same as$A$, which has only one temperature change. The unsavoriness is$0$since$A_i = B_i$for all$i$.
Test case$3$:
One optimal choice of$B$is$B = [27, 44, 44, 27]$. There are two temperature changes (at steps$2$and$4$), which is allowed because$K = 2$.
It can be verified that$|A_2 - B_2| = 4$is the maximum difference.$4$is optimal.
Test case$4$:
One optimal choice of$B$is$B = [101, 101, 101, 101, 90]$, which has one temperature change.

Sample Input:
4
3 0
1 3 3
3 1
1 3 3
4 2
25 40 47 30
5 1
120 100 82 111 74

Sample Output:
1
0
4
19

C++ solution:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

// Check if it's possible to achieve unsavoriness W
// with at most K temperature changes (i.e. <= K+1 segments).
bool feasible(const vector<ll>& A, ll W, int K) {
    int segments = 1;
    ll cur_min = A[0], cur_max = A[0];
    for (int i = 1, n = A.size(); i < n; ++i) {
        cur_min = min(cur_min, A[i]);
        cur_max = max(cur_max, A[i]);
        // If the current segment's range exceeds 2W, start a new segment
        if (cur_max - cur_min > 2*W) {
            ++segments;
            cur_min = cur_max = A[i];
        }
    }
    return segments <= K + 1;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;
    while (T--) {
        int N, K;
        cin >> N >> K;
        vector<ll> A(N);
        for (int i = 0; i < N; ++i)
            cin >> A[i];

        // If you can change at every step, you can match A exactly.
        if (K >= N - 1) {
            cout << 0 << "\n";
            continue;
        }

        // Determine the search range: 0 … max(A)-min(A)
        ll mn = *min_element(A.begin(), A.end());
        ll mx = *max_element(A.begin(), A.end());
        ll low = 0, high = mx - mn;

        // Binary search for the minimal W
        while (low < high) {
            ll mid = (low + high) / 2;
            if (feasible(A, mid, K))
                high = mid;
            else
                low = mid + 1;
        }

        cout << low << "\n";
    }
    return 0;
}

Go solution:
package main

import (
    "bufio"
    "fmt"
    "os"
    "strconv"
    "strings"
)

func main() {
    var t int
    reader := bufio.NewReader(os.Stdin)

    tStr, _ := reader.ReadString('\n')
    tStr = strings.TrimSpace(tStr)
    t, _ = strconv.Atoi(tStr)  

    for i := 0; i < t; i++ {
        nkStr, _ := reader.ReadString('\n')
        nkStr = strings.TrimSpace(nkStr)
        nk := strings.Split(nkStr, " ")
        n, _ := strconv.Atoi(nk[0])
        k, _ := strconv.Atoi(nk[1])

        arrStr, _ := reader.ReadString('\n')
        arrStr = strings.TrimSpace(arrStr)
        arrTokens := strings.Split(arrStr, " ")

        arr := make([]int, n)
        for j := 0; j < n; j++ {
            arr[j], _ = strconv.Atoi(arrTokens[j])
        }

        min := arr[0]
        max := arr[0]
        for j := 1; j < n; j++ {
            if arr[j] < min {
                min = arr[j]
            }
            if arr[j] > max {
                max = arr[j]
            }
        }

        low, high := int64(0), int64(max-min)
        for low < high {
            mid := low + (high-low)/2
            groups := int64(1)
            l := int64(arr[0]) - mid
            r := int64(arr[0]) + mid

            for i := 1; i < n; i++ {
                nl := int64(arr[i]) - mid
                nr := int64(arr[i]) + mid

                if nl > r || nr < l {
                    groups++
                    l = nl
                    r = nr
                } else {
                    if nl > l {
                        l = nl
                    }
                    if nr < r {
                        r = nr
                    }
                }
            }

            if groups <= int64(k+1) {
                high = mid
            } else {
                low = mid + 1
            }
        }

        fmt.Println(low)
    }
}

Java solution:
/* package codechef; // don't place package name! */

import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
class Post{
    int f;
    int p;
    String s;
    int isSpecial;
    
    public Post(int f, int p, String s, int isSpecial){
        this.f = f;
        this.p = p;
        this.s = s;
        this.isSpecial = isSpecial;
    }
}
class Codechef
{
    public static void main (String[] args) throws java.lang.Exception
    {
        Set<Integer> setP = new HashSet();
        boolean[] isP = new boolean[1000001];
        for(int i = 0; i < 1000001; i++) isP[i]=true;
        for(int i = 2; i * i <= 1000000; i++){
            if(isP[i]){
                for(int j=i*i;j<=1000000;j+=i) isP[j]=false;
            }
        }
        for(int i =2;i<=1000000;i++) if(isP[i]) setP.add(i);
        PrintWriter out=new PrintWriter(System.out);
        FastReader sc = new FastReader();
        int testQ = sc.nextInt();
        for(int q = 0; q < testQ; q++){
            int n = sc.nextInt();
            int k = sc.nextInt();
            int[] a = new int[n];
            for(int i = 0; i < n; i++)a[i] = sc.nextInt();
            int l = 0, r = 1000000000, ans = 0;
            while(l<=r){
                int m = (r+l)/2;
                if(canAchieve(a,m,k,n)){
                    ans = m; r = m-1;
                }else l=m+1;
            }
            out.println(ans);
        }
        out.flush();
    }
    static boolean canAchieve(int[]a, int d, int k, int n){
        int min = a[0] - d, max = a[0]+d, f = k;
        for(int i = 1; i < n && f >= 0; i++){
            if(a[i]+d<min||a[i]-d>max){
                k--; 
                min = a[i]-d;
                max = a[i]+d;
            }else{
                min = Math.max(min,a[i]-d);
                max = Math.min(max,a[i]+d);
            }
        }
        return k>=0;
    }
    public int gcd(int a, int b) {
        if (b==0) return a;
        return gcd(b,a%b);
    }
    static class FastReader {
        BufferedReader br;
        StringTokenizer st;

        public FastReader()
        {
            br = new BufferedReader(
                new InputStreamReader(System.in));
        }

        String next()
        {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                }
                catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() { return Integer.parseInt(next()); }

        long nextLong() { return Long.parseLong(next()); }

        double nextDouble()
        {
            return Double.parseDouble(next());
        }

        String nextLine()
        {
            String str = "";
            try {
                if(st.hasMoreTokens()){
                    str = st.nextToken("\n");
                }
                else{
                    str = br.readLine();
                }
            }
            catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
    }
}

JavaScript solution:
/* -------------------------------------------------------- */
/*   ( The Authentic JS CodeBuff )
 ___ _                      _              _ 
 | _ ) |_  __ _ _ _ __ _ __| |_ __ ____ _ (_)
 | _ \ ' \/ _` | '_/ _` / _` \ V  V / _` || |
 |___/_||_\__,_|_| \__,_\__,_|\_/\_/\__,_|/ |
                                        |__/ 
 */
/* ---------------------------------------------------------   */
/*    Youtube: https://youtube.com/@code-with-Bharadwaj        */
/*    Github : https://github.com/Manu577228                  */
/* ----------------------------------------------------------- */

/* Template Starts here Fast IO! */

const V8Flags = [
    '--max-old-space-size=4096', '--max-semi-space-size=16', '--stack-size=65536', '--reclaim-unused-memory',
    '--gc-interval=100', '--expose-gc', '--gc-global', '--optimize-for-speed',
    '--always-opt', '--max-inlined-source-size=600', '--max-inlined-bytecode-size=600', '--turbo-inline-js-wasm-calls',
    '--turbo', '--turbo-optimizer', '--force-optimization', '--no-lazy',
    '--no-lazy-inner-functions', '--optimize-for-size', '--initial-heap-size=64', '--max-heap-size=192',
    '--use-strict', '--predictable', '--single-threaded-gc', '--no-inline-new',
    '--opt', '--no-lazy-deserialization', '--no-browser-globals', '--turbo-inline-array-builtins',
    '--fast-math', '--fuzzing', '--minor-mc', '--incremental-marking',
    '--concurrent-recompilation', '--stress-compaction', '--experimental-flush-embedded-blob-icache', '--experimental-value-unavailable'
];

if (V8Flags.length > 0) {
        process.execArgv.push('--v8-options=' + V8Flags.join(' '));
}

const inputBuffer = Buffer.allocUnsafe(1e7);
let inputIndex = 0,
        inputLength = 0;
const outputBuffer = Buffer.allocUnsafe(1e7);
let outputIndex = 0;

const fs = require('fs');
inputLength = fs.readSync(process.stdin.fd, inputBuffer, 0, inputBuffer.length, null);

function readInt() {
        let num = 0,
                sign = 1;
        while (inputBuffer[inputIndex] < 48 || inputBuffer[inputIndex] > 57) {
                if (inputBuffer[inputIndex] === 45) sign = -1;
                inputIndex++;
        }
        while (inputIndex < inputLength && inputBuffer[inputIndex] >= 48 && inputBuffer[inputIndex] <= 57) {
                num = num * 10 + (inputBuffer[inputIndex++] - 48);
        }
        return num * sign;
}

function writeInt(value, isLast = false) {
        if (outputIndex > 0) outputBuffer[outputIndex++] = 32;
        if (value < 0) {
                outputBuffer[outputIndex++] = 45;
                value = -value;
        }
        let digits = [];
        do {
                digits.push(value % 10);
                value = Math.floor(value / 10);
        } while (value > 0);
        for (let i = digits.length - 1; i >= 0; i--) {
                outputBuffer[outputIndex++] = 48 + digits[i];
        }
        if (isLast) {
                outputBuffer[outputIndex++] = 10;
        }
}

/* Template Ends here! */

let T = readInt();
while (T--) {
        let N = readInt(),
                K = readInt();
        let A = new Array(N);
        for (let i = 0; i < N; i++) A[i] = readInt();
        
        let minA = Infinity,
                maxA = -Infinity;
        for (let i = 0; i < N; i++) {
                if (A[i] < minA) minA = A[i];
                if (A[i] > maxA) maxA = A[i];
        }
        
        let l = 0,
                r = Math.max(1e9, maxA - minA);
        
        const possible = (D) => {
                let s = 1,
                        L = A[0] - D,
                        R = A[0] + D;
                for (let i = 1; i < N; i++) {
                        let nl = Math.max(L, A[i] - D),
                                nr = Math.min(R, A[i] + D);
                        if (nl > nr) {
                                s++;
                                L = A[i] - D;
                                R = A[i] + D;
                        } else {
                                L = nl;
                                R = nr;
                        }
                }
                return s <= K + 1;
        };
        
        while (l < r) {
                let m = Math.floor((l + r) / 2);
                if (possible(m)) r = m;
                else l = m + 1;
        }
        writeInt(l, true);
}

fs.writeSync(process.stdout.fd, outputBuffer.slice(0, outputIndex));

Python solution:
# cook your dish here
def min_unsavoriness(t, test_cases):
    results = []
    
    for n, k, a in test_cases:
        low, high = 0, max(a)
        while low < high:
            mid = (low + high) // 2
            block_count = 1
            l, r = a[0] - mid, a[0] + mid
            for temp in a:
                # Update range
                nl, nr = max(l, temp - mid), min(r, temp + mid)
                if nl > nr:
                    # Start a new block
                    block_count += 1
                    l, r = temp - mid, temp + mid
                else:
                    l, r = nl, nr
            if block_count - 1 <= k:
                high = mid
            else:
                low = mid + 1
        results.append(low)
    
    return results


# Input Reading
t = int(input())
test_cases = []
for _ in range(t):
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    test_cases.append((n, k, a))

# Solve and Output
results = min_unsavoriness(t, test_cases)
print("\n".join(map(str, results)))

Ruby solution:
def solve
  input = $stdin.read.split
  ptr = 0
  test_cases = input[ptr].to_i
  ptr += 1
  results = []
  
  test_cases.times do
    n = input[ptr].to_i
    k = input[ptr + 1].to_i
    ptr += 2
    a = input[ptr, n].map(&:to_i)
    ptr += n
    
    low = 0
    high = a.max - a.min
    
    answer = high
    
    while low <= high
      mid = (low + high) / 2
      segments = 1
      current_min = a[0]
      current_max = a[0]
      
      (1...n).each do |i|
        new_min = [current_min, a[i]].min
        new_max = [current_max, a[i]].max
        if (new_max - new_min) > 2 * mid
          segments += 1
          current_min = a[i]
          current_max = a[i]
        else
          current_min = new_min
          current_max = new_max
        end
      end
      
      if segments <= k + 1
        answer = mid
        high = mid - 1
      else
        low = mid + 1
      end
    end
    
    results << answer
  end
  
  puts results.join("\n")
end

solve