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.