Cheat Sheet 695k5c

d (n, INF); d[v] = 0; // It can be any source vertex vector p (n, -1); // parents int x; for (int i=0; i d[e[j].a] + e[j].cost) { // Relaxation condition d[e[j].b] = max (-INF, d[e[j].a] + e[j].cost); p[e[j].b] = e[j].a; x = e[j].b; } } if (x == -1) cout << "No negative cycle from " << v; else { int y = x; for (int i=0; i path; for (int cur=y; ; cur=p[cur]) { path.push_back (cur); if (cur == y && path.size() > 1) break; } reverse (path.begin(), path.end()); cout << "Negative cycle: "; for (size_t i=0; i<path.size(); ++i) cout << path[i] << ' '; } } Edmon Karp Max Flow const int MAXN = 5e3 + 50 ; // vector > > G ( MAXN ) ; // This is used to store the Edges of the Graph and capacity of the edges . Int E[ MAXN ][ MAXN ] ; Int C[ MAXN ][ MAXN ] ; Int F[ MAXN ][ MAXN ] ; Int N , Edges ; Int Edmond_Karp( Int s , Int t ) { while( true ) { bool Flg = false ; // Flag to see if We have found A path to the destination. vector Parent( N , -1 ) ; // Storing parents used for backtracking. Parent[ s ] = s ; // Initialisation.

vector M( N ) ; // Capacity of the path to the node M[s] = 1e15 ; // Initialisation queue Q ; // Queue to Run a BFS Q.push( s ) ; while( !Q.empty() ) { Int u = Q.front() ; Q.pop() ; for( Int v = 0 ; v < N ; v ++ ) { if( !E[u][v] )continue ; // If this edge doesn't exists the continue. // There is available capacity and the node is not seen before essential condition for sp via bfs. if( C[u][v] - F[u][v] > 0 and Parent[v] == -1 ) { Parent[v] = u ; M[ v ] = min( M[u] , C[u][v] - F[u][v] ) ; // C[u][v] - F[u][v] maximum Flow we can send through this Edge . if( v!= t )Q.push(v) ; // If its not the destination , then push it into the queue. else { while( Parent[v] != v ) { // Backtrack and update the values. u = Parent[v] ; F[u][v] += M[t] ; F[v][u] -= M[t] ; v=u; } Flg = true ; // Found the path therefore break break ; } } } if( Flg )break ; // Found the path therfore break } if( !Flg ) {// Path Not Found Time to Exit. Int sum = 0 ; for( Int i = 0 ; i < N ; i ++ ) sum = sum + F[s][i] ; return sum ; } } } int main ( ) { scanf("%lld%lld",&N,&Edges) ; // v is the number of vertices and e is number of edges . FOR( i , Edges ) { Int u , v ,c ; scanf("%lld%lld%lld",&u,&v,&c) ; u-- ; v-- ; if( v!= u ) { E[u][v] = 1 ; // IF graph is undirected. E[v][u] = 1 ; C[u][v] += c ;

C[v][u] += c ; } } Int s , t ; s = 0; t = N-1; cout<<Edmond_Karp( s, t ) ; } Hierholzer Euler Tour int cnt[ N ] ; bool mark[ N*N ]; vector > > g( N ); void Euler_path(int u, int par){ vis[u] = 1; while(cnt[u] < (int)g[u].size()){ cnt[u]++; if (mark[g[u][cnt[u]-1].S]) continue; else mark[g[u][cnt[u]-1].S] = 1, Euler_path(g[u][cnt[u]-1].F, u); } ans.pb(u); // stores euler path in reverse order } Extended Euclid Writing the code for extended euclidean algorithm , can be used to find mod inverse when a and MOD are coprime that is gcd = 1, x = inverse extend_euclid ( ) { int x = 1 ; int xlast = 0 ; int y = 0 ; int ylast = 1 ; while ( a ) { q = b/a ; r = b%a ; m = xlast - q*x ; n = ylast - q*y ; x=m; y=n; a=r; b=a; } } Hoprcroft Maximum Bipartite Matching const int MAXN = 1e5 ; int N , M ; // N = Number of Nodes on the Left side and M = Number of Edges in the bipartite graph vector g [ MAXN ] ; // Declaration of our bipartite graph

int Distance[ MAXN ] ; // This will store the Length of augmenting path we have made till this node int matched[ MAXN ] ; // matched[u] = v , if there is an edge between u and v in final matched graph. const int INF = 1e9 ; bool bfs( ) { queue q ; for( int i = 1 ; i <= N ; i ++ ) if( matched[i] == 0 ) { q.push(i) ; Distance[i] = 0 ; } else Distance[i] = INF ; Distance[0] = INF ; while( !q.empty() ) { int Left = q.front( ); q.pop() ; for( int Right : g[Left] ) { if( Distance[ matched[Right] ] == INF ) { Distance[ matched[Right] ] = Distance[Left] + 1 ; q.push( matched[Right] ) ; } } } return ( Distance[ 0 ] != INF ) ; } bool dfs( int Left ) { if( Left == 0 )return true ; for( int Right : g[Left] ) { if( Distance[matched[Right]] == Distance[Left] + 1 ) if( dfs( matched[Right] ) ) { matched[Left] = Right ; matched[Right] = Left ; return true ; } } Distance[ Left ] = INF ; return false ; } void Hopcroft( ) { int matching = 0 ; while( bfs( ) ) { for( int i = 1 ; i <= N ; i ++ ) if( matched[i] == 0 and dfs( i ) ) matching++ ; } cout<<matching<<endl; } int main( ) { int B ; scanf("%d%d%d",&N,&B,&M) ;

FOR( i , M ) { int u , v ; scanf("%d%d",&u,&v) ; v= v+N ; g[u].pb( v ) ; g[v].pb( u ) ; } Hopcroft( ) ; } KMP String Matching std::vector Build( string s ) { int n = s.length(); vector pref(n); pref[0] = 0 ; for ( int i = 1 ; i < n ; i ++ ) { int j = pref[i-1]; while ( j > 0 && !(s[i] == s[j])) j = pref[j-1]; if( s[i] == s[j]) ++j ; pref[i] = j ; } return pref ; } Int KMP ( string text , string pat) { int n = text.length(); int m = pat.length(); if ( m > n ) return 0 ; // Corner Case Int ans = 0 ; if (m == 1) { // if m == 1 brute force for (int i = 0; i < n; i++) if( pat[0] == text[i] ) ans ++; return ans; } if (m == 2) { // brute force again for (int i = 0; i < n - 1; i++) if (pat[0] == text[i] && pat[1] == text[i + 1]) ans++; return ans; } vector Prefix = Build( pat ); int q = 0 ; // number of characters matched for ( int i = 0 ; i < n ; i ++ ) { while( q > 0 && pat[q] != text[i] ) // If next character does not matches { q = Prefix[q] ; } if( pat[q] == text[i] ) q=q+1;

if( q == m ) { ans += 1 ; q = Prefix[q-1] ; } } return ans ; } int main ( ) { string text , pat ; cout<<"Enter the text " << endl ; cin >> text ; cout<<"Enter the pattern" << endl ; cin >> pat ; cout<<" Number of occurance of pattern in string " << endl ; cout< >g(0) ; void PreProcess() { int i, j; for (i = 0; i < N; i++) for (j = 0; 1 << j < N; j++) P[i][j] = -1; //the first ancestor of every node i is T[i] for (i = 0; i < N; i++) P[i][0] = T[i]; //bottom up dynamic programing for (j = 1; 1 << j < N; j++) for (i = 0; i < N; i++) if (P[i][j - 1] != -1) P[i][j] = P[P[i][j - 1]][j - 1]; // 2^(j-1) * 2^(j-1) = 2^j } void bfs ( ) { queue q; while( !q.empty()) q.pop(); q.push( 0 ) ; L[0] = 0 ; while ( !q.empty() ) { int v = q.front() ; q.pop() ; for( int i = 0 ; i < g[v].size() ; i ++ ) { int ch = g[v][i] ;

L[ch] = L[v] + 1 ; cout<< "Ch" << ch << endl; q.push(ch); } } return ; } int query(int p, int q) { int tmp, log, i; if (L[p] < L[q]) swap( p , q ) ; for (log = 1; 1 << log <= L[p]; log++); log--; for (i = log; i >= 0; i--) if (L[p] - (1 << i) >= L[q]) p = P[p][i]; if (p == q) return p; for (i = log; i >= 0; i--) if (P[p][i] != -1 && P[p][i] != P[q][i]) p = P[p][i], q = P[q][i]; return T[p]; } int main ( ) { for( int i = 1 ; i < N ; i ++ ) { g[ T[i] ].push_back( i ) ; } bfs( ) ; PreProcess(); cout<< query ( 7 , 8 ) << endl ; } Manacher Longest Palindromic Substring string preProcess(string s) { int n = s.length(); if (n == 0) return "^$"; string ret = "^"; for (int i = 0; i < n; i++) ret += "#" + s.substr(i, 1); ret += "#$"; return ret; } string longestPalindrome(string s) { string T = preProcess(s); int n = T.length(); int *P = new int[n]; int C = 0, R = 0;

for (int i = 1; i < n-1; i++) { int i_mirror = 2*C-i; // equals to i' = C - (i-C) P[i] = (R > i) ? min(R-i, P[i_mirror]) : 0; while (T[i + 1 + P[i]] == T[i - 1 - P[i]]) P[i]++; if (i + P[i] > R) { C = i; R = i + P[i]; } } int maxLen = 0; int centerIndex = 0; for (int i = 1; i < n-1; i++) { if (P[i] > maxLen) { maxLen = P[i]; centerIndex = i; } } delete[] P; return s.substr((centerIndex - 1 - maxLen)/2, maxLen); } Sparse Table void process2(int M[MAXN][LOGMAXN], int A[MAXN], int N) { int i, j; for (i = 0; i < N; i++) M[i][0] = i; for (j = 1; 1 << j <= N; j++) for (i = 0; i + (1 << j) - 1 < N; i++) if (A[M[i][j - 1]] < A[M[i + (1 << (j - 1))][j - 1]]) M[i][j] = M[i][j - 1]; else M[i][j] = M[i + (1 << (j - 1))][j - 1]; } int RMQ( int i , int j ) { int k = log2( j - i + 1 ) ; if( A[M[i][k]] > A[M[ j - (1<
{ if (phi[p] == p) { phi[p] = p-1; for (int i = 2*p; i<=n; i += p) { phi[i] = (phi[i]/p) * (p-1); } } } } Articulation Point void dfs (int v, int p = -1) { used[v] = true; tin[v] = fup[v] = timer++; int children = 0; for (size_t i=0; i = tin[v] && p != -1) IS_CUTPOINT(v); ++children; } } if (p == -1 && children > 1) IS_CUTPOINT(v); } int main() { timer = 0; dfs (0) } Bridge vector g[MAXN]; bool used[MAXN]; int timer, tin[MAXN], fup[MAXN]; void dfs (int v, int p = -1) { used[v] = true; tin[v] = fup[v] = timer++; for (size_t i=0; i
int to = g[v][i]; if (to == p) continue; if (used[to]) fup[v] = min (fup[v], tin[to]); else { dfs (to, v); fup[v] = min (fup[v], fup[to]); if (fup[to] > tin[v]) IS_BRIDGE(v,to); } } } void find_bridges() { timer = 0; for (int i=0; i 1) { q = a / b; t = b, b = a % b, a = t; t = x0, x0 = x1 - q * x0, x1 = t; } if (x1 < 0) x1 += b0; return x1; } int chinese_remainder(int *n, int *a, int len) { int p, i, prod = 1, sum = 0; for (i = 0; i < len; i++) prod *= n[i]; for (i = 0; i < len; i++) { p = prod / n[i]; sum += a[i] * mul_inv(p, n[i]) * p; } return sum % prod; } int main(void) {

int n[] = { 3, 5, 7 }; int a[] = { 2, 3, 2 }; printf("%d\n", chinese_remainder(n, a, sizeof(n)/sizeof(n[0]))); return 0; } General solution = ans + mult(n[0]:n[n – 1])k for every non-negative integer k Fast and Simple LIS multiset < int > s; multiset < int > :: iterator it; FOR(i, 1, n) { s.insert(a[i]); it = s.upper_bound(a[i]); if(it != s.end()) s.erase(it); } cout << s.size() << endl; Fast and Simple LCS

Topological Sort Do a reverse DFS tree with postorder traversal!!!!!!! Simple SCC Do a TopoSort and a DFS with Toposort Order (don’t forget to compute the component each traversal) Bipartite Matching Just Color the node with Red-Blue, without 2 adjacent node with same color Simple Maximum Bipartite Matching

Reserved for Some Math

Prime test with Rabin-miller strong pseudoprime test Ghoib! With worst case take 200 Steps and Less than 100 Steps on Average

Moving to Computational Geometry!! ☹☹ Usable struct for point

Some Annoying Orientation

Convex Hull O(n logn)

Some covex testing Algorithm?

Shoelace Formula

Intesection Point

Minimum Enclosing Circle (EASY maranatha Qualification) #include #include int n; double x[1005], y[1005], X, Y, d, e; double dist(double a, double b) { return a*a + b*b; } int main() { scanf("%d", &n); for (int i = 0; i < n; i++) { scanf("%lf%lf", &x[i], &y[i]); X += x[i]; Y += y[i]; } X /= n; Y /= n; double P = 0.1; for (int i = 0; i < 30000; i++) { int f = 0; d = dist(X - x[0], Y - y[0]); for (int j = 1; j < n; j++) { e = dist(X - x[j], Y - y[j]); if (d < e) { d = e; f = j; } } X += (x[f] - X)*P; Y += (y[f] - Y)*P; P *= 0.999; } printf("%.3lf %.3lf\n%.3lf", X, Y, sqrt(d)); } Some geometric fact

Easy Josephus Problem from Quora (BEWARE OF OVERFLOW)

Maximum submatrix sum Brute Force 2 Column, and use kadane for the row Largest Rectangle in Histogram int largestRectangleArea(vector & heights) { int maxRect = 0; stack stack; for (unsigned i = 0; i <= heights.size(); ) { if (stack.empty() || i < heights.size() && heights[i] >= heights[stack.top()]) { stack.push(i++); continue; } const int currentHeight = heights[stack.top()]; stack.pop(); const int rect = currentHeight * (i - (stack.empty() ? -1 : stack.top()) - 1); if (rect > maxRect) { maxRect = rect; } } return maxRect; } Maximum binary sub matrix Consider every row as a histogram Binomial Coefficient int binomialCoeff(int n, int k) { int res = 1;

// Since C(n, k) = C(n, n-k) if ( k > n - k ) k = n - k; for (int i = 0; i < k; ++i) { res *= (n - i); res /= (i + 1); } return res; } Reserver for Bit magic A |= (1 << i) (set ith bit), A &= ~(1 << i) (unset ith bit), A & (1 << i) (check if the ith bit is set), A ^= (1 << i) (toggle the ith bit), T = A & (-A) (LSB), T = v && (v & (v – 1)) (true for 2^k), A |= B (merge 2 bits), __builtin_popcount(A) (count set bits on A), __builtin_ctz(A) (count trailing zero on A), __builtin_clz(A) (count leading zero on A) MSB(long N) { //changing all right side bits to 1. N = N| (N>>1); N = N| (N>>2); N = N| (N>>4); N = N| (N>>8); … 16 for 32 bit and 32 for 64 bit return (N+1)>>1; } TIPS!!! Dont panic! Don’t ever rely on FAST-IO!!! Avoid cin use scanf instead If Kruskal got TLE, use Union by rank, if still TLE, try Prim If int is enough, use it. Long long can cause TLE Extra care is always needed when we deal with precision problems and special cases in geometry. There are many nice little tricks to deal with these, which are beyond the scope of this cheat sheet.

Cheat Sheet 695k5c

Overview 4q3b3c

More details 26j3b

Related Documents 171j1w

Cheat Sheet 695k5c

Cheat Sheet 695k5c

Cheat Sheet 695k5c

Cheat Sheet 695k5c

Cheat Sheet 695k5c

Cheat Sheet 695k5c

More Documents from "FąĎhiĽ セフィロス" 285v4i

Askep Ibu Menyusui 275x1j