cppAcademy
FROM LEARNING TO COMPETING

Proficient.
Put your skills to the test.

Bulgarian Informatics Group B · 2009–2026

217 independently explained problems: 54 Municipal, 54 Regional and 109 National. Start with the easier tasks and work upwards. Difficulty labels are learning estimates, not official ratings; Group B also includes challenging national-level problems. National-round tasks shared by Groups A and B are included. Years follow Arena’s competition-season labels. Source clarifications and special grader requirements are noted on affected tasks.
GROUP B2023 · MediumSubset sum

Balanced Partition

National Olympiad — Regional round (2023 season)

Submission name: min.cpp

Solve in Editor →

Problem summary

Partition the supplied positive integers into two disjoint groups minimizing the absolute difference of their sums. Treat equal input occurrences as separate elements.

Input

n, then n positive integers.

Output

The smallest possible absolute sum difference.

Constraints

1 < n < 300; 0 < a[i] < 10000.

Worked example

An independently prepared example for this explanation.

Input

5
7 3 10 5 7

Output

2

Solution analysis

  1. If the total is T and one group sums to s, the difference is |T−2*s|. By swapping the groups, we may require s≤T/2, so choose the largest attainable subset sum not exceeding T/2.
  2. Represent attainable sums as bits. Initially only bit zero is set. For an element v, update reachable |= reachable << v. The shift appends this element to every old subset, while OR preserves the subsets omitting it.
  3. In the sample, T=32. Sum 16 is unattainable, but 15 is attained by 10+5. The other group is 7+3+7=17, giving the optimal difference 2.

Why it works

After processing each element, a subset either excludes that occurrence and keeps an old sum, or includes it and adds its value to an old sum. The bitset update describes exactly these possibilities, so induction proves reachability is exact. For s≤T/2, T−2*s decreases as s increases, proving that the largest reachable such s is optimal.

Complexity: O(n*T/w + T) time and O(T) bits, with machine word size w for bitset shifts; the implementation uses a fixed bound of 3000001 bits because T < 3000000.

Watch out. Use each input occurrence at most once. The sample repeats 7 despite calling the input a set; preserve every occurrence. Do not use a greedy split.

Commented C++17 solution

An independently written complete program with standard headers.

#include<iostream>
#include<vector>
#include<bitset>
// Algorithm: If the total is T and one group sums to s, the difference is |T−2*s|.
using namespace std;
int main(){
    int n;
    cin>>n;
    vector<int>values(n);
    int total=0;
    for(int&value:values){
        cin>>value;
        total+=value;
    }
    bitset<3000001>reachable;
    reachable[0]=true;
    for(int value:values){
        reachable|=reachable<<value;
    }
    for(int sum=total/2;sum>=0;--sum){
        if(reachable[sum]){
            cout<<total-2*sum<<'\n';
            break;
        }
    }
}

Source: Arena Olimpiici ↗