Minimum Maximum PartitionProblem 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 N1 position. Let's call $A[0] + A[N1]$ 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 N2. This way, each element in heap now contains cost of increasing partition count by 1. Add first (K1) values in min heap to base cost for Minimum cost. For Maximum Cost The logic remains same, we just use Maxheap in place of minheap, to attain maximum cost.
This question is marked "community wiki".
asked 04 Jan '18, 22:47

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
