CareerCup

Algo - Greedy Algorithm
Add smallest two ropes first and push the change back to min heap
Java Implementation

public class MinimunRopeJoiningCost {
    static public void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader( new InputStreamReader( System.in));
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        String[] temp = br.readLine().trim().split(" ");
        for ( String s: temp){
            pq.add(Integer.parseInt(s));
        }
        Integer result = new Integer(0);
        while(pq.size()>1){
            Integer a = pq.remove();
            Integer b = pq.remove();
            result = result + a+b;
            pq.add(a+b);
        }
        System.out.println(result);
    }
}

You'll have to use min-heap. Extract the two smallest ropes Li and Lj from minheap and add back (Li + Lj) back to min-heap. Repeat the process until there is only one element in minheap and its length will be L1 to LN

Isn't the solution greedy ? We store rope array in min heap and join the two less expensive ( the less expensive with current rope) each time till there is one rope

O(n log n) - choose 2 smallest lengths for joining first - minHeap, put result back to heap, repeat till only one element in heap remains (the final length)

c++, priority_queue, O(n log n)

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int minCost(vector<int>& arr) {
    priority_queue< int, vector<int>, greater<int> > pq;
    int i, cost;

    cost = 0;
    for (i = 0; i < arr.size(); i++) {
        pq.push(arr[i]);
    }

    while (pq.size() > 1) {
        i = pq.top();
        pq.pop();
        i += pq.top();
        pq.pop();
        pq.push(i);
        cost += i;
    }

    return cost;
}

int main (int argc, char* argv[]) {
    vector<int> arr;

    cout << minCost(arr) << endl;

    arr.push_back(1);
    arr.push_back(2);
    arr.push_back(3);
    arr.push_back(5);
    arr.push_back(7);

    cout << minCost(arr) << endl;

    return 0;
}

you are miss-interpreting the question.
1st : you have to join all the ropes available
2nd: total length should be sum of all ropes.

I think what you want it is an arithmetic progression.
So you should use this formula: Sn = ((L1+Ln) x n) / 2
C++ example:

int main() { int ropes[]{2,4,6,8,10}; //5 =n, the number of the ropes
    int Sn=0;  Sn=((2+10)*5)/2;  cout<<"Ropes Length: "<<Sn; return 0; }

public class Test {

public static void main(String[] args) {

int swap;
int[] arr = {5,6,2,4,3};
int j = arr.length;

for( int i = j ; i > 1 ; i--){
for(int k = 0 ; k < 2 ; k++){
for(int m = k+1 ; m < i ; m++){
if(arr[k] > arr[m]){
swap = arr[k];
arr[k] = arr[m];
arr[m] = swap;
}
} // sorting first two elements.

}

arr[0] = arr[0] + arr[1];
System.out.print(arr[0]);
for(int n=1 ; n < i-1 ; n++){
arr[n] = arr[n+1];
System.out.print(","+arr[n]);
}
System.out.println("");
}
System.out.println("Total Cost : "+ arr[0]);
}

}

Dynamic Programming: for 3 ropes


min = min(l1 + 2 * (l2+l3), (l1+l2)*2 + l3, (l1+l3)*2 + l2)

Also, one more thing I noticed, if we sort them and join them

1 2 3 4 5 6

Join 1 and 2 : 3 3 4 5 6 : 3
Join 3 and 3: 6 4 5 6: 6
Join 6 and 4: 10 5 6 : 10
Join 10 and 5: 15 6 : 15
Join 15 and 6: 21

total : 55


Can we use this algorithm

Can you please add an example i.e. sample input and an output?

It does not matter - whatever order you choose the code is same - because when you join two ropes the next join would require joining ropes of larger length.

Final cost would be sum(L1, ,,, , LN) in whatever order

I don't get the confusion ?? Total cost of joining is L1 + 2*(L2+L3+L4...) + Ln. So you actually need to find the maximum and 2nd max make them the end of the rope and just join others. In my example I assumed L1,Ln are max. This will be the minimum cost.

this is Hoffman encoding in disguise

/* re-arrange the list of rope in sorted order
then get the cost of first two biggest rope joining 
with the smallet rope from both the end.
so the cost will be 
L1 + 2S1 + L2*/
int minCost(int *arr, int size){
	int f = 0;
	for (int s = 1, l = size - 1; arr[s] != INT_MIN; f++, s++, l--){
		arr[s] = arr[f] + 2 * arr[l] + arr[s];
		arr[l] = INT_MIN;
		arr[f] = INT_MIN;	
	}
	return arr[f];
}

input rope array :: 15 14 8 37 20
isorted rope passed to minCost() :: 37 20 15 14 8
minimum cost = 116

I think he program needs clarification, seems that the sum is always the same, can you provide more detail on it?

lets say we have ropes of 5, 6, 8, 9, total cost of joining is always going to 56, no matter what combination we take.
5+6=11
8+9=17
11+17=28
Final cost = 11+17+28=56

Total cost is always going to be the same irrespective of the combination -
example lets say we have ropes of length 5,6,8,9.
1) 5+6=11
2) 8+9=17
3) 11+17=28
4) 28+17+11=56

Total cost is always 56

package com.company;

import java.lang.*;
import java.util.*;

public class Main {

    public static void main(String[] args) {
        int a[] = {4, 3, 2, 6};
        int n = a.length;
        PriorityQueue<Integer> p = new PriorityQueue<>(n);
        for (int i = 0; i < n; i++) {
            p.add(a[i]);
        }
        int r = 0;
        while(p.size()>1){
            int b = p.remove();
            int c = p.remove();
            r = r + (c+b);
            p.add(c+b);
        }
        System.out.print(r);
    }
}

I think what you want it is an arithmetic progression.
So you should use this formula: Sn = ((L1+Ln) x n) / 2
C++ example:
#include <iostream>

using namespace std;

int main()
{
int ropes[]{2,4,6,8,10}; //5 =n, the number of the ropes
int Sn=0;
Sn=((2+10)*5)/2;
cout<<"Ropes Length: "<<Sn;
return 0;
}

I think what you want it is an arithmetic progression.
So you should use this formula: Sn = ((L1+Ln) x n) / 2
C++ example:

#include <iostream> 

using namespace std; 

int main()
{
    int ropes[]{2,4,6,8,10}; //5 =n, the number of the ropes
    int Sn=0;
    Sn=((2+10)*5)/2;
    cout<<"Ropes Length: "<<Sn;
    return 0;
}

As all the ropes lengths have to be considered no matter what, can't we directly sort the lengths and compute its sum? in any case, it seems like there is no minimum sum as the sum amount is always going to be same for any combination of lengths. I might be missing something here, if so please let me know.

Is it only me who notices that the cost is given L1 + L2, no matter what. So even if we join any random pieces of rope the cost is still gonna be fixed. So the cost might be (n-1)*(L1+L2). Thoughts on this?