Minimum Cost to Cut the Stick

Problem Statement You are given a stick of length N units. You are also provided with an array cuts of size C, where each element cuts[i] represents a marking on the stick where a cut needs to be made. It is necessary to make cuts at all the specified markings. Whenever you make a cut, you incur a cost. This cost is equal to the length of the stick on which the cut is being made. For example, if you have a stick of length 10 and you make a cut at mark 5, the cost incurred is 10. This cut divides the stick into two parts, one from 0 to 5 and another from 5 to 10. Your task is to find the minimum total cost incurred to cut the stick at all the given cut points. Note: The stick has markings from 0 to N. The cuts array contains values between 0 and N, exclusive. Input Specification The first line contains an integer N, representing the total length of the stick. The second line contains an integer C, representing the number of cuts to be made. The third line contains C space separated integers, representing the elements of the cuts array. Output Specification Print a single integer, the minimum cost incurred to cut the stick at all specified points. Constraints 1 <= N <= 10^9 1 <= C <= 100 0 < cuts[i] < N All cuts[i] are distinct. Sample Test Case Input: Output: Explanation: Given stick of length 7 and cuts at [3, 5, 1, 4]. To minimize cost, we can sort the cuts: [1, 3, 4, 5]. Add 0 and 7 to cuts: [0, 1, 3, 4, 5, 7]. Consider making the first cut at mark 4 (original stick length 7): Cost = 7. Remaining sticks: (0,4) and (4,7). Cuts: (1,3) and (5). For stick (0,4) with cuts (1,3): Cut at 1: Cost = 4. Remaining sticks: (0,1) and (1,4). Cuts: () and (3). Cut at 3: Cost = 3. Remaining sticks: (1,3) and (3,4). Cuts: () and (). Total for (0,4): 4 + 3 = 7 For stick (4,7) with cut (5): Cut at 5: Cost = 3. Remaining sticks: (4,5) and (5,7). Cuts: () and (). Total for (4,7): 3 Total cost: 7 (initial cut) + 7 (left subproblem) + 3 (right subproblem) = 17. Alternatively, consider making the first cut at mark 3 (original stick length 7): Cost = 7. Remaining sticks: (0,3) and (3,7). Cuts: (1) and (4,5). For stick (0,3) with cut (1): Cut at 1: Cost = 3. Remaining sticks: (0,1) and (1,3). Cuts: () and (). Total for (0,3): 3 For stick (3,7) with cuts (4,5): Cut at 4: Cost = 4. Remaining sticks: (3,4) and (4,7). Cuts: () and (5). Cut at 5: Cost = 3. Remaining sticks: (4,5) and (5,7). Cuts: () and (). Total for (3,7): 4 + 3 = 7 Total cost: 7 (initial cut) + 3 (left subproblem) + 7 (right subproblem) = 17. Let's try another order: Cut at 1 first (cost 7). Remaining sticks: (0,1) and (1,7). Cuts: () and (3,4,5). For stick (1,7) with cuts (3,4,5): Cut at 3 (cost 6). Remaining sticks: (1,3) and (3,7). Cuts: () and (4,5). For (3,7) with (4,5): Cut at 4 (cost 4). Remaining sticks: (3,4) and (4,7). Cuts: () and (5). For (4,7) with (5): Cut at 5 (cost 3). Remaining sticks: (4,5) and (5,7). Cuts: () and (). Total for (4,7) with (5): 3 Total for (3,7) with (4,5): 4 + 3 = 7 Total for (1,7) with (3,4,5): 6 + 7 = 13 Total cost: 7 + 13 = 20. Minimum cost is found by considering all possible cut orders. The example output 16 implies a specific optimal order. For the given example, the optimal order can be: 1. Cut at 4 (cost 7). Remaining sticks: (0,4) and (4,7). Cuts: [1,3] for (0,4) and [5] for (4,7). 2. For stick (0,4) with cuts [1,3]: Cut at 1 (cost 4). Remaining sticks: (0,1) and (1,4). Cuts: [] and [3]. For stick (1,4) with cut [3]: Cut at 3 (cost 3). Total for (1,4): 3. Total for (0,4): 4 + 3 = 7. 3. For stick (4,7) with cut [5]: Cut at 5 (cost 3). Total for (4,7): 3. Total cost: 7 + 7 + 3 = 17. The provided sample output of 16 suggests a different optimal sequence or interpretation. Let's re verify the sample output explanation from a standard source for this problem: cuts = [1, 3, 4, 5], N = 7 (0 to 7 stick) Initial cuts array becomes [0, 1, 3, 4, 5, 7]. If we cut at cuts[3] (which is 4) first: Cost = cuts[5] cuts[0] = 7 0 = 7. Subproblems: (0, 4) with cuts [1, 3] and (4, 7) with cut [5]. For (0, 4) with [1, 3] (i.e., cuts[0..3] where cuts[0]=0, cuts[1]=1, cuts[2]=3, cuts[3]=4): If we cut at cuts[1] (which is 1): Cost = cuts[3] cuts[0] = 4 0 = 4. Subproblems: (0, 1) and (1, 4). For (1, 4) we have cut [3]. For (1, 4) with [3]: Cut at cuts[2] (which is 3): Cost = cuts[3] cuts[1] = 4 1 = 3. Total cost for (1, 4): 3. Total cost for (0, 4): 4 + 3 = 7. For (4, 7) with [5] (i.e., cuts[3..5] where cuts[3]=4, cuts[4]=5, cuts[5]=7): If we cut at cuts[4] (which is 5): Cost = cuts[5] cuts[3] = 7 4 = 3. Total cost for (4, 7): 3. Total cost = 7 (initial) + 7 (left subproblem) + 3 (right subproblem) = 17. Let's try cutting at cuts[2] (which is 3) first: Cost = cuts[5] cuts[0] = 7 0 = 7. Subproblems: (0, 3) with cut [1] and (3, 7) with cuts [4, 5]. For (0, 3) with [1] (i.e., cuts[0..2] where cuts[0]=0, cuts[1]=1, cuts[2]=3): Cut at cuts[1] (which is 1): Cost = cuts[2] cuts[0] = 3 0 = 3. Total cost for (0, 3): 3. For (3, 7) with [4, 5] (i.e., cuts[2..5] where cuts[2]=3, cuts[3]=4, cuts[4]=5, cuts[5]=7): Cut at cuts[3] (which is 4): Cost = cuts[4] cuts[2] = 5 3 = 2. Subproblems: (3, 4) and (4, 7). For (4, 7) we have cut [5]. For (4, 7) with [5] (i.e., cuts[3..5] where cuts[3]=4, cuts[4]=5, cuts[5]=7): Cut at cuts[4] (which is 5): Cost = cuts[5] cuts[3] = 7 4 = 3. Total cost for (4, 7): 3. Total cost for (3, 7): 2 + 3 = 5. Total cost = 7 (initial) + 3 (left subproblem) + 5 (right subproblem) = 15. Ah, the sample output 16 is still not matching. Let's trace the example [3, 5, 1, 4] and N=7 again with the provided logic: cuts = [0, 1, 3, 4, 5, 7]. The indices in the function f(i, j) refer to the indices in this modified cuts array. f(1, c) where c is the original number of cuts. Here c=4. So, f(1, 4) will be called. cuts array: [0, 1, 3, 4, 5, 7] Indices: [0, 1, 2, 3, 4, 5] Original c is 4. f(1, 4) implies considering cuts[1] to cuts[4], which are [1, 3, 4, 5]. The cost for f(i, j) is cuts[j+1] cuts[i 1]. So for f(1, 4), cost is cuts[4+1] cuts[1 1] = cuts[5] cuts[0] = 7 0 = 7. Options for ind (cut point index in sorted cuts array, from i to j): 1. ind = 1 (cut at cuts[1]=1) Cost = 7 + f(1, 0) + f(2, 4) f(1, 0) is base case 0. f(2, 4) means cuts [3, 4, 5]. Cost for f(2,4) = cuts[4+1] cuts[2 1] = cuts[5] cuts[1] = 7 1 = 6. f(2, 4) will recursively call for ind = 2, 3, 4. If f(2,4) cuts at cuts[2]=3: Cost = 6 + f(2, 1) + f(3, 4) f(2, 1) is base case 0. f(3, 4) means cuts [4, 5]. Cost for f(3,4) = cuts[4+1] cuts[3 1] = cuts[5] cuts[2] = 7 3 = 4. f(3, 4) will recursively call for ind = 3, 4. If f(3,4) cuts at cuts[3]=4: Cost = 4 + f(3, 2) + f(4, 4) f(3, 2) is base case 0. f(4, 4) means cut [5]. Cost for f(4,4) = cuts[4+1] cuts[4 1] = cuts[5] cuts[3] = 7 4 = 3. f(4, 4) will recursively call for ind = 4. If f(4,4) cuts at cuts[4]=5: Cost = 3 + f(4, 3) + f(5, 4) Both base cases 0. So, f(4,4) returns 3. Thus, f(3,4) with cut at cuts[3]=4 gives 4 + 0 + 3 = 7. If f(3,4) cuts at cuts[4]=5: Cost = 4 + f(3, 3) + f(5, 4) f(5, 4) is base case 0. f(3, 3) means cut [4]. Cost for f(3,3) = cuts[3+1] cuts[3 1] = cuts[4] cuts[2] = 5 3 = 2. f(3, 3) will recursively call for ind = 3. If f(3,3) cuts at cuts[3]=4: Cost = 2 + f(3, 2) + f(4, 3) Both base cases 0. So, f(3,3) returns 2. Thus, f(3,4) with cut at cuts[4]=5 gives 4 + 2 + 0 = 6. Minimum for f(3,4) is 6. So, f(2,4) with cut at cuts[2]=3 gives 6 + 0 + 6 = 12. If f(2,4) cuts at cuts[3]=4: Cost = 6 + f(2, 2) + f(4, 4) f(2, 2) means cut [3]. Cost for f(2,2) = cuts[2+1] cuts[2 1] = cuts[3] cuts[1] = 4 1 = 3. f(2, 2) returns 3. f(4, 4) returns 3 (calculated above). So, f(2,4) with cut at cuts[3]=4 gives 6 + 3 + 3 = 12. If f(2,4) cuts at cuts[4]=5: Cost = 6 + f(2, 3) + f(5, 4) f(5, 4) is base case 0. f(2, 3) means cuts [3, 4]. Cost for f(2,3) = cuts[3+1] cuts[2 1] = cuts[4] cuts[1] = 5 1 = 4. f(2, 3) will recursively call for ind = 2, 3. If f(2,3) cuts at cuts[2]=3: Cost = 4 + f(2, 1) + f(3, 3) f(2, 1) is base case 0. f(3, 3) returns 2 (calculated above). So, f(2,3) with cut at cuts[2]=3 gives 4 + 0 + 2 = 6. If f(2,3) cuts at cuts[3]=4: Cost = 4 + f(2, 2) + f(4, 3) f(4, 3) is base case 0. f(2, 2) returns 3 (calculated above). So, f(2,3) with cut at cuts[3]=4 gives 4 + 3 + 0 = 7. Minimum for f(2,3) is 6. So, f(2,4) with cut at cuts[4]=5 gives 6 + 6 + 0 = 12. Minimum for f(2,4) is 12. Thus, f(1, 4) with cut at cuts[1]=1 gives 7 + 0 + 12 = 19. 2. ind = 2 (cut at cuts[2]=3) Cost = 7 + f(1, 1) + f(3, 4) f(1, 1) means cut [1]. Cost for f(1,1) = cuts[1+1] cuts[1 1] = cuts[2] cuts[0] = 3 0 = 3. f(1, 1) returns 3. f(3, 4) returns 6 (calculated above). Thus, f(1, 4) with cut at cuts[2]=3 gives 7 + 3 + 6 = 16. 3. ind = 3 (cut at cuts[3]=4) Cost = 7 + f(1, 2) + f(4, 4) f(4, 4) returns 3 (calculated above). f(1, 2) means cuts [1, 3]. Cost for f(1,2) = cuts[2+1] cuts[1 1] = cuts[3] cuts[0] = 4 0 = 4. f(1, 2) will recursively call for ind = 1, 2. If f(1,2) cuts at cuts[1]=1: Cost = 4 + f(1, 0) + f(2, 2) f(1, 0) is base case 0. f(2, 2) returns 3 (calculated above). So, f(1,2) with cut at cuts[1]=1 gives 4 + 0 + 3 = 7. If f(1,2) cuts at cuts[2]=3: Cost = 4 + f(1, 1) + f(3, 2) f(3, 2) is base case 0. f(1, 1) returns 3 (calculated above). So, f(1,2) with cut at cuts[2]=3 gives 4 + 3 + 0 = 7. Minimum for f(1,2) is 7. Thus, f(1, 4) with cut at cuts[3]=4 gives 7 + 7 + 3 = 17. 4. ind = 4 (cut at cuts[4]=5) Cost = 7 + f(1, 3) + f(5, 4) f(5, 4) is base case 0. f(1, 3) means cuts [1, 3, 4]. Cost for f(1,3) = cuts[3+1] cuts[1 1] = cuts[4] cuts[0] = 5 0 = 5. f(1, 3) will recursively call for ind = 1, 2, 3. If f(1,3) cuts at cuts[1]=1: Cost = 5 + f(1, 0) + f(2, 3) f(2, 3) returns 6 (calculated above). So, f(1,3) with cut at cuts[1]=1 gives 5 + 0 + 6 = 11. If f(1,3) cuts at cuts[2]=3: Cost = 5 + f(1, 1) + f(3, 3) f(1, 1) returns 3. f(3, 3) returns 2. So, f(1,3) with cut at cuts[2]=3 gives 5 + 3 + 2 = 10. If f(1,3) cuts at cuts[3]=4: Cost = 5 + f(1, 2) + f(4, 3) f(1, 2) returns 7. f(4, 3) is base case 0. So, f(1,3) with cut at cuts[3]=4 gives 5 + 7 + 0 = 12. Minimum for f(1,3) is 10. Thus, f(1, 4) with cut at cuts[4]=5 gives 7 + 10 + 0 = 17. Comparing all options for f(1, 4): 19, 16, 17, 17. The minimum is 16. So the example output is correct and my manual trace confirms it when following the recursive formula strictly.