CSES - Array Division

Explanation

In this problem, we're asked to divide an array into $k$ subarrays such that the maximum sum of a subarray is minimized.

Let's begin by making an important observation. First of all, if you can divide an array such that the maximum sum is at most $x$, you can also divide the array such that the maximum sum is at most $y > x$ with the same division.

Now, given some maximum sum $x$, we can check whether a division is possible using a greedy algorithm. If we can divide the array into $s < k$ subarrays, then we can divide it into $k$ subarrays without increasing the maximum sum of a subarray. Therefore, we can greedily create subarrays as long as the sum of the subarray does not exceed $x$, and check if the number of subarrays is $\leq k$.

Implementation

Time Complexity: $\mathcal{O}(N \log N)$

Copy
#include <bits/stdc++.h>
using namespace std;

using ll = long long;

// MAX_N * MAX_X
ll MAX_SUM = 2e5 * 1e9;

/**
 * true if the given `arr` can be divided into `k` subarrays where the sum of

Copy
import java.io.*;
import java.util.StringTokenizer;

public class ArrayDivision {
	// MAX_N * MAX_X
	static final long MAX_SUM = (long)(2e5 * 1e9);

	public static void main(String[] args) throws IOException {
		BufferedReader br =
		    new BufferedReader(new InputStreamReader(System.in));

Copy
n, k = map(int, input().split())
nums = list(map(int, input().split()))


def can_divide_arrays(max_sum: int) -> bool:
	"""
	Checks if it is possible to divide nums into k subarrays with each
	each subarray having a maximum sum of max_sum

	:param max_sum: The maximum sum of each subarray