There are N students in a class with known amount of programming skills (here the skill of a person is scored with a number). Now the lecturer wants to form two programming teams in the class in such a way that their overall difference in programming skill in minimal.
Your task is to help the lecturer find the minimum such achievable difference. (Note : The sizes of groups do not have to be equal)
Input Format
The first input line has an integer N the number of students.
The next line has N integers p1​,p2​,...,pn​ the programming skill of each student.
Constraints
1≤N≤20
1≤pi​≤109
Output Format
Output one integer the minimum difference between the skills of the groups.
Sample Inputs:
Input
10
603 324 573 493 659 521 654 70 718 257
Output
2
First Attempt — Greedy Algorithm
My first thought is to by simply using greedy algorithm, which works by first sorting the numbers in descending order, thus adding the numbers on both arrays. Thus, inserting the next number into smaller array to try balancing out.
Meanwhile, this won't work at all as this method only gives approximation, not exact minimum difference. For sample input, this method would output 62 instead of 2, which is not viable solution.
But this could be the first start before opting to better strategy.
def min_partition_difference(arr):
arr.sort(reverse=True)
sum1, sum2 = 0, 0
for num in arr:
if sum1 < sum2:
sum1 += num
else:
sum2 += num
return abs(sum1 - sum2)
i = int(input())
arr = list(map(int, input().split()))
print(min_partition_difference(arr))
Second Attempt — MiTM Dynamic Programming
After realizing that greedy algorithm won't work anyways, I tried to attempt this question by using dynamic programming instead. First, we know that the most optimized difference is 0, which is when both array is same. By making both array is same, the most optimized value should be the half of the sum of the inputs.
After getting the optimized target, now we can use iterative method to find if the combination of subset is able to reach the target. After taking all pairs of targets possible, we can simply divide the input array into 2 subsets (with all possible ways), compute all possible sums on each half, and lastly getting the best way to combine the sum as close as the target.
Although sounds feasible, meanwhile it defeats itself (TLE) when the test case values are large. Therefore, we have to think another better way to attempt this question.
def min_partition_difference(arr):
total_sum = sum(arr)
n = len(arr)
half_sum = total_sum // 2
dp = [False] * (half_sum + 1)
dp[0] = True
for num in arr:
for j in range(half_sum, num - 1, -1):
if dp[j - num]:
dp[j] = True
for s in range(half_sum, -1, -1):
if dp[s]:
return total_sum - 2 * s
i = int(input())
arr = list(map(int, input().split()))
print(min_partition_difference(arr))
Final Solution — Optimize with binary search, combinations
If we somehow utilize the ready-made library, maybe it can make it faster in some reason. The previous attempt hits the TLE as it took too much time to traverse all possible pairs.
After thinking a bit, I think implementing a binary search during search phase, and introducing the combination library could help optimizing the problem.
Here's the final solution, which passed all test cases:
from itertools import combinations
import bisect
def subset_sums(arr):
sums = set()
n = len(arr)
for i in range(n + 1):
for comb in combinations(arr, i):
sums.add(sum(comb))
return sorted(sums)
def min_partition_difference(arr):
total_sum = sum(arr)
half_sum = total_sum // 2
n = len(arr)
left, right = arr[:n//2], arr[n//2:]
left_sums = subset_sums(left)
right_sums = subset_sums(right)
min_diff = float('inf')
for s in left_sums:
idx = bisect.bisect_right(right_sums, half_sum - s) - 1
if idx >= 0:
best_s = right_sums[idx] + s
min_diff = min(min_diff, abs(total_sum - 2 * best_s))
return min_diff
i = int(input())
arr = list(map(int, input().split()))
print(min_partition_difference(arr))