Documentation Index Fetch the complete documentation index at: https://resources.devweekends.com/llms.txt
Use this file to discover all available pages before exploring further.
Quick Reference Card
Time Complexity Limits
Constraint Max Complexity Example Algorithm n ≤ 10 O(n!) Brute force permutations n ≤ 20 O(2^n × n) Bitmask DP n ≤ 100 O(n³) Floyd-Warshall n ≤ 500 O(n³) Matrix chain DP n ≤ 3,000 O(n²) 2D DP, all pairs n ≤ 10⁵ O(n log n) Sorting, segment tree n ≤ 10⁶ O(n) Linear algorithms n ≤ 10⁸ O(n) careful Very simple O(n) n ≤ 10⁹ O(√n) or O(log n) Binary search, math n ≤ 10¹⁸ O(log n) Binary exponentiation
Common Constants
const int MOD = 1 e 9 + 7 ;
const int MOD2 = 998244353 ;
const long long INF = 1 e 18 ;
const int IINF = 1 e 9 ;
const double EPS = 1 e- 9 ;
const double PI = acos ( - 1.0 );
STL Complexity Reference
vector
Operation Complexity push_backO(1) amortized pop_backO(1) Access [i] O(1) insert at positionO(n) erase at positionO(n) sizeO(1)
set / map
Operation Complexity insertO(log n) findO(log n) eraseO(log n) lower_boundO(log n) begin / rbeginO(1)
unordered_set / unordered_map
Operation Complexity insertO(1) avg, O(n) worst findO(1) avg, O(n) worst eraseO(1) avg
priority_queue
Operation Complexity pushO(log n) popO(log n) topO(1)
Binary Search Templates
Lower Bound (First ≥ target)
int lo = 0 , hi = n;
while (lo < hi) {
int mid = lo + (hi - lo) / 2 ;
if ( arr [mid] >= target) hi = mid;
else lo = mid + 1 ;
}
// lo is the answer
Upper Bound (First > target)
int lo = 0 , hi = n;
while (lo < hi) {
int mid = lo + (hi - lo) / 2 ;
if ( arr [mid] > target) hi = mid;
else lo = mid + 1 ;
}
Binary Search on Answer
int lo = MIN_ANS, hi = MAX_ANS;
while (lo < hi) {
int mid = lo + (hi - lo) / 2 ;
if ( isPossible (mid)) hi = mid; // Minimize answer
else lo = mid + 1 ;
}
Graph Templates
DFS
vector < bool > vis ( n + 1 );
function < void ( int ) > dfs = [ & ]( int u ) {
vis [u] = true ;
for ( int v : adj [u]) {
if ( ! vis [v]) dfs (v);
}
};
BFS
vector < int > dist ( n + 1 , - 1 );
queue < int > q;
q . push (start);
dist [start] = 0 ;
while ( ! q . empty ()) {
int u = q . front (); q . pop ();
for ( int v : adj [u]) {
if ( dist [v] == - 1 ) {
dist [v] = dist [u] + 1 ;
q . push (v);
}
}
}
Dijkstra
vector < ll > dist ( n + 1 , INF );
priority_queue < pair < ll, int > , vector < pair < ll, int >> , greater <>> pq;
dist [start] = 0 ;
pq . push ({ 0 , start});
while ( ! pq . empty ()) {
auto [d, u] = pq . top (); pq . pop ();
if (d > dist [u]) continue ;
for ( auto [v, w] : adj [u]) {
if ( dist [u] + w < dist [v]) {
dist [v] = dist [u] + w;
pq . push ({ dist [v], v});
}
}
}
GCD / LCM
ll gcd ( ll a , ll b ) { return b ? gcd (b, a % b) : a; }
ll lcm ( ll a , ll b ) { return a / gcd (a, b) * b; } // Prevent overflow
Modular Exponentiation
ll power ( ll base , ll exp , ll mod ) {
ll res = 1 ;
base %= mod;
while (exp > 0 ) {
if (exp & 1 ) res = res * base % mod;
base = base * base % mod;
exp >>= 1 ;
}
return res;
}
Modular Inverse (p prime)
ll modinv ( ll a , ll p ) { return power (a, p - 2 , p); }
Combinations (nCr)
ll C ( int n , int r ) {
if (r > n || r < 0 ) return 0 ;
return fact [n] * inv_fact [r] % MOD * inv_fact [n - r] % MOD;
}
Check Prime
bool isPrime ( ll n ) {
if (n < 2 ) return false ;
if (n == 2 ) return true ;
if (n % 2 == 0 ) return false ;
for (ll i = 3 ; i * i <= n; i += 2 )
if (n % i == 0 ) return false ;
return true ;
}
Bit Manipulation
// Check if i-th bit is set (0-indexed)
(n >> i) & 1
// Set i-th bit
n | ( 1 LL << i)
// Clear i-th bit
n & ~ ( 1 LL << i)
// Toggle i-th bit
n ^ ( 1 LL << i)
// Get lowest set bit
n & ( - n)
// Clear lowest set bit
n & (n - 1 )
// Count set bits
__builtin_popcount (n) // int
__builtin_popcountll (n) // long long
// Check power of 2
n && ! (n & (n - 1 ))
// Iterate all subsets of mask
for ( int sub = mask; sub > 0 ; sub = (sub - 1 ) & mask) { }
String Patterns
String to Int/LL
int x = stoi (s);
ll x = stoll (s);
Int to String
Split by Delimiter
stringstream ss ( s );
string token;
while ( getline (ss, token, ',' )) {
// process token
}
Check Palindrome
string t = s;
reverse ( t . begin (), t . end ());
bool isPalin = (s == t);
Direction Arrays
// 4 directions (up, down, left, right)
int dx[] = { - 1 , 1 , 0 , 0 };
int dy[] = { 0 , 0 , - 1 , 1 };
// 8 directions
int dx[] = { - 1 , - 1 , - 1 , 0 , 0 , 1 , 1 , 1 };
int dy[] = { - 1 , 0 , 1 , - 1 , 1 , - 1 , 0 , 1 };
// Usage
for ( int d = 0 ; d < 4 ; d ++ ) {
int nx = x + dx [d], ny = y + dy [d];
if (nx >= 0 && nx < n && ny >= 0 && ny < m) {
// valid cell
}
}
Common Patterns
Coordinate Compression
vector < int > vals = arr;
sort ( vals . begin (), vals . end ());
vals . erase ( unique ( vals . begin (), vals . end ()), vals . end ());
for ( int & x : arr) {
x = lower_bound ( vals . begin (), vals . end (), x) - vals . begin ();
}
Prefix Sum
vector < ll > pre ( n + 1 );
for ( int i = 0 ; i < n; i ++ ) pre [i + 1 ] = pre [i] + a [i];
// Sum [l, r] = pre[r + 1] - pre[l]
Two Pointers
int l = 0 , r = 0 ;
while (r < n) {
// Expand: add arr[r]
while ( /* condition broken */ ) {
// Contract: remove arr[l]
l ++ ;
}
// Update answer
r ++ ;
}
// YES/NO
cout << (ans ? "YES" : "NO" ) << ' \n ' ;
// Fixed precision
cout << fixed << setprecision ( 9 ) << x << ' \n ' ;
// Vector with spaces
for ( int i = 0 ; i < n; i ++ ) cout << a [i] << " \n " [i == n - 1 ];
// Multiple values
for ( int x : v) cout << x << ' ' ;
cout << ' \n ' ;
Contest Checklist
Back to Overview Return to the course curriculum.