 # ICL1704 - Editorial

Practice

Contest

Author: Bhuvnesh Jain

Tester: Ankit Sultana

Editorialist: Eklavya Shama

Easy

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
``````

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

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

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?

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

#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?

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! 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?

//