ICL1704 - Editorial

Problem Link

Practice

Contest

Author: Bhuvnesh Jain

Tester: Ankit Sultana

Editorialist: Eklavya Shama

Difficulty

Easy

Prerequisites

Priority queue

Problem

You are given sizes of several arrays.
You have to find out the optimal order for merging these arrays such that
the worst-case number of element comparisons are minimum.
You have to output the total number of comparisons in the worst case for this order.

Explanation

When two arrays of size m and n are merged, the worst case number of comparisons is m + n - 1
and size of the resultant array is of size m + n.

The optimal merging strategy is greedy, i.e. keep merging the shortest two arrays until just one array remains.

This can be efficiently done using a priority queue.

s = 0
Insert n1, n2, ..., nM in the priority queue.
While there is more than 1 element in the priority queue:
    Pop the smallest 2 elements from the priority queue. Let these be x and y.
    s = s + x + y - 1;
    Insert x + y in the priority queue.
output s

Time complexity

O(M*log(M))

Solution codes

Setter’s solution

Tester’s solution

How I can submit my solution to this problem now ??? The contest is over but I want to submit my solution

I have tried to implement it without priority queue. Instead I have used an array. The solution goes like -

    while(j++ < testCases) {
        M = fs.nextInt();
        int sum = 0, result = 0;
        arraySize = new int[M];
        for (int a = 0; a < M; a++) {
            arraySize[a] = fs.nextInt();
        }
        Arrays.sort(arraySize);
        // System.out.println(sum);
        for(int i = 0; i < M; i++) {
            sum += arraySize[i];
            if(i == 0) {
            } else {
                result += sum - 1;
            }
        }
        System.out.println(result);
    }

Is my approach CORRECT?

#include <bits/stdc++.h>
typedef unsigned long long LL;
using namespace std;
int main()
{
int T;
scanf("%d",&T);
while(T–){
LL n,ans=0,no;
priority_queue<LL,vector,greater > pq;
scanf("%llu",&n);
for(int i=0;i<n;i++){
scanf("%llu",&no);
pq.push(no);
}
while(pq.size()>1) {
LL s1=pq.top(); pq.pop();
LL s2=pq.top(); pq.pop();
ans+=(s1+s2-1);
pq.push(s1+s2);

        }
        printf("%llu\n",ans);
    }
    return 0;
}

This is my code. Will it work ?? =P I can’t wait

ACC to your algo, for 3 4 5 the answer is 17 but what if we first sort 4 and 5 with answer 8 and then sort 3 and 9(4+5), in this way it gives 19. Where am I wrong?

Can anyone please explain each components of

std::priority_queue<int, std::vector<int>, std::greater<int> > q2;

with which we are converting a priority queue into heap?

The problems will be soon moved to the practice section. Please be patient till then.

No, the size of the arrays after getting merged will change, thus you need to sort it everytime, which is too slow.

To decrease number of total operations, you should always chose the minimum sizes of array to reduce number of comparisons. You do it the other way around.

Yeah i didn’t read the problem well and was trying to find the max number of them! Sorry my bad!:stuck_out_tongue:

Read this - http://stackoverflow.com/questions/2439283/how-can-i-create-min-stl-priority-queue