You are not logged in. Please login at www.codechef.com to post your questions!

×

# Minimum Maximum Partition

Problem Setter: Istasis Mishra

Problem Tester: Soham Mukherjee

Editorialist: Taranpreet Singh

## Problem:

Given an array of size N and an integer K. Find out the minimum and maximum cost of dividing given array into K parititons, where partitions cost of partition [l,r] is defined as A[l]+A[r].

## Solution:

This problem does not want to go for typical dp solutions that run in our mind hearing the word partitioning into K parts.

Since it is necessary to include all the elements in one partition or another, There will be a partition starting at 0 and one partition ending at N-1 position. Let's call $A[0] + A[N-1]$ as base cost.

Now, since we need to have all elements in one partition or another, if A[i] is included in ans as end of some partition other than the last one, A[i+1] will be included in ans as start of next partition.

Thus, the ideal policy if to select "Ideal Split points", for both min cost and max cost.

For Minimum Cost

To determine an idea split point, maintain a min heap (PriorityQueue) and push into heap $A[i]+A[i+1]$ for every i from 0 to N-2. This way, each element in heap now contains cost of increasing partition count by 1. Add first (K-1) values in min heap to base cost for Minimum cost.

For Maximum Cost

The logic remains same, we just use Max-heap in place of min-heap, to attain maximum cost.

Editorialsist' solution

This question is marked "community wiki".

asked 04 Jan '18, 22:47

4.0k31104
accept rate: 22%

 0 It's a pretty beautiful question with a nice sorting criteria. But, this isn't a cakewalk by a long shot. answered 11 Feb '18, 17:15 58●5 accept rate: 5%
 toggle preview community wiki:
Preview

### Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×1,688
×247
×42
×28
×6

question asked: 04 Jan '18, 22:47

question was seen: 558 times

last updated: 11 Feb '18, 17:15