Revision

Flashcards from every finished chapter, then each chapter’s cheat sheet. Ideal the night before a contest.Har finished chapter ke flashcards, phir har chapter ki cheat sheet. Contest se pehle wali raat ke liye perfect.

All flashcards (33)Saare flashcards (33)

33 left

1. Introduction

Template

FastReader (BufferedReader + StringTokenizer) for input, PrintWriter for output, out.flush() at the end. Rename the class to Main.

Input ke liye FastReader (BufferedReader + StringTokenizer), output ke liye PrintWriter, end mein out.flush(). Class ka naam Main karo.

int vs long

int ≈ ±2.1·10⁹, long ≈ ±9.2·10¹⁸. Widen before multiplying: (long) a * b. Math.multiplyExact catches overflow.

int ≈ ±2.1·10⁹, long ≈ ±9.2·10¹⁸. Multiply se pehle widen karo: (long) a * b. Math.multiplyExact overflow pakadta hai.

Modulo

Reduce after every + − ×. -7 % 3 == -1 in Java, so use Math.floorMod. The product of two values below 10⁹+7 needs a long.

Har + − × ke baad reduce karo. Java mein -7 % 3 == -1, toh Math.floorMod. 10⁹+7 se chhoti do values ka product long mein.

Doubles

Compare with Math.abs(a - b) < 1e-9. Print with String.format(Locale.US, "%.9f", x). Integers are exact only up to 2⁵³.

Math.abs(a - b) < 1e-9 se compare karo. String.format(Locale.US, "%.9f", x) se print karo. Integers sirf 2⁵³ tak exact.

Formulas

Σx = n(n+1)/2, Σx² = n(n+1)(2n+1)/6, geometric (bk − a)/(k − 1), harmonic ≤ log₂ n + 1.

Floor / ceil

Java / truncates toward 0, so use Math.floorDiv for negatives. ⌈a/b⌉ = (a + b - 1) / b for positive numbers.

Java / zero ki taraf truncate karta hai — negatives ke liye Math.floorDiv. Positive ke liye ⌈a/b⌉ = (a + b - 1) / b.

2. Time complexity

Rules

k nested loops → O(nᵏ). Drop constants. Phases → the slowest phase wins. Recursion → calls × cost per call.

k nested loops → O(nᵏ). Constants hatao. Phases → sabse slow jeet-ta hai. Recursion → calls × har call ka cost.

Limits → complexity

n ≤ 10: n!; ≤ 20: 2ⁿ; ≤ 500: n³; ≤ 5000: n²; ≤ 10⁶: n log n or n; bigger: log n or 1.

n ≤ 10: n!; ≤ 20: 2ⁿ; ≤ 500: n³; ≤ 5000: n²; ≤ 10⁶: n log n ya n; usse bada: log n ya 1.

10⁸ per second

Plug n into the complexity. Up to ~10⁸ operations is comfortable; 10⁹ is risky in Java.

Complexity mein n daalo. ~10⁸ operations tak aaram; Java mein 10⁹ risky.

Kadane

sum = max(a[k], sum + a[k]); best = max(best, sum); gives O(n). For a non-empty subarray, start best at a[0].

sum = max(a[k], sum + a[k]); best = max(best, sum); — O(n). Non-empty ke liye best a[0] se.

3. Sorting

Sort bounds

Neighbour swaps → O(n²) (inversions). Comparison sorts ≥ n log n. Counting sort O(n + c) for small values.

Padosi swaps → O(n²) (inversions). Comparison sorts ≥ n log n. Chhoti values pe counting sort O(n + c).

Java sorting

Arrays.sort(int[]): shuffle first. Objects: TimSort, stable, O(n log n). Pairs: int[][] + comparator.

Arrays.sort(int[]): pehle shuffle. Objects: TimSort, stable, O(n log n). Pairs: int[][] + comparator.

Comparators

Comparator.comparingInt(f).thenComparing(g); Integer.compare(a, b), never a - b.

Comparator.comparingInt(f).thenComparing(g); Integer.compare(a, b), kabhi a - b nahi.

Bounds

lowerBound = first ≥ x, upperBound = first > x; count = ub − lb. Arrays.binarySearch returns any match or -(ins) - 1.

lowerBound = pehla ≥ x, upperBound = pehla > x; count = ub − lb. Arrays.binarySearch koi bhi match ya -(ins) - 1.

On the answer

Monotone ok(x): jump with b = z, z/2, …, 1 while !ok(x + b). The answer is x + 1.

Monotone ok(x): b = z, z/2, …, 1 se jump jab tak !ok(x + b). Answer x + 1.

4. Data structures

STL → Java

vector→ArrayList, set→TreeSet, unordered_set→HashSet, map→TreeMap, unordered_map→HashMap, deque/stack/queue→ArrayDeque, priority_queue→PriorityQueue (min!), bitset→BitSet.

Navigation

ceiling (≥ x), higher (> x), floor (≤ x), lower (< x), first, last. All O(log n), returning null when nothing matches.

ceiling (≥ x), higher (> x), floor (≤ x), lower (< x), first, last — sab O(log n), kuch na mile toh null.

Multiset

TreeMap<Integer,Integer>: merge(x, 1, Integer::sum); remove one copy by decrementing, and drop the key at 0.

TreeMap<Integer,Integer>: merge(x, 1, Integer::sum); ek copy hatane ke liye ghatao, 0 pe key hatao.

Traps

remove(int) removes by index; get returns null; PriorityQueue is a min-heap; headSet(x).size() is O(n); boxing is slow.

remove(int) index se hatata hai; get null deta hai; PriorityQueue min-heap; headSet(x).size() O(n); boxing slow.

Prefer sorting

If one sort + a linear scan solves it, that usually beats a set or map with the same O(n log n).

Agar ek sort + linear scan se kaam ho jaaye, toh woh aksar same O(n log n) wale set/map se tez hai.

5. Complete search

Subsets

Recursion: skip k, take k, undo. Bits: for (b = 0; b < 1 << n; b++), and element i is in when (b & (1 << i)) != 0. Both are O(2ⁿ · n).

Recursion: k chhodo, k lo, undo. Bits: for (b = 0; b < 1 << n; b++), element i andar jab (b & (1 << i)) != 0. Dono O(2ⁿ · n).

Permutations

Recursion with chosen[], or nextPermutation: non-increasing suffix → swap → reverse. n ≤ 10 is fine.

chosen[] ke saath recursion, ya nextPermutation: non-increasing suffix → swap → reverse. n ≤ 10 theek.

Backtracking

Extend, recurse, undo. Make the "is this allowed?" check O(1) with helper arrays (queens: column, x+y, x−y+n−1).

Badhao, recurse, undo. "Allowed hai?" check helper arrays se O(1) (queens: column, x+y, x−y+n−1).

Pruning

Stop as soon as a partial solution can’t finish. Early cuts beat late cuts. Use symmetry to halve work.

Jaise hi partial solution poora na ho sake, ruko. Jaldi ke cuts der ke cuts se behtar. Symmetry se kaam aadha.

Meet in the middle

Split in two, enumerate each half (2^(n/2)), sort, combine with two pointers. Use it for n ≈ 40 subset problems.

Do mein todo, har half enumerate (2^(n/2)), sort, two pointers se jodo. n ≈ 40 wale subset problems ke liye.

9. Range queries

Prefix sums

p[k] = p[k−1] + a[k], sumq(a,b) = p[b] − p[a−1]. Build O(n), query O(1), no updates. Use long[].

p[k] = p[k−1] + a[k], sumq(a,b) = p[b] − p[a−1]. Build O(n), query O(1), updates nahi. long[] lo.

2D prefix sums

s[i][j] = g + s[i−1][j] + s[i][j−1] − s[i−1][j−1]; rectangle = S(A) − S(B) − S(C) + S(D). Pad with a zero row and column.

s[i][j] = g + s[i−1][j] + s[i][j−1] − s[i−1][j−1]; rectangle = S(A) − S(B) − S(C) + S(D). Zero row/column ka padding rakho.

Sparse table

mn[j][i] = min(mn[j−1][i], mn[j−1][i + 2^(j−1)]). Query: j = 31 − Integer.numberOfLeadingZeros(len), then two overlapping blocks. Only for min/max/gcd.

mn[j][i] = min(mn[j−1][i], mn[j−1][i + 2^(j−1)]). Query: j = 31 − Integer.numberOfLeadingZeros(len), phir do overlapping blocks. Sirf min/max/gcd ke liye.

Fenwick tree

1-indexed. tree[k] = sum of the k & -k values ending at k. sum: k -= k & -k; add: k += k & -k. Both O(log n).

1-indexed. tree[k] = k pe khatam hone wale k & -k values ka sum. sum: k -= k & -k; add: k += k & -k. Dono O(log n).

Segment tree (bottom-up)

Leaves at tree[n..2n−1], children 2k, 2k+1, parent k/2. Query: take odd a, even b, climb. Update: recompute the path to the root.

Leaves tree[n..2n−1] pe, children 2k, 2k+1, parent k/2. Query: odd a, even b lo, upar chado. Update: root tak ka path recompute.

Other operations

Any associative combine: min, max, gcd, xor, and, or. Identity: 0 for sum, Long.MAX_VALUE for min, Long.MIN_VALUE for max.

Koi bhi associative combine: min, max, gcd, xor, and, or. Identity: sum ke liye 0, min ke liye Long.MAX_VALUE, max ke liye Long.MIN_VALUE.

Index compression

Sort and dedupe, then Arrays.binarySearch(sorted, x) + 1. Keeps order. Offline only: collect all values first.

Sort + dedupe, phir Arrays.binarySearch(sorted, x) + 1. Order same rehta hai. Sirf offline: pehle saari values collect karo.

Difference array

Range add: d[a] += x; d[b+1] −= x. A value is a prefix sum of d. With a Fenwick tree, range add + point query in O(log n).

Range add: d[a] += x; d[b+1] −= x. Value = d ka prefix sum. Fenwick ke saath range add + point query O(log n).

Which one?

Static sum: prefix sums. Static min: sparse table. Updates + sum: Fenwick. Updates + anything else: segment tree.

Static sum → prefix sums. Static min → sparse table. Updates + sum → Fenwick. Updates + kuch aur → segment tree.