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

2 Likes

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