Home » Archives for 2011-08-14

Windows 7 Command Prompt Commands

   11:57 PM      

Append: It can be used by programs to open files in another directory as if they were located in the current directory. Arp: It is used to display or change entries in the ARP cache.. Assoc: The assoc command is used to display or change the file type associated with a particular file extension.. At: The...

  

vi/vim cheat sheet

   11:16 PM      

My vi/vim cheatsheet Cursor movement h - move left j - move down k - move up l - move right w - jump by start of words (punctuation considered words) W - jump by words (spaces separate words) e - jump to end of words (punctuation considered words) E - jump to end of words (no punctuation) b...

  

C++ String references with example

   11:14 PM      

C++ String Examples body{color:#000051;position:relative;top:157; scrollbar-face-color:#FFFFFF; scrollbar-arrow-color:#000051; scrollbar-track-color:#FFFFFF;} .blue{color:red;font-weight:bold;} .green{color:green;} constructors 1. #include <iostream> #include...

  

Strongly Connected Component (Tarjan)

   8:00 PM      

vector< int > M[MX]; int color[MX],f[MX],low[MX],ftm,st[MX],top,scc; bool instack[MX]; void dfs(int u){ int i,v,sz; f[u] = ftm; low[u] = ftm; ftm++; st[top] = u;top++;instack[u] = true; sz = M[u].size(); color[u] = 1; for(i=0;i<sz;i++){ v = M[u][i]; if(!color[v]){ dfs(v); low[u]...

  

Maximum Flow (basic)

   7:58 PM      

vector < int > M[mx]; int pre[mx], cap[mx][mx]; bool color[mx]; int bfs(int s, int t){ int ok,u,v,sz,i,path_cap; memset(pre,-1,sizeof(pre)); memset(color,0,sizeof(color)); queue < int > q; color[s] = 1; q.push(s); ok = 1; while(!q.empty() && ok){ u = q.front(); q.pop(); sz...

  

Minimum Spanning Tree (Kruskal)

   7:57 PM      

struct node { int u,v,w; bool operator < ( const node &b) const{ return w<b.w; } }e[mx]; int pr[mx]; int find(int r) { return r==pr[r]?r:(pr[r]=find(pr[r])); } int mst(int n,int m){ int i,u,v,r=0; for(i=1;i<=n;i++) pr[i]=i; sort(e,e+m); for(i=0;i<m;i++)...

  

Max flow with min cut

   7:54 PM      

vector < int > M[mx]; i64 cap[mx][mx], CAP[mx][mx]; int pre[mx]; bool color[mx]; i64 bfs(int s, int t){ int ok,u,v,sz,i; i64 path_cap; memset(pre,-1,sizeof(pre)); memset(color,0,sizeof(color)); queue < int > q; color[s] = 1; q.push(s); ok = 1; while(!q.empty() && ok){ u...

  

Convex Hull (Grahm Scan)

   7:47 PM      

point fp; bool cmp(const point &a,const point &b){ i64 d = isLeft(fp,a,b); if(d<0)return false; if(feq(d,(i64)0) && (dist(fp,a) > dist(fp,b)) )return false; return true; } void ConvexHull(point p[], point c[], int &np, int &nc){ int i,j,pos = 0,k; i64 dd; bool...

  

Miscellaneous Geometry

   7:44 PM      

#include <iostream> #include <cstdio> #include <cstdlib> #include <cmath> #include <vector> #include <map> #include <algorithm> using namespace std; #define mx 100 #define pii pair < int, int > #define i64 long long #define eps 1e-9 #define _min(i,j)...

  

Bipartite Matching (Basic)

   7:16 PM      

#define mx 210 vector < int > g[mx]; int lf[mx],rt[mx],n; bool vis[mx]; bool dfs(int p) { int i,j=g[p].size(); for(i=0;i<j;i++) if(!vis[g[p][i]]) { vis[g[p][i]]=1; if(rt[g[p][i]]==-1 || dfs(rt[g[p][i]])) { rt[g[p][i]]=p; lf[p]=g[p][i]; return true; } } return false; } int...

  

Bellman Ford

   4:51 PM      

vector < pii > M[mx]; int d[mx]; bool bellman_ford(int s,int n){ int i,u,j,sz,v,w; bool done = false; for(i=0;i<n;i++)d[i] = inf; d[s] = 0; for(i=0;i<n && !done;i++){ done = true; for(u=0;u<n;u++){ sz = M[u].size(); for(j=0;j<sz;j++){ v = M[u][j].first; w...

  

Bridge Network

   4:50 PM      

#define mx 110 #define _min(i,j) ((i)>(j)?(j):(i)) int d[mx],low[mx],t; bool color[mx],artp[mx]; vector < int > M[mx]; vector < pii > bridge; void dfs(int par, int u){ int sz,i,v; low[u] = d[u] = ++t; color[u] = 1; sz = M[u].size(); for(i=0;i<sz;i++){ v = M[u][i]; if(v==par)continue; if(!color[v]){ dfs(u,v); low[u]...

  

Articulation Point

   4:48 PM      

#define mx 110 #define _min(i,j) ((i)>(j)?(j):(i)) int d[mx],low[mx],t; bool color[mx],artp[mx]; vector < int > M[mx]; void dfs(int par, int u){ int sz,i,v,child = 0; low[u] = d[u] = ++t; color[u] = 1; sz = M[u].size(); for(i=0;i<sz;i++){ v = M[u][i]; if(v==par)continue; if(!color[v]){ child++; dfs(u,v); low[u]...

  

Single Source Shortest Path (Dijkstra)

   4:45 PM      

struct comp { bool operator() (const pii &a, const pii &b) { return a.second > b.second; } }; int color[mx], d[mx], nodes; vector < pii > path[MX]; int dijkstra(int source, int dest){ int u,v,sz,y,z; priority_queue< pii, vector< pii >,comp > q; for(v...

  

Number of Divisor

   4:40 PM      

i64 noOfDivisor(i64 n){ int j,f; i64 cnt,ans=1; f = 0; for(j=0;prime[j]<=n && j<prlen;j++){ cnt = 0; if(n%prime[j]==0){ while(n%prime[j]==0){ cnt++; n /= prime[j]; } f=1; ans *= (cnt+1); } } //if(!f || n!=1)cnt++; if(n^1)ans <<= 1; return ans...

  

Template

   4:37 PM      

//Bismillahir Rahmanir Rahim //#pragma warning(disable:4786) //#pragma comment(linker,"/STACK:514850816") #include <iostream> #include <cstdio> #include <cstdlib> #include <cmath> #include <cctype> #include <cstring> #include <climits> #include <string> #include...

  

Prime Factorization

   4:36 PM      

void PrimeFact( int n, int *factors, int *factCount, int &len){ int i,count, sqrtN; sqrtN = (int) sqrt( (double) n ) + 1; for(i = 0; prime[i] < sqrtN ; i++)if(!(n%prime[i])){ factors[len] = prime[i]; count = 0; while(!(n%prime[i]))n/=prime[i], count++; factCount[len++] = count; sqrtN...

  

Generating Prime (Sieve)

   4:34 PM      

#define mx 100000 #define chkp(n) (prm[n>>6]&(1<<((n>>1)&31))) #define genp(n) (prm[n>>6]|=(1<<((n>>1)&31))) #define PrimeLimit 10000000 int prm[PrimeLimit / 64], prime[mx], prlen; void GeneratePrime(){ int i,j,sqrtN; prlen = 0; prime[prlen++]=2; sqrtN...

  

Bignumber Subtraction

   4:26 PM      

void Subtraction(char *f, char *s, char *ans){ int lenf,lens,a,carry,ind,b; lenf = strlen(f)-1; lens = strlen(s)-1; carry = ind = 0; while(lens >=0 || lenf >=0){ b = ((lens >=0)?(s[lens--]-'0'):0) + carry; if(f[lenf] >=(b+'0')){a = f[lenf--]-'0';carry = 0;} else{a = f[lenf--]-'0'...

  

Bignumber Multiplication

   4:22 PM      

void Multiplication(char *f, char *s, char *sum){ int lenf,lens,i,j,k,carry,a; memset(sum,0,sizeof(sum)); lenf = strlen(f);lens = strlen(s); reverse(f,f+lenf);reverse(s,s+lens); for(i=0;i < lens;i++){ carry = 0;k = i; for(j=0;j < lenf;j++){ a = ( (f[j]-'0') * (s[i]-'0') ) + carry; if(i)...

  

Bignumber Addition

   12:10 PM      

void Addition(char *f, char *s, char *ans){ int lenf,lens,a,carry,ind; lenf = strlen(f)-1; lens = strlen(s)-1; carry = ind = 0; while(lens > =0 || lenf > =0){ a = ((lens > =0) ? (s[lens--]-'0') : 0) + ((lenf > =0) ? (f[lenf--]-'0') : 0) + carry; ans[ind++] = (a%10) + '0'; carry...