Competitive Programming Tutorial #18 | Split the Search in Half: 2^40 Becomes 2·2^20

Competitive Programming Tutorial: Episode 18 of SyntaxPilot's free Competitive Programming full course, with real-life examples for every concept. Split the Search in Half: 2^40 Becomes 2·2^20. In this video you'll learn: • Original Problem R (Exact Budget): count subsets with sum exactly S • Brute force over 2^n masks and its real TLE at n = 40 • The split: every subset is a left part plus a right part • List both halves' sums, sort one, count matches with equal_range • Hand trace on the sample, then n = 40 live • Stress test against the brute force • Complexity: O(2^(n/2) · n) against the constraints • Three real bugs: binary_search, int overflow, forgetting to sort Every concept starts with a real-life example, then an animation and notes, then live code in the SyntaxPilot online compiler. Practice free in the SyntaxPilot compiler (nothing to install): https://syntaxpilot-learning-2026.web... Detailed notes for this episode (code, outputs, practice): https://syntaxpilot-learning-2026.web... Chapters 00:00 Welcome 00:21 Today's agenda 00:38 Problem R: Exact Budget 01:44 Brute force: TLE at n = 40 02:26 The tunnel from both ends 02:46 Split into two halves 03:55 Match with a lookup 04:55 n = 40, live 06:09 Stress test 06:27 Complexity vs the constraints 06:56 Common mistakes 08:24 What you invented 08:46 Quick quiz 09:11 Recap and homework 09:50 Next episode Next episode: Number theory 1: divisibility, GCD/LCM, the Euclidean algorithm Post your homework and quiz answer in the comments, and subscribe for the full basic-to-master playlist, free. #Competitive Programming #CompetitiveProgrammingTutorial #SyntaxPilot