CSES - Array Division

Authors: Michael Cao, George Pong, Chuyang Wang

Appears In

Silver - Binary Search

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)$

Warning!

Make sure to use 64-bit numbers to avoid overflow! Implementing the greedy algorithm also requires some caution.

C++

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

using ll = long long;

/**
 * true if the given `arr` can be divided into `k` subarrays where the sum of
 * each subarray is at most `max_sum`
 */
bool is_possible(const vector<ll> &arr, const int k, ll max_sum) {

Java

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;
import java.util.stream.LongStream;

public class ArrayDivision {

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

Python

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

Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!

Join Forum