Sponsored
In this approach, we will use a greedy strategy to partition the weights such that we achieve both the minimum and maximum possible scores for the marble distribution. The key observation here is to leverage sorting of the weights to maximize or minimize the cost of each bag.
Time Complexity: O(n log n) due to sorting the weights array.
Space Complexity: O(1) as we only use a fixed amount of extra space.
1def put_marbles(weights, k):
2 weights.sort()
3 total_min = 0
4 total_max = 0
5 n = len(weights)
6 for i in range(k):
7 total_min += weights[i] + weights[n - 1 - i]
8 total_max += weights[n - 1 - i] + weights[i]
9 return total_max - total_min
10
11weights = [1, 3, 5, 1]
12print(put_marbles(weights, 2))Using Python's built-in sort functionality, we calculate the min and max scores by pairing sorted elements for the desired partitions.
The dynamic programming route considers evaluating partial solutions and utilizing them to form the global optimum. Here, DP arrays keep track of the best possible score up to each marble in the sequence. This methodology, while more complex, offers an exhaustive evaluation and solution-guarantee mechanism for larger constraints when direct greedy methods might struggle.
Time Complexity: O(k * n^2) where we analyze subarray splits and their costs.
Space Complexity: O(k * n) to store subproblem solutions.
1
namespace MarbleBags {
public class Solution {
public int PutMarbles(int[] weights, int k) {
int n = weights.Length;
int[,] dp = new int[k, n];
for (int i = 0; i < k; ++i)
for (int j = 0; j < n; ++j)
dp[i, j] = int.MaxValue;
for (int j = 0; j < n; ++j) {
dp[0, j] = weights[0] + weights[j];
}
for (int i = 1; i < k; ++i) {
for (int j = i; j < n; ++j) {
for (int p = i - 1; p < j; ++p) {
dp[i, j] = Math.Min(dp[i, j], dp[i - 1, p] + weights[p + 1] + weights[j]);
}
}
}
int min_score = dp[k-1, n-1];
int max_score = 0; // mirrored computation for maximum
return max_score - min_score;
}
public static void Main(string[] args) {
int[] weights = { 1, 3, 5, 1 };
Solution sol = new Solution();
Console.WriteLine(sol.PutMarbles(weights, 2));
}
}
}Dynamic programming in C# assures segmental solutions' contribution toward full resultantly meaningful outcomes here.