#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/contests/7/problems/f

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░█████████████████████████████████████████

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/contests/7/problems/f

Repovive

Circular Delivery - Repovive Career Starter Round 1 | Repovive | Repovive

Back

Code

Upload

Submissions

Problem

7F. Circular Delivery

3000 ptstype :zen to enter zen mode

by AmirMohammad Shahrezaei (AmShZ)

Time: 2sMemory: 256 MB

Page 1

The main difficulty is that the array is circular. If the array were linear, this would be the classical problem of splitting an array into $k$ non-empty subarrays while minimizing the maximum subarray sum.

Here we can still use the same high-level idea.

Suppose we guess that the answer is at most $X$ .

Now the question becomes:

Can we cut the circle into at most $k$ non-empty contiguous parts, such that the sum of each part is at most $X$ ?

We use "at most $k$ " instead of "exactly $k$ " because all $a_i$ are positive.

If we can split the circle into $s \le k$ parts, then we can split some of those parts further until we have exactly $k$ parts. Since every new part has smaller or equal sum than the original part, the maximum cost will not increase.

Also, because $k \le n$ , this splitting process is always possible.

So for a fixed $X$ , it is enough to check whether the circle can be covered using at most $k$ parts, each with sum at most $X$ .