Click here to Skip to main content
14,839,939 members
Please Sign up or sign in to vote.
1.00/5 (2 votes)
See more:
Can anyone just say how to solve this problem. I am not asking for code just a way to solve.

Question:
There are m cabins numbered from 1 to m where n cabins are broken. You are provided with infinitely long tape which you are allowed to cut only k times. The task is to cover all the broken cabins with minimum length of tape used. You are provided with broken cabin positions, you are also allowed to cover non-broken cabins, and it is possible that some pieces of tape will overlap.

Input Format
First line contains three inputs n, m and k where n is number of cabins broken, m is total number of cabins, and k is number of tape pieces to be cut.
Second line contains n integers b1, b2, b3 ...... bn represents positions of broken cabins in increasing order.

Output Format
print minimum total length of the pieces.

Example:
Input
4 100 2
20 30 75 80


Output
17


Explanation:
4 broken cabins, you need to cover broken cabins with 2 pieces of tape.

cabins - Bold numbers are broken cabins
1.......20........30....................75.......80........100
        -----11-----                    -----6-----


length of tape used to cover cabin 20 and 30 is 11
length of tape used to cover cabin 75 and 80 is 6
so total length is 17

If k=4 that means only 1 meter tape of 4 pieces are required to cover cabins 20, 30, 75, and 80 So the total length required is 4.

What I have tried:

I tried in many different ways by taking gaps between the broken cabins and by sorting them, but some cases are not getting solve. Please anyone just suggest algorithm to solve this problem. It is not urgent so you can take time to solve.
Posted
Updated 12-Feb-21 9:53am
v4
Comments
Maciej Los 10-Feb-21 3:22am
   
What [2] means in the first line?
Padala Vamsi ujpNQUXGRi 10-Feb-21 3:51am
   
2 is number of pieces of tape must cut. That is why we just cut 2 pieces with length 11 and 6 meters. If that number is 4 we might have cut 4 pieces of length 1 meter.

The problem is very simple, much simpler than what has already been said. You don't need combinations, variations, permutations, factorials, none of that.

Lets assume you start with one piece of tape from the leftmost to the rightmost broken cabin. When more pieces of tape are allowed, there must be better solutions.
So you want to remove as much tape as possible. The lengths of tape that are candidate for removal are the distances between consecutive broken cabins (BTW: if you think about it, the +1 in length=B-A+1 is irrelevant!).

Given a set of numbers and being allowed to take K of them, how do you maximize the sum? Obviously by picking the K largest numbers. Hence my algorithm is just:
apply the minimal piece of tape spanning the broken cabins
while(more pieces are allowed) {
    remove largest piece of tape linking two neighboring broken cabins
}

Two comments:
- when the largest piece is present more than once, it doesn't matter which one you pick (or pick first);
- if the largest gap were to become zero (i.e. adjacent cabins), there is no need to split further.

Example 1:
Input
4 100 2
20 30 75 80

Connect all [20 30 75 80]
Locate largest link, its 30-75, and remove it: [20 30] [75 80]

Example 2:
Input
6 200 3
20 30 75 80 110 140

Connect all [20 30 75 80 110 140]
Locate largest link, its 30-75, and remove it: [20 30] [75 80 110 140]
Locate largest remaining link,its 80-110 or 110-140, and remove it: [20 30] [75 80] [110 140]
or [20 30] [75 80 110] [140]

:)

PS: you can also treat it bottom up: start with N pieces of length 1, one for every broken cabin (and probably more pieces than you are allowed); now add some tape, until the number of tape islands reaches the allowed number. Here, obviously you first apply tape to the shortest distances. The result will be the same.
   
v6
Comments
Maciej Los 11-Feb-21 7:49am
   
Well, ..., ..., i'm staying speechless.
BIG 5!
Luc Pattyn 11-Feb-21 8:10am
   
Thanks.
I'm a duct tape expert after all. :D
Patrice T 11-Feb-21 14:27pm
   
Your algorithm look pretty much the same as OP described "I tried in many different ways by taking gaps between the broken cabins and by sorting them", but OP is too busy to give us details on how it works and how it fail.
Padala Vamsi ujpNQUXGRi 11-Feb-21 19:39pm
   
You are right, I tried this way already but some test cases are getting failed. I am a full time employee so I'm little busy this week. But I can give you hint since you are all curious. Remember in the question they said tape pieces my overlap.
Luc Pattyn 11-Feb-21 21:25pm
   
So overlap is allowed; how could it result in a lower minimum??? I don't see a need for an overlap.

Some test cases fail? Then give us one of those!
Padala Vamsi ujpNQUXGRi 11-Feb-21 22:11pm
   
Hidden test cases. And the link is dead.
Patrice T 11-Feb-21 22:38pm
   
Tape overlap can't lead to better result.
Show your code and we will try to understand where it fail, or when it fail.
Add a link to original requirement, exact wording may matter.
I'm not sure i understand you well, but the answer is quite obvious...

If the second line represents pairs of cabins, then you need to use below "algorithm":
30 - 20 + 1 = 11
80 - 75 + 1 =  6
----------------
sum:          17

A [+ 1] is needed because you need to "include" the last broken cabin ;)

[EDIT]
Accordingly to...
Quote:

let say if there are 150 cabins and 6 broken cabins 20, 30, 75, 80, 110, 140 and number of pieces to be cut is 3

.....20.....30....75....80.....110....140....
then
-----|-- 11 --|---|-- 6 --|-----|--31--|-----
or
-----|-- 11 --|---|----- 36 -----|---|-1-|---

now the answer is 11+6+31
but another possible ways is <code">56+31+1


In other words, you have to get all possible combinations without repetitions (where the order in the group is matter) of broken cabins which can create a group of 3 (the number of parts of tape).

I'd suggest to get piece of paper and pencil, then you'll be able to write algorithm.

Well... Broken cabins {20, 30, 75, 80, 110, 140} can create the following groups of three elements (items). See the image[^]

There is 10 possible combinations:
1) 6 = 1 + 1 + 4 => 20, 30, {75, 80, 110, 140} => 1+1+66=68
2) 6 = 1 + 2 + 3 => 20, {30, 75}, {80, 110, 140} => 1+46+61=108
3) 6 = 1 + 3 + 2 => 20, {30, 75, 80}, {110, 140} => 1+51+31=83
4) 6 = 1 + 4 + 1 => 20, {30, 75, 80, 110}, 140 => 1+81+1=82
5) 6 = 2 + 1 + 3 => {20, 30}, 75, {80, 110, 140} => 11+1+61=73
6) 6 = 2 + 2 + 2 => {20, 30}, {75, 80}, {110, 140} => 11+6+31=48
7) 6 = 2 + 3 + 1 => {20, 30}, {75, 80, 110}, 140 => 11+36+1=48
8) 6 = 3 + 1 + 2 => {20, 30, 75}, 80, {110, 140} => 56+1+31=88
9) 6 = 3 + 2 + 1 => {20, 30, 75}, {80, 110}, 140 => 56+31+1=88
10) 6 = 4 + 1 + 1 => {20, 30, 75, 80}, 110, 140 => 56+1+1=58



Good luck!
   
v4
Comments
Padala Vamsi ujpNQUXGRi 10-Feb-21 4:00am
   
let say if there are 150 cabins and 6 broken cabins 20, 30, 75, 80, 110, 140 and number of pieces to be cut is 3

.....20.....30....75....80.....110....140....
then
-----|-- 11 --|---|-- 6 --|-----|--31--|-----
or
-----|-- 11 --|---|----- 36 -----|---|-1-|---
now the answer is 11+6+31
but another possible ways is
56+31+1
Quote:
I tried in many different ways by taking gaps between the broken cabins and by sorting them

Per your wording, it is exactly how to solve the problem, but devil hide in details.
You need to show us how you solve the problem with the 2 examples, but you show all the calculation when number of pieces of tape vary from 1 to number of broken cabins.
Details that matters are how calculation evolve when you add 1 cut in tape.
Quote:
I tried in many different ways by taking gaps between the broken cabins

What is your definition of gap ?
Quote:
but some cases are not getting solve

Preferably show the calculation on an example where you fail to get correct answer.

Similar problem: Problem - 1110b - Codeforces[^]
   
v4
That was very interesting task, which was worth to spend some time to resolve it.

Here is a c# solution. Entire code was written and tested in LinqPad[^]. That does not contain method responsible for reading an input. So, feel free to improve it.


C#
//https://www.codeproject.com/Questions/5294427/Finding-minimum-length-of-tape-required

void Main()
{
	//broken cabins
	List<int> bc = new List<int>(){20, 30, 75, 80, 110, 140};
	//get all digits which sum is equal to number of broken cabins
	//in this case 6 - from {1,1,4}, {1, 2, 3}, ... {2, 2, 2} up to {4, 1, 1}
	int[,] comb = FactorizeUpToSum(6,3);
	//get dimension of an array
	int dmn = comb.Rank;
	//create a list of integers, to store all available sums
	List<int> allSums = new List<int>();
	//loop through the items in array
	for(int i=comb.GetLowerBound(0); i<comb.GetUpperBound(0); i++)
	{
		//length of tape used to cover broken cabins
		int sum = 0;
		//helper variable
		int k = 0;
		//loop through the items in a 'row'
		for(int j=0; j<=dmn; j++)
		{
			//calculate the distance between numbers
			sum += GetDistance(bc.Skip(k).Take(comb[i,j]));
			//increase number of "rows" to skip next time
			k+=comb[i,j];
		}
		//add sum onto the list
		allSums.Add(sum);
	}
	//get minimum length of tape
	int minSum = allSums.Min();
	Console.WriteLine($"Minimum length of tape necessary to cover {bc.Count} cabins in {dmn+1} pieces is {minSum} m.");
}



/// <summary>
/// returns a set of numbers which sum is egual to ...
/// for example: if [6] have to be a set of [3] numbers then 
/// below function returns {1,1,4}, {1,2,3}, {1,3,2}, ... {2,2,2}, up to {4,1,1}
/// </summary>
public int[,] FactorizeUpToSum(int sum, int cnt)
{
	int iniVal = Convert.ToInt32(new string('1', cnt)); //111
	int finVal = Convert.ToInt32(new string(Convert.ToChar($"{sum}"), cnt)); //666
	//calculate the lower bound of an array
	int upar = Combinations(sum, cnt)-Combinations(sum-1, cnt);
	int[,] items = new int[upar, cnt]; //create an array
	int i = 0;
	//loop through the numbers 111 to 666
	for(int curVal=iniVal; curVal<=finVal; curVal++)
	{
		//split number into an array of digits: 111 => {1,1,1}; 112 => {1,1,2} and so on...
		int[] tmp = curVal.ToString().Select(x=> ((int)x)-48).ToArray();
		if(tmp.Sum(x=>x)==sum && tmp.All(x=>x!=0))
		{
			for(int j=0; j<cnt; j++)
				items[i, j] = tmp[j];
			i++;
		}
	}
	return items;
}

public int Combinations(int cntGroup, int cntSets)
{
	return Factorial(cntGroup)/(Factorial(cntSets)*Factorial(cntGroup-cntSets));
}

public int Factorial(int nu)
{
	int f = 1;
	for(int i=1; i<=nu; i++)
		f*=i;
	return f;
}

/// <summary>
/// returs distance between numbers
/// </summary>
public int GetDistance(object o)
{
	int[] arr = ((IEnumerable)o).Cast<object>()
                 .Select(x => (int)x)
                 .ToArray();
	if(arr.Length>1)
		return (int)arr[arr.Length-1] - (int)arr[0] + 1;
	else
		return 1;
}


Note: issue with calculating the lower bound of an array in FactorizeUpToSum has been resolved
   
v3
Comments
Patrice T 11-Feb-21 6:59am
   
2 solutions ?
Beware, I have been downvoted for than that. :)
Maciej Los 11-Feb-21 7:17am
   
Well, the reason i submitted second solution is very simple: the first one is about theory, the second - practical usage ;)
THanks for warning.
Padala Vamsi ujpNQUXGRi 11-Feb-21 8:33am
   
Thank you for the time.
Padala Vamsi ujpNQUXGRi 11-Feb-21 8:33am
   
Thank you for your time.
I posted a recursive solution on AskAvan.com (Finding minimum length of tape required. | Ask a Professional Developer![]) but I DON'T know if it's right. I wish we had more test cases so I could make sure.



The idea is this:

You loop through all the broken cabins and place the end of the first tape encompassing all broken cabins before it and then make a recursive call for the remaining cabins

If the total length is less than the minimum length update the minimum length

At the end return the minimum length

Below is the (Java) code in case my vague explanation above is not enough. Keep in mind this has not been tested extensively and could definitely be wrong. I wish we had an official leetcode challenge where I could run my code...but oh well.

SPACE INTENTIONALLY LEFT BLANK

Java
public static int minTape(int numBrokenCabins, int totalCabins, int numTapeCuts, int[] brokenCabins){
	    int firstCabin = brokenCabins[0];
	    int maxLength =  brokenCabins[brokenCabins.length-1] - firstCabin + 1;
	    int minLength = maxLength;
	    
	    // Base cases
        if(numTapeCuts == 1){
            return maxLength;
        }
        if(numTapeCuts == numBrokenCabins){
            return numBrokenCabins;
        }
        
        for(int i = 0; i < brokenCabins.length-1; i++){
            int currentCabin = brokenCabins[i];
            int thisLength = currentCabin - firstCabin + 1;
            int newNumBrokenCabins = numBrokenCabins - i - 1;
            int newTotalCabins = totalCabins;
            int newNumTapeCuts = numTapeCuts - 1;
            int[] newBrokenCabins = Arrays.copyOfRange(brokenCabins, i+1, brokenCabins.length);
            if(newNumBrokenCabins < newNumTapeCuts){
                break;
            }
            int totalLength = thisLength + minTape(newNumBrokenCabins, newTotalCabins, newNumTapeCuts, newBrokenCabins);
            minLength = totalLength < minLength ? totalLength : minLength;
        }
        
        return minLength;
	}



You can also see this code in action here:

[Online GDB ]
   

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)




CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900