Concepts Used

Sorting

Difficulty Level

Medium

Problem Statement (Simplified):

For given values of N and K, an array of N elements is given. You can pick at most K items in one turn, each turn costs you (turn number * element value). For all values i between 1 and N, calculate the minimum possible value of picking exactly i items.

Test Case

Input:
1
5 2
4 5 3 7 5

Output:
3 7 15 24 39

Explanation:
For K=4,
We can select 3, 4, 5, and 5. As our daily limit is 2, so we split chocolates in 2 days, we'll select larger chocolates for day 1 and select rest for day 2. So we can select chocolates like:
1st Day = 5 and 5
2nd Day = 3 and 4

So, its cost will be 1(5)+1(5)+2(3)+2(4), so our final cost becomes 24. Hence, for K=4 we print 24.

See original problem statement here

Solving Approach :

1) If we sort the provided array, it would be easy to pick items, as we can pick elements from the start of the array and the total cost would be minimal.
2) We can use Cummulative Array to solve this problem by referring online programming courses.
> * Cummulative Array: Cummulative Array is an array that contains the sum of all elements before the current index and element at the current index.
3) For any value between K, the minimum cost will be the sum of the current index. But if maximum capacity i.e. M reaches or is crossed, it also includes cost at (current day - capacity)^{th} day.

Examples

Let array A be,

Graphic-1 Here

size of array is 5 and we have $capacity$ of 2.

We arrange array in non-decreasing order. So array A becomes,

Graphic-2 Here

We create a cummulative array from our array A, hence our array A becomes,

Graphic-3 Here

For any value between 1 and size, for e.g. 4, it will represent index 3 in our array, as value is greater than our capacity, so minimum cost will be,

> minimumCost = currentDayCost + (currentDay - capacity)^{th} Day cost
>
> minimumCost = 18 + (4-3)^{th} day cost
>
> minimumCost = 18 + A[1]
>
> minimumCost = 18 + 7
>
> minimumCost = 25,

Hence, minimumCost will be 25 for the index 3, hence we get values for all days like this.

Solutions

#include <stdio.h>

void merge(long long arr[], int start, int mid, int end){
    long long left[mid-start+1];
    long long right[end-mid];

    for(int i=start; i<mid+1; i++){
        left[i-start] =  arr[i];
    }
    for(int i=mid+1; i<=end; i++){
        right[i-(mid+1)] = arr[i];
    }
    int leftIndex=0, rightIndex=0, arrIndex=start;
    for( ; leftIndex<=mid-start && rightIndex<end-mid; arrIndex++){
        if(left[leftIndex]<right[rightIndex]){
            arr[arrIndex] = left[leftIndex++];
        }
        else{
            arr[arrIndex] = right[rightIndex++];
        }
    }

    while(leftIndex<=mid-start){
        arr[arrIndex++] = left[leftIndex++];
    }

    while(rightIndex<end-mid){
        arr[arrIndex++] = right[rightIndex++];
    }

}

void mergeSort(long long arr[], int start, int end){
    if(end==start)
        return;
    mergeSort(arr,start,(start+end)/2);
    mergeSort(arr,((start+end)/2)+1,end);
    merge(arr,start,(start+end)/2,end);
}

int main()
{
  int test;
  scanf("%d",&test);

  while(test--){

    int n, k;
    scanf("%d%d",&n,&k);

    long long int chocolate[n];
    for(int i=0; i<n; i++)
      scanf("%lld",&chocolate[i]);

    mergeSort(chocolate, 0, n-1);

    for(int i=1; i<n; i++)
      chocolate[i] += chocolate[i-1];

    for(int i=0; i<n; i++){
      if(i>=k)
        chocolate[i] += chocolate[i-k];
      printf("%lld ",chocolate[i]);
    }

    printf("\n");

  }
}
#include <bits/stdc++.h>
using namespace std;

void merge(long long arr[], int start, int mid, int end){
    long long left[mid-start+1]={0};
    long long right[end-mid]={0};
    for(int i=start; i<mid+1; i++){
        left[i-start] =  arr[i];
    }
    for(int i=mid+1; i<=end; i++){
        right[i-(mid+1)] = arr[i];
    }
    int leftIndex=0, rightIndex=0, arrIndex=start;
    for( ; leftIndex<=mid-start && rightIndex<end-mid; arrIndex++){
        if(left[leftIndex]<right[rightIndex]){
            arr[arrIndex] = left[leftIndex++];
        }
        else{
            arr[arrIndex] = right[rightIndex++];
        }
    }

    while(leftIndex<=mid-start){
        arr[arrIndex++] = left[leftIndex++];
    }

    while(rightIndex<end-mid){
        arr[arrIndex++] = right[rightIndex++];
    }

}

void mergeSort(long long arr[], int start, int end){
    if(end==start)
        return;
    mergeSort(arr,start,(start+end)/2);
    mergeSort(arr,((start+end)/2)+1,end);
    merge(arr,start,(start+end)/2,end);
}

int main()
{
  int test;
  cin>>test;

  while(test--){

    int n, k;
    cin>>n>>k;

    long long int chocolate[n];
    for(int i=0; i<n; i++)
      cin>>chocolate[i];

    mergeSort(chocolate, 0, n-1);

    for(int i=1; i<n; i++)
      chocolate[i] += chocolate[i-1];

    for(int i=0; i<n; i++){
      if(i>=k)
        chocolate[i] += chocolate[i-k];
      cout<<chocolate[i]<<" ";
    }

    cout<<endl;

  }
}
import java.util.*;
import java.io.*;

public class Main {

  static void merge(long arr[], int start, int mid, int end){
    long left[] = new long[mid-start+1];
    long right[] = new long[end-mid];

    for(int i=start; i<mid+1; i++){
        left[i-start] =  arr[i];
    }
    for(int i=mid+1; i<=end; i++){
        right[i-(mid+1)] = arr[i];
    }
    int leftIndex=0, rightIndex=0, arrIndex=start;
    for( ; leftIndex<=mid-start && rightIndex<end-mid; arrIndex++){
        if(left[leftIndex]<right[rightIndex]){
            arr[arrIndex] = left[leftIndex++];
        }
        else{
            arr[arrIndex] = right[rightIndex++];
        }
    }

    while(leftIndex<=mid-start){
        arr[arrIndex++] = left[leftIndex++];
    }

    while(rightIndex<end-mid){
        arr[arrIndex++] = right[rightIndex++];
    }

  }

  static void mergeSort(long arr[], int start, int end){
      if(end==start)
          return;
      mergeSort(arr,start,(start+end)/2);
      mergeSort(arr,((start+end)/2)+1,end);
      merge(arr,start,(start+end)/2,end);
  }

  public static void main(String args[]) throws IOException {

    InputStreamReader r = new InputStreamReader(System.in);    
    BufferedReader br = new BufferedReader(r);    
    int test = Integer.parseInt(br.readLine());

    while(test-->0){

      String s= br.readLine();
      String[] s1 = s.split(" ");
      int n = Integer.parseInt(s1[0]);
      int k = Integer.parseInt(s1[1]);

      long chocolate[] = new long[n];
      s = br.readLine();
      String s2[] = s.split(" ");
      for(int i=0; i<n; i++)
        chocolate[i] = Long.parseLong(s2[i]);

      mergeSort(chocolate, 0, n-1);

      for(int i=1; i<n; i++)
        chocolate[i] += chocolate[i-1];

      for(int i=0; i<n; i++){
        if(i>=k)
          chocolate[i] += chocolate[i-k];
        System.out.print(chocolate[i]+" ");
      }

      System.out.println();

    }
    br.close();
  }
}

Space Complexity

O(1)

Previous post First character
Next post Find the Inversion Count

Leave a Reply

Your email address will not be published. Required fields are marked *