ICL1704 - Editorial

Problem Link



Author: Bhuvnesh Jain

Tester: Ankit Sultana

Editorialist: Eklavya Shama




Priority queue


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.


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


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();
        // System.out.println(sum);
        for(int i = 0; i < M; i++) {
            sum += arraySize[i];
            if(i == 0) {
            } else {
                result += sum - 1;

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;
LL n,ans=0,no;
priority_queue<LL,vector,greater > pq;
for(int i=0;i<n;i++){
while(pq.size()>1) {
LL s1=pq.top(); pq.pop();
LL s2=pq.top(); pq.pop();

    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!:stuck_out_tongue:

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?

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