Competitive Programming Essentials, Master Algorithms

Set up Sublime Text for competitive programming with a three-column layout—new.cpp, input.txt, and output.txt—to keep code, input, and output in one window.

Resolve the macOS clang missing bits/stdc++.h issue by creating a consolidated stdc++.h in a new bits folder from C/C++ headers and wiring it into the build.

Explain how online judges evaluate code and how IFNDEF and IFDEF manage code blocks for local versus online environments, using input.txt and output.txt.

Learn how to create and use sublime code snippets to insert whole code blocks with tab triggers, speeding up competitive programming tasks and saving time to think.

Learn how macros and short-hands speed up competitive programming by redefining int as long long, using ll, int32_t, F and S for pair fields, and pb for pushback.

Explore example code explained through debugging templates, code templates, and bulk input/output tricks for competitive programming, with emphasis on test cases and modular function design.

Analyze time and space complexity with Big O notation to compare algorithms. Learn how input size shapes growth patterns—linear, quadratic, constant, and exponential—and the difference between theoretical and experimental analyses.

Explore experimental analysis by measuring execution time with timestamps for sorting algorithms, comparing merge sort and bubble sort across input sizes to illustrate N^2 versus N log N growth.

Learn how to analyze algorithm time using big O notation, identify worst-case complexity, and map functions to O(1) through O(n^3), with examples like loops, bubble sort, and binary search.

Analyze how two nested for loops contribute to O(N^2) time by counting inner iterations and summing N + (N-1) + ... + 1.

Analyze a loop-based pattern where the outer loop increments by k, with k treated as a constant, and the inner loop runs up to k, yielding O(n) time.

Analyze bubble sort's time complexity by comparing best and worst cases, using a swapped flag to break early in sorted arrays, achieving O(n) best and O(n^2) worst.

An intuitive and mathematical analysis of binary search complexity, showing that the loop runs log2(n) times as the search space halves each iteration, yielding O(log n) time.

Analyze the time complexity of merge sort by forming a recurrence from dividing the array, sorting halves, and merging in linear time. Conclude that the overall complexity is O(n log n).

Learn to estimate if your solution passes an online judge by matching constraints and time limits with operation counts, and favor O(n log n) over O(n^2) to avoid TLE.

Explore how worst-case time complexities limit algorithm choices, from small-n N! and N^6 to larger-n N^4, N^3, N^2, and N log N, with examples like floydwarshall and traveling salesman dp.

Explore data structures and the c++ stl by revisiting containers, iterators, sequence and associative containers, unordered variants, container adapters, and common operations like insertion, search, and deletion.

Master both classical and STL arrays in C++, learn fixed-size storage, indexing, and initialization, and understand passing arrays to functions, base addresses, and size semantics.

Explore the c++ stl array container, its size and initialization, access, and passing by value versus by reference; learn aliases and operations like sort and fill with begin and end.

Master the vector STL, a dynamic array that doubles capacity as needed, offers constant-time random access, and supports push back, pop back, front, back, range and copy constructors.

Explore the deque, a dynamic double-ended queue that supports push and pop at both ends, size, and access via front, back, at, and brackets.

Explore the C++ standard template library stack (stl stack) for solving online coding challenges and interviews, and reuse common data structures using push, top, pop, and empty.

Learn to use the queue STL in C++, including the queue header, create a queue of integers, push numbers, and pop from the front to demonstrate FIFO behavior.

Utilize C++'s inbuilt priority queue (heap) via the queue header to push integers and pop them in descending order; convert to a min-heap with a comparator or a custom comparator.

Explore bit manipulation techniques using bitwise operators, including AND, OR, XOR, NOT, and left and right shifts, with examples showing bit-by-bit operations and 2's complement concepts.

Explore left shift multiplies a number by 2 raised to the power b, while right shift divides by 2 raised to the power b, illustrated with 5 and 10.

Explore determining odd or even numbers using bitwise operators by checking the last bit with x & 1, and review a quick code demo that prints odd or even.

Learn to get the ith bit of a number using bitwise operators, creating a mask by left shifting 1 by i and testing with and to reveal 1 or 0.

Learn to clear the ith bit by creating a mask with one left shift i, negating it, and applying a bitwise and to update n, illustrated with n=13 yielding 9.

Learn how to set the ith bit with a bitwise OR and a left-shifted mask, updating n in place and verifying with examples like five becoming seven.

Update ith bit by clearing the target bit, create a mask with value left shift i, and or it with n to set or clear the bit as required.

Learn to clear the last i bits of a number by creating a mask with the rightmost bits zero via left shifting minus one and applying it to the number.

Clear bits in a range i to j by building a two-part mask, A and B, then use bitwise and with the number to erase those bits.

This lecture explains how to insert m into n between positions j and i by clearing range, left-shifting m by i, and applying a bitwise or to produce the result.

Use the bitwise test n & (n-1) == 0 to confirm a number is a power of two; it works for 16, 8, 1024, but not for 5 or 12.

Count set bits in a number by iterating its binary representation with n & 1 and n >>= 1, incrementing the count when the last bit is one.

Count the number of set bits efficiently by repeatedly applying n = n & (n - 1), which removes the last set bit and increments the answer.

Convert a decimal number to binary using bitwise operators and right shifts to extract the last bit. Build the result with powers of ten and illustrate with 9 becoming 1001.

Learn to find the unique number among 2N+1 numbers using xor, compare brute force, hash maps, and bit masking, and achieve linear time with constant space.

Identify the unique number in an array by computing the cumulative XOR of all elements in a vector and returning the result in C++.

Identify the two numbers that appear once among 2n+2 values using XOR to cancel duplicates, then split by a set bit to isolate both in O(n) time and O(1) space.

Compute xor of all numbers to obtain the xor of the two unique numbers, then partition by a set bit mask and xor each group to reveal them.

Solve unique number problem where numbers appear three times except one, using a per-bit sum modulo 3 to cancel repeats and reveal value; extend to 5n+1, 7n+1, or 4n+1.

Implement the unique number three problem by counting set bits across 32 positions, taking modulo 3 to isolate the unique number, then reconstruct the integer from the bit sums.

Explore computing all subsequences of a string using a bit masking approach, iterating from 0 to 2^N-1, and selecting characters by binary masks to generate and sort subsequences.

Learn to generate all subsets of a string by enumerating 0 to 2^N-1 with bit masking, printing characters corresponding to set bits for each subset.

Analyze the traveling salesman problem to design a minimum cost Hamiltonian cycle that visits all locations and returns to the start, highlighting NP-hardness and brute-force and DP approaches.

Learn how dynamic programming solves the traveling salesman problem by reusing optimal subtours and tracking the visited cities set and the last city with bit masking.

Demonstrates a dp based traveling salesman solution using recursion and bitmasking, with a 2d distance matrix, bitwise visited set, and a base case.

Explore a dp-based travelling salesman solution using bitmask states (2^N x N), top-down memoization, and a dp array to compute and cache the shortest distance.

Explore the concept of big integers and how Java, C++, and Python handle them, including digit-by-digit storage with arrays or strings and basic operations.

Learn to add two large numbers beyond standard int limits by treating them as strings, using reversal and carry-aware digit-by-digit addition. Swap so the larger number is second for handling.

Learn how to implement big integer addition in code by reading large numbers as strings, reversing digits, and performing digit-wise addition with carry to produce a correct string result.

Explore array-based multiplication to compute large factorials, storing digits in an array, reversing as needed, and iteratively multiplying by each i from 1 to n.

Compute big factorials by multiplying an array or vector of digits, updating size and carry, and printing the result in reverse order to obtain the full factorial.

Explore how Python automatically handles big integers, using an efficient internal base 32 representation, allowing seamless multiplication, exponentiation, and factorial calculations without extra work.

Compute X as (N - K) divided by 2 and Y as X plus K from N and K, solving the Julka big integer challenge with Java BigInteger arithmetic.

Read multiple test cases, use big integers to compute X = (N - K)/2 and Y = X + K, then print the larger value first.

Master the concept of binary exponentiation to compute a^b efficiently by using last set bit checks, squaring, and bit shifting, achieving O(log b) time.

Master modular binary exponentiation under a prime modulus, such as 10^9+7, by updating the result with multiplication and squaring the base while applying mod to prevent overflow.

Master fast multiplication for competitive programming by using binary exponentiation style techniques with bit manipulation to compute A*B mod C for A, B up to 1e15 in C++.

learn matrix exponentiation to solve dynamic programming problems and linear recurrence relations, using Fibonacci as an example; apply matrix and binary exponentiation to compute F_n efficiently.

Code matrix exponentiation to compute Fibonacci numbers with a 2x2 matrix and mod 1e9+7, using power n-2 and the identity matrix, and explain complexity of size cubed times log n.

Explore efficient methods to compute the sum of Fibonacci numbers from f(n) to f(m) using matrix exponentiation and a prefix-sum approach, and derive the Fibonacci property.

adopts a second approach to fibosum by leveraging fibonacci properties and matrix multiplication, deriving F(n+1) from F(n) and F(n-1), and illustrating with a base case example.

Learn the pigeonhole principle and its use in competitive programming, demonstrated with five pigeons and four holes, plus a hair-counting example to show overlaps.

Learn to solve the divisible subset problem from a multiset by finding a nonempty subset whose sum is divisible by N, using brute force limits, subarrays, and pigeonhole concepts.

Apply the pigeonhole principle to show a subarray with sum divisible by N exists, using cumulative sums mod N and a linear-time frequency array to find it efficiently.

Learn how to decide four numbers with xor zero when consecutive 64-bit integers differ by one bit, using a 130 threshold and N^3 brute force for smaller sets.

Solve the holiday problem on trees by summing, for each edge, twice the edge weight times the smaller partition size, using a single DFS to compute subtree sizes.

Build a weighted undirected graph with an adjacency list for the holiday accommodation problem, use DFS to compute subtree sizes, and accumulate 2 * min(subtree_size, N - subtree_size) * weight.

Explore mathematical expectation as a weighted average of a random variable, using discrete and continuous examples, and learn how to compute E(X) with sums or integrals.

Apply linearity of expectation to compute the expected sum of two random variables by adding their individual expectations, even when dependent or independent, as illustrated with two dice.

Apply the rule of linearity of expectation to a fair coin flipped N times, deriving that the expected number of heads is N/2.

Compute the expected number of coin flips to get a head using a recursive approach, deriving x = 1/2 + 1/2(1 + x) and arriving at x = 2.

Master the expected number of coin flips to achieve two consecutive heads, solving the equation to find it equals six throws.

Derive the expected number of coin flips to get n consecutive heads using a generalized analysis and a geometric progression, yielding x = 2^{n+1} - 2.

Explore Bernoulli's trial, a two-outcome experiment, with examples like coin flips and prime checks. Learn the key results: expected trials 1/p and expected successes np in n trials.

Analyze a Bernoulli trial application per theorem two, where n students choose numbers from 1 to 100, showing the expected number selecting a single digit is n times 9/100.

Explore how Bernoulli's trial applies to interviewing, where a 0.16 success rate yields an expected 6.25 interviews (rounded up to seven) using the geometric approach.

Explore the coupon collector problem to compute the expected packets needed to collect all N coupons using linearity of expectation, yielding the harmonic series 1 plus 1/2 plus 1/N.