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

×

MINMAX3 - EDITORIAL

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

taran_1407's gravatar image

5★taran_1407
4.0k31104
accept rate: 22%

edited 05 Jan '18, 07:41


It's a pretty beautiful question with a nice sorting criteria. But, this isn't a cakewalk by a long shot.

link

answered 11 Feb '18, 17:15

mathprogrammer's gravatar image

3★mathprogrammer
585
accept rate: 5%

toggle preview
Preview

Follow this question

By Email:

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

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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