These are the notes for Competitive Programming episode 18. An original problem, Exact Budget, asks how many sets of sponsor offers add up to exactly the cost of a college fest stage. Last episode's bitmask loop tries every subset: it is right on the sample and gets Time Limit Exceeded on 40 offers, because 40 offers have 2^40 (over a trillion) subsets. A tunnel dug from both ends of a mountain shows the way out: split the offers into two halves, list every sum of each half (about a million each), sort one side, and for every left sum x count the right sums equal to S − x, the way you look a word up in a dictionary. That is meet in the middle. Then a hand trace, n = 40 in a fraction of a second, a stress test against the brute force, and three bugs with real outputs. Every C++ example was compiled with g++ -O2 -std=c++17 main.cpp -o main (g++ 13, the same command as the SyntaxPilot compiler); all outputs below are real.
The real-life hook: the fest sponsor puzzle
Your college fest needs a stage that costs exactly ₹10 lakh: not more, the committee won't allow leftovers. Sponsors make offers of 2, 3, 5 and 7 lakh. You take an offer whole, or not at all. How many different sets of offers add up to exactly 10?
- 3 + 7 = 10
- 2 + 3 + 5 = 10
Two ways. Easy for four sponsors. But a big fest has forty sponsors, and forty offers make 2^40 ≈ 1.1·10^12 sets: over a trillion.
Words you need first
- A subset is any choice of items where each item is either in or out, and order does not matter. From {2, 3, 5, 7}, {3, 7} is a subset, and {7, 3} is the same subset. The empty choice {} is a subset too. n items have 2^n subsets (2 choices per item).
- A subset sum is the total of the items in a subset. The subset {2, 3, 5} has sum 10; the empty subset has sum 0.
- A bitmask (episode 17) is an integer whose bits say which items are in: bit
i= 1 means itemiis chosen. For 4 items,mask = 6is binary0110: items 1 and 2 are in, so witha = {2, 3, 5, 7}it is the subset {3, 5}. - Exponential complexity means the work grows like 2^n: every extra item doubles it. 2^20 ≈ 10^6 is fine; 2^40 ≈ 10^12 is not.
The problem: Exact Budget
Problem R · Exact Budget (written for this course). You are given
noffersa[0 … n − 1]and a targetS. Count the subsets of offers whose sum is exactlyS.
1 ≤ n ≤ 40,1 ≤ a[i] ≤ 10^9,1 ≤ S ≤ 4·10^10.Input:
nandSon the first line, then thenoffers. Output: one number, the count.
| Sample input | Sample output | Why |
|---|---|---|
4 102 3 5 7 |
2 |
{3, 7} and {2, 3, 5} |
A sum can reach 40 · 10^9 = 4·10^10, far beyond the largest int (about 2.1·10^9), so every sum must be a long long. The answer itself can also be huge (see n = 40 below), so it is a long long too.
Brute force: every mask (Time Limit Exceeded)
Every number from 0 to 2^n − 1 is one subset. Add up the ticked items and compare with S.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
ll S;
cin >> n >> S;
vector<ll> a(n);
for (auto &x : a) cin >> x;
ll ans = 0;
for (ll mask = 0; mask < (1LL << n); mask++) {
ll sum = 0;
for (int i = 0; i < n; i++)
if (mask >> i & 1) sum += a[i];
if (sum == S) ans++;
}
cout << ans << "\n";
return 0;
}
| Input | Output |
|---|---|
the sample (4 10 / 2 3 5 7) |
2 |
40 400 / 1 2 3 … 40 |
Time Limit Exceeded (2^40 masks × 40 steps ≈ 4.4·10^13) |
Rule of thumb: plain masks are fine up to n ≈ 20.
The idea: dig the tunnel from both ends
| Building a mountain tunnel | In our problem |
|---|---|
| One team digs 2 km: takes 20 months | one huge search over all 2^n subsets |
| Two teams, 1 km each, from both ends | two halves of n/2 items: 2^(n/2) sums each |
| They meet in the middle, and the tunnel is done | match left + right = S with a fast lookup |
For a tunnel, two teams halve the time. For us it is far better than half, because the work is exponential: 2^40 ≈ 10^12, but 2 · 2^20 ≈ 2·10^6.
The split observation
- Split the array:
L= the firstn/2items,R= the rest. - Every subset of all items = (a subset of L) + (a subset of R). The two choices are independent choices: what you pick on the left does not limit what you can pick on the right. Example: {2, 3, 5} = {2, 3} from the left + {5} from the right.
- List all 2^(n/2) sums of each half.
- If the left part sums to
x, the right part must sum to exactlyS − x. So for each left sumx, count how many right sums equalS − x, and add them up.
We never multiply the halves together (that would be 2^20 × 2^20 = 2^40 again). We only match them.
Listing every subset sum of a half
Start with just {0} (the empty choice). For each new item x, copy every sum so far with x added. Each item doubles the list.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
vector<ll> sums(vector<ll> v) {
vector<ll> s = {0};
for (ll x : v) {
int m = s.size();
for (int i = 0; i < m; i++) s.push_back(s[i] + x);
}
return s;
}
int main() {
vector<ll> left = {2, 3}, right = {5, 7};
for (ll x : sums(left)) cout << x << " ";
cout << "<- left sums\n";
for (ll x : sums(right)) cout << x << " ";
cout << "<- right sums\n";
return 0;
}
Real output:
0 2 3 5 <- left sums
0 5 7 12 <- right sums
Four sums per half: 2^2. For {2, 3}: start {0} → add 2 → {0, 2} → add 3 → {0, 2, 3, 5}.
Why int m = s.size(); first? Because push_back makes s grow during the loop; we must only copy the sums that existed before this item.
Hand trace on the sample
S = 10, left {2, 3}, right {5, 7}. Right sums sorted: 0 5 7 12.
Left sum x |
Need S − x |
Found in right sums? | Subset |
|---|---|---|---|
| 0 | 10 | no (0 matches) | |
| 2 | 8 | no (0 matches) | |
| 3 | 7 | yes (1 match) | {3} + {7} |
| 5 | 5 | yes (1 match) | {2, 3} + {5} |
Total: 2, the same two subsets as before.
The fast lookup: a dictionary
| A paper dictionary | In code |
|---|---|
| Words are in alphabetical order: that's why lookup is fast | sorting: sort(Bs.begin(), Bs.end()), once |
| Open in the middle, go left or right, halving the pages | binary search (episode 11): about log2(m) steps, 20 for a million |
| The same word can have several meanings: count all of them | equal_range: the first and last-plus-one position of a value |
- Sorting puts values in increasing order:
7 0 12 5→0 5 7 12.std::sorttakes O(m log m). - Binary search finds a value in sorted data by looking at the middle and throwing away the half that cannot contain it.
binary_search(b, e, v)only answers yes or no. lower_bound(b, e, v)returns the first position whose value is ≥ v;upper_bound(b, e, v)returns the first position whose value is > v. Both are binary searches.equal_range(b, e, v)returns the pair(lower_bound, upper_bound). Every element between them equalsv, sohi − lois how many timesvappears. Example: in0 1 1 2,equal_range(…, 1)gives positions 1 and 3, so 1 appears 3 − 1 = 2 times.
The full solution
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
vector<ll> sums(vector<ll> v) {
vector<ll> s = {0};
for (ll x : v) {
int m = s.size();
for (int i = 0; i < m; i++) s.push_back(s[i] + x);
}
return s;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
ll S;
cin >> n >> S;
vector<ll> a(n);
for (auto &x : a) cin >> x;
vector<ll> L(a.begin(), a.begin() + n / 2);
vector<ll> R(a.begin() + n / 2, a.end());
vector<ll> A = sums(L), Bs = sums(R);
sort(Bs.begin(), Bs.end());
ll ans = 0;
for (ll x : A) {
auto [lo, hi] = equal_range(Bs.begin(), Bs.end(), S - x);
ans += hi - lo;
}
cout << ans << "\n";
return 0;
}
auto [lo, hi] = … is a C++17 structured binding: it unpacks the pair returned by equal_range into two iterators.
| Input | Output | Why |
|---|---|---|
4 10 / 2 3 5 7 (sample) |
2 |
the trace above |
1 5 / 5 |
1 |
n = 1: the left half is empty, its only sum is 0, the right half does all the work |
5 100 / 1 2 3 4 5 |
0 |
15 is the most you can reach |
4 2 / 1 1 1 1 |
6 |
any two of the four: C(4, 2) = 6 |
6 3000000000 / six × 1000000000 |
20 |
any three of the six: C(6, 3) = 20 |
6 9 / 9 1 8 2 7 3 |
3 |
{9}, {1, 8}, {2, 7} |
40 400 / 1 2 3 … 40 |
5779890186 |
in about 0.2 s (it timed out with masks) |
Almost six billion subsets of 1 … 40 add up to 400, and we counted them without visiting a single one.
Stress test
The mask brute force against meet in the middle, on 1000 random arrays of up to 12 small offers (values 1 … 10, so many sums repeat):
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
vector<ll> sums(vector<ll> v) {
vector<ll> s = {0};
for (ll x : v) {
int m = s.size();
for (int i = 0; i < m; i++) s.push_back(s[i] + x);
}
return s;
}
ll brute(vector<ll> &a, ll S) {
int n = a.size();
ll ans = 0;
for (int mask = 0; mask < (1 << n); mask++) {
ll sum = 0;
for (int i = 0; i < n; i++) if (mask >> i & 1) sum += a[i];
ans += (sum == S);
}
return ans;
}
ll mitm(vector<ll> &a, ll S) {
int n = a.size();
vector<ll> A = sums(vector<ll>(a.begin(), a.begin() + n / 2));
vector<ll> Bs = sums(vector<ll>(a.begin() + n / 2, a.end()));
sort(Bs.begin(), Bs.end());
ll ans = 0;
for (ll x : A) {
auto [lo, hi] = equal_range(Bs.begin(), Bs.end(), S - x);
ans += hi - lo;
}
return ans;
}
int main() {
mt19937 rng(18);
for (int it = 1; it <= 1000; it++) {
int n = rng() % 12 + 1;
vector<ll> a(n);
for (auto &x : a) x = rng() % 10 + 1;
ll S = rng() % 30 + 1;
if (brute(a, S) != mitm(a, S)) {
cout << "DIFF on test " << it << "\n";
return 0;
}
}
cout << "OK: 1000 random tests agree\n";
return 0;
}
Real output: OK: 1000 random tests agree.
(Here 1 << n in an int is safe because n ≤ 12.)
Solutions in C++, Java and Python
C++: the full solution above.
Java (tested on the sample and the edge inputs: 2, 1, 0, 6, 20, 3; on n = 40 it printed 5779890186 in about 0.5 s). Java has no equal_range, so bound is a hand-written lower/upper bound:
import java.io.*;
import java.util.*;
public class Main {
static long[] sums(long[] v, int from, int to) {
long[] s = new long[1 << (to - from)];
int m = 1;
for (int k = from; k < to; k++) {
for (int i = 0; i < m; i++) s[m + i] = s[i] + v[k];
m *= 2;
}
return s;
}
// first index with b[idx] >= key (strict = false) or b[idx] > key (strict = true)
static int bound(long[] b, long key, boolean strict) {
int lo = 0, hi = b.length;
while (lo < hi) {
int mid = (lo + hi) >>> 1;
if (b[mid] < key || (strict && b[mid] == key)) lo = mid + 1;
else hi = mid;
}
return lo;
}
public static void main(String[] args) throws IOException {
StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
in.resetSyntax();
in.wordChars('0', '9');
in.wordChars('-', '-');
in.whitespaceChars(0, ' ');
in.nextToken(); int n = Integer.parseInt(in.sval);
in.nextToken(); long S = Long.parseLong(in.sval);
long[] a = new long[n];
for (int i = 0; i < n; i++) { in.nextToken(); a[i] = Long.parseLong(in.sval); }
long[] A = sums(a, 0, n / 2);
long[] B = sums(a, n / 2, n);
Arrays.sort(B);
long ans = 0;
for (long x : A) ans += bound(B, S - x, true) - bound(B, S - x, false);
System.out.println(ans);
}
}
Python (same outputs on the sample and edge inputs; bisect_left / bisect_right are Python's lower_bound / upper_bound). On n = 40 it printed 5779890186 using about 0.5 s of CPU time on our machine (about 1.9 s wall-clock while the machine was busy); with 2^20 sums per half Python is much slower than C++, so on a strict judge with n = 40 it may be close to the time limit:
import sys
from bisect import bisect_left, bisect_right
def sums(v):
s = [0]
for x in v:
s += [y + x for y in s]
return s
def main():
data = sys.stdin.read().split()
n, S = int(data[0]), int(data[1])
a = list(map(int, data[2:2 + n]))
A = sums(a[:n // 2])
B = sorted(sums(a[n // 2:]))
ans = 0
for x in A:
need = S - x
ans += bisect_right(B, need) - bisect_left(B, need)
print(ans)
main()
Brute force vs optimal
| Brute force (all masks) | Meet in the middle | |
|---|---|---|
| Time | O(2^n · n) | O(2^(n/2) · n): listing 2 · 2^(n/2) sums, sorting, 2^(n/2) binary searches of ~n/2 steps |
| Memory | O(n) | O(2^(n/2)): 2^20 long longs ≈ 8 MB per half |
| n = 20 | ≈ 2·10^7 steps: fine | ≈ 2·10^4 steps |
| n = 40 | ≈ 4.4·10^13 steps: TLE | ≈ 2·10^7 steps: about 0.2 s |
| Fits | n ≤ ~20 | n ≤ ~40 |
Meet in the middle trades memory for time: the brute force needs almost no memory, while meet in the middle stores two lists of a million sums.
Common mistakes (and the real outputs)
| Mistake | Input | What you see | Why | Fix |
|---|---|---|---|---|
if (binary_search(Bs.begin(), Bs.end(), S - x)) ans++; |
4 2 / 1 1 1 1 |
4 (expected 6) |
the right sum 1 appears twice, but binary_search only says yes/no, so equal sums are counted once |
equal_range, ans += hi - lo |
vector<int> sums(vector<int> v) (all sums in int) |
6 3000000000 / six × 1000000000 |
18 (expected 20) |
3·10^9 inside one half overflows int and wraps to a negative number, so the two sets that use all three of one half never match |
vector<ll> everywhere |
Forgetting sort(Bs.begin(), Bs.end()); |
6 9 / 9 1 8 2 7 3 |
2 (expected 3), no error |
binary search on unsorted data goes left or right at the wrong moments and misses matches | sort the right sums once |
Plain masks mask < (1 << n) with n = 40 |
n = 40 | TLE or wrong | 2^40 masks; 1 << 40 doesn't even fit in an int |
split into two halves |
The third bug is the nastiest: no crash, no warning, and the sample still prints 2. Only a test like the one above (or a stress test) catches it. The first two bugs also print the correct 2 on the sample, which is why the sample alone proves little.
The bug lines, exactly as in the video (everything else is the full solution):
// Bug 1: replaces the two equal_range lines
if (binary_search(Bs.begin(), Bs.end(), S - x)) ans++;
// Bug 2: int instead of ll
vector<int> sums(vector<int> v) {
vector<int> s = {0};
for (int x : v) {
...
vector<int> a(n);
...
vector<int> L(a.begin(), a.begin() + n / 2);
vector<int> R(a.begin() + n / 2, a.end());
vector<int> A = sums(L), Bs = sums(R);
...
for (int x : A) {
// Bug 3: the line sort(Bs.begin(), Bs.end()); is missing
vector<ll> A = sums(L), Bs = sums(R);
ll ans = 0;
Mini project
Build a subset-sum toolkit with one sums function and four query modes on the same two half-lists: count = S (equal_range), count ≤ S (upper_bound), the largest sum ≤ S, and XOR instead of +. Add a mask brute force and a random stress test that checks all four modes for n ≤ 12, then time each mode on n = 40.
Practice
-
Count subsets with sum ≤ S (n ≤ 40).
Answer
Same split. For each left sum <code>x</code>, the partners are right sums <code>≤ S − x</code>; in the sorted right list they are exactly the prefix before <code>upper_bound(Bs.begin(), Bs.end(), S - x)</code>, so add <code>upper_bound(...) - Bs.begin()</code>. For <code>a = 2 3 5 7</code>, <code>S = 10</code> the answer is <code>11</code> (sums 0, 2, 3, 5, 5, 7, 7, 8, 9, 10, 10). Verified against a mask brute force on 2000 random tests. -
Largest subset sum that is ≤ S (n ≤ 40).
Answer
For each left sum <code>x ≤ S</code>, the best partner is the largest right sum <code>≤ S − x</code>: the element just before <code>upper_bound(Bs.begin(), Bs.end(), S - x)</code> (it always exists, because 0 is a right sum). Take the maximum of <code>x + partner</code>. For <code>a = 2 3 5 7</code>: <code>S = 11</code> → <code>10</code>, <code>S = 1</code> → <code>0</code> (only the empty set). Verified against a brute force on 2000 random tests. -
Count subsets whose XOR is exactly K (n ≤ 40).
Answer
List the XORs of each half (<code>s.push_back(s[i] ^ x)</code>). If the left XOR is <code>x</code>, the right XOR must be <code>y</code> with <code>x ^ y = K</code>, i.e. <code>y = K ^ x</code> (XOR undoes itself). Sort the right list and count <code>K ^ x</code> with <code>equal_range</code>. For <code>a = 1 2 3 4</code>, <code>K = 4</code>: <code>2</code> ({4} and {1, 2, 3, 4}). Verified against a brute force on 2000 random tests. -
Largest (subset sum mod M) (n ≤ 35).
Answer
Take every sum mod M, so both lists hold values in <code>[0, M)</code>. For a left value <code>x</code>, <code>x + y</code> is either <code>< M</code> (no wrap) or in <code>[M, 2M)</code> (wraps to <code>x + y − M</code>). Best without wrap: the largest <code>y < M − x</code> (just before <code>lower_bound(..., M - x)</code>; 0 always qualifies). Best with wrap: the largest <code>y</code> overall, giving <code>(x + y) mod M</code>. Take the maximum. For <code>a = 3 5 8</code>, <code>M = 7</code>: <code>6</code>, from {5, 8}: 13 mod 7 = 6 (all three give 16 mod 7 = 2, which is worse). Verified against a brute force on 2000 random tests. -
With n = 40, how many sums does each half list, and why is the total far less than 2^40?
Answer
2^20 = 1,048,576 sums per half, about 2.1·10^6 in total. We never form all pairs; each left sum does one binary search (~20 steps) in the sorted right list, about 2·10^7 steps in all, versus 2^40 · 40 ≈ 4.4·10^13 for the masks.
Quick quiz
a = {1, 2, 3, 4}, S = 5. Left = {1, 2} (sums 0 1 2 3), right = {3, 4} (sums 0 3 4 7). How many subsets have sum exactly 5?
A) 1 · B) 2 · C) 3 · D) 4
Answer
B. Left 0 needs 5: no. Left 1 needs 4: yes ({1, 4}). Left 2 needs 3: yes ({2, 3}). Left 3 needs 2: no. The full solution prints 2 on 4 5 / 1 2 3 4.
Interview questions
- What is meet in the middle? Split an exponential search into two halves, enumerate each half separately (2^(n/2) each), and combine them with sorting plus binary search (or hashing) instead of trying every combination.
- Why is it much better than "half the work"? Work grows like 2^n, and 2^(n/2) is the square root of 2^n: for n = 40, 10^12 becomes 10^6.
- When does it apply? When the answer splits into two independent parts whose results combine by a simple rule (sum equals S, XOR equals K, sum ≤ S), and n is around 30–45.
- What is the cost? Memory: O(2^(n/2)) stored values (about 8 MB per half of
long longs for n = 40), plus O(2^(n/2) · n) time. binary_searchvslower_boundvsequal_range?binary_searchanswers yes/no;lower_boundgives the first element ≥ v;upper_boundthe first > v;equal_rangegives both, so their difference is the count of v. All need sorted data.- Could you use a hash map instead of sorting? Yes,
unordered_map<ll, int>counting right sums works for "exactly S" in expected O(2^(n/2)), but it cannot answer "≤ S" or "largest ≤ S", which need order.
Glossary
| Term | Meaning | Example |
|---|---|---|
| Subset | Any choice of items, each in or out; order doesn't matter | {3, 7} from {2, 3, 5, 7} |
| Empty subset | The choice with no items; its sum is 0 | {} |
| Subset sum | The total of the items in a subset | {2, 3, 5} → 10 |
Bitmask (mask) |
An integer whose bits mark which items are chosen | 6 = 0110 → items 1 and 2 |
1LL << n |
2^n as a 64-bit number | 1LL << 40 |
| Brute force | Try every possibility; slow but surely correct | all 2^n masks |
| Exponential complexity | Work like 2^n: each extra item doubles it | 2^40 ≈ 1.1·10^12 |
| TLE | Time Limit Exceeded: the program was too slow | masks on n = 40 |
| Meet in the middle | Solve two halves separately, then match their results | tunnel dug from both ends |
| Split | Cutting the input into a left half and a right half | L = first n/2 items, R = the rest |
| Independent choices | Picking on one side doesn't limit the other side | any left part + any right part |
| Half sums | Every subset sum of one half (2^(n/2) values) | {2, 3} → 0 2 3 5 |
Partner / S − x |
The right sum needed to complete a left sum x |
x = 3, S = 10 → 7 |
| Sorting | Putting values in increasing order | 7 0 12 5 → 0 5 7 12 |
| Binary search | Finding a value in sorted data by halving the range | dictionary lookup, ~20 steps for 10^6 |
binary_search |
C++: yes/no, is the value present? | true for 7 in 0 5 7 12 |
lower_bound |
First position with value ≥ v | v = 5 in 0 5 7 12 → index 1 |
upper_bound |
First position with value > v | v = 5 in 0 5 7 12 → index 2 |
equal_range |
The pair (lower_bound, upper_bound); hi − lo = how many times v appears |
0 1 1 2, v = 1 → 2 |
| Structured binding | C++17 auto [lo, hi] = … unpacks a pair |
auto [lo, hi] = equal_range(...) |
long long (ll) |
64-bit integer, up to about 9.2·10^18 | sums up to 4·10^10 |
| Integer overflow | A value too big for its type wraps around | 3·10^9 in an int becomes −1294967296 |
| Stress test | Compare a fast solution with a brute force on many random inputs | 1000 random arrays |
mt19937 |
C++ random number generator | mt19937 rng(18) |
| Undefined result | Output that depends on luck, not logic | equal_range on unsorted data |
| Memory–time trade-off | Storing more data to run faster | 2 × 8 MB of sums instead of 2^40 steps |
XOR (^) |
Bitwise "exclusive or"; x ^ x = 0 |
K ^ x in practice 3 |
Modulo (%) |
Remainder after division | 16 mod 7 = 2 |
Summary
- Problem R (Exact Budget): count subsets with sum exactly S, n ≤ 40.
- Masks are O(2^n · n): correct (
2on the sample) but TLE at n = 40; fine only up to n ≈ 20. - Split: every subset = a left part + a right part, chosen independently.
- List each half's 2^(n/2) sums (start from
{0}, each item doubles the list), sort the right ones, and for each left sumxcountS − xwithequal_range. - O(2^(n/2) · n) time, O(2^(n/2)) memory: n = 40 printed
5779890186in about 0.2 s; 1000 random tests agreed with the brute force. - Real bugs:
binary_searchcounts one copy (4, expected6);intsums overflow (18, expected20); nosortgives a silent wrong answer (2, expected3).
Next episode: Number theory 1: divisibility, GCD/LCM, the Euclidean algorithm.