saadtaame/aui-programming-contest-manual

The AUI notebook for programming contests.

aui-programming-contest-manual's Issues

Fast Modular Power

Problem

Compute a to the power b modulo 100000007 where a, b <= 1e9

Implementation

#include <cstdio>

using namespace std;

typedef long long ll;

int mod = int(1e9) + 7;

ll fastModPow(int a, ll b, int &mod) {
  if( !b ) return 1;

  ll res = fastModPow(a, b / 2, mod);
  res *= res;
  if( res >= mod ) res %= mod;

  if( b % 2 ) res *= a;
  if( res >= mod ) res %= mod;

  return res;
}

int main( void ) {
  int a; ll b;
  scanf("%d %lld", &a, &b);

  printf("%lld\n", fastModPow(a, b, mod));

  return 0;
}

Notes

In the code above, I have used a reference to mod because it is less costly and the mod doesn't change over time and I declared the mod at the top as a global this is not necessary and varies depending on the problem on hand.

This fasModPow function also helps in computing binomial coefficients especially if the mod is prime

PS: I will add the link to a cool theorem when I have time

Fast Modular (% prime) Inverses

Fast Modular Inverses

Find inverses of all numbers 1 through P-1 where P is a prime number in O(P) time. One can find mod inverses of all numbers from 1 to P-1 by using Fermat's little theorem but that takes time (P lg P). This technique is much more efficient. It is based on the following recurrence relation:

inverse[1] = 1
inverse[i] = -(P / i) * inverse[P mod i];

Implementation

#include <cstdio>
#include <cassert>
#include <iostream>

using namespace std;

const int P = 11; // To adjust (must be prime).
long long r[P];

/* For debugging only */
long long power(long long x, long long y) {
    if(y == 0)
        return 1;

    long long ans = power(x, y / 2);
    ans = (ans * ans) % P;
    if(y % 2 == 1)
        ans = (ans * x) % P;

    return ans;
}

/* Example */
int main( void ) {
    r[1] = 1;
    for(int i = 2; i < P; i++)
        r[i] = ((P - (P / i)) * r[P % i]) % P;

    // Check
    for(int i = 1; i < P; i++)
        assert(power(i, P - 2) == r[i]);

    return 0;
}

Minimum Spanning Tree (Kruskal's Algorithm)

Problem: Minimum Spanning Tree: (Kruskal's Algorithm)

Input:

You are given a connected undirected graph G. You want to know what is the minimum spanning tree (a tree with the minimal total weighting of its edges )that connects all the vertices in the graph G.

Output:

Weight of the tree with the minimal total weighting of graph G's edges.
(In this implementation, we displayed the edges that construct the MST)

Running Time:

E : Number of Edges, V : number of vertices

• Sorting : O(E log E)
• Union-find: O(log V)
• Overall: O(E log V)

Implementation:

#include <cstdio>
#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
#define MAXN 30023
#define eps 1e-7

using namespace std;

struct edge {
    int u, v, w;

    bool operator < (edge o) const {
        if( abs(o.w - w) < eps )
            return pair<int, int>(u, v) < pair<int, int>(o.u, o.v);
        return w < o.w;
    }
};


int p[MAXN];
vector<edge> edgeList;
vector< pair<int,int> > connectedEdges;

int find(int u) {
    return p[u] == u ? u : find(p[u]);
}

void merge(int u, int v) {
    int pu = find(u), pv = find(v);
    p[pu] = pv;
}

int main(void){
    int u, v, w, n, e;

    while(true){
        cin >> n >> e;
        if(n == 0 && e == 0) return 0;
        edgeList.clear();
        connectedEdges.clear();
        for(int i = 0; i < e; i++){
            cin >> u >> v >> w;
            edgeList.push_back((edge){u, v, w});
        }

        sort(edgeList.begin(), edgeList.end());
        for(int i = 0; i < n; i++) p[i] = i;

        int res = 0;
        for(int i = 0; i < edgeList.size(); i++) {
            int u = edgeList[i].u, v = edgeList[i].v;
            if( find(u) == find(v) ) continue;
            merge(u, v);
            res += edgeList[i].w;
            if(edgeList[i].v > edgeList[i].u){
                connectedEdges.push_back(make_pair(edgeList[i].u, edgeList[i].v));
            } else {
                connectedEdges.push_back(make_pair(edgeList[i].v, edgeList[i].u));
            }
        }

        sort(connectedEdges.begin(), connectedEdges.end());
        if(res == 0 || connectedEdges.size() != n - 1) puts("Impossible");
        else {
            cout << res << endl;
            for (int i = 0; i < connectedEdges.size(); i++){
                cout << connectedEdges[i].first << " " << connectedEdges[i].second << endl;
            }
        }
    }
    return 0;
}

KMP

KMP

A C++ implementation of the Knuth-Morris-Pratt algorithm for sequences of integers. The program reads two integers m, the length of the pattern, and n, the length of the sequence to search in. The program then reads the pattern and the sequence and prints positions (0 based) where the pattern occurs as a contiguous sub-sequence of the original sequence.

Sample input/output:

input:

2 10
3 5
3 3 5 3 -1 3 3 5 5 1

output:

match at 1
match at 6

Implementation

#include <cstdio>

const int N = 5000; /* max pattern length - adjust */
int m, n; /* pattern length, text length */

int p[N]; /* pattern */
int f[N]; /* suffix links */

int main(void)
{   scanf("%d %d", &m, &n);
    for(int i = 0; i < m; i++)
    {   scanf("%d", &p[i]);
    }

    /* build automaton (fill the f array) */
    f[0] = -1;
    for(int i = 1; i < m; i++)
    {   int k = f[i - 1];
        while(p[k + 1] != p[i] && k >= 0) k = f[k];
        if(k == -1 && p[0] != p[i]) f[i] = -1;
        else f[i] = k + 1;
    }

    /* match */
    int x;
    int k = -1, pos = 0;
    for(int i = 0; i < n; i++)
    {   scanf("%d", &x);
        while(p[k + 1] != x && k >= 0) k = f[k];
        if(k == -1 && p[0] != x) k = -1;
        else k = k + 1;

        if(k == m - 1)
        {   printf("match at %d\n", pos - m + 1);
        }
        pos++;
    }

    return 0;
}

LCA

LCA

Quick lowest-common-ancestor queries using sparse tables. The function lca(x,y) takes two node identifiers in a rooted tree and returns their lowest common ancestor (LCA for short). The function takes O(lg N) time where N is the number of nodes in the tree. A O(N lg N) pre-processing step is needed to build the sparse table.

API

• void init( void ); // Initialize the module (assumes that the tree is built and the number of nodes is stored in variable n
• void lca(int x, int y) // Lowest common ancestor of x and y

Other uses

This data structure can also be used to quickly answer path-queries in a (weighted) rooted tree. Examples include:

• Find sum of weights on path from node x to node y.
• Find min/max edge weight on path from node x to node y.
• Find weight of path from node x to node y.

The data structure can support updates by adding a function to update the sparse table. An update can be implemented in time O(lg N) so both operations are fast.

Implementation

#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1000010; /* Max nodes */
const int M = 30; /* Max LOG */
int LG;
int n;

vector<int> adj[N]; /* Adjacency list */
int p[N][M]; /* Sparse table */
int depth[N];

void init( void ) {
    LG = 0;
    while((1 << LG) < n)
        LG += 1;

    for(int i = 0; i < n; i++)
        for(int j = 0; j < LG; j++)
            p[i][j] = -1;
}

void dfs(int x, int par = -1, int d = 0) {
    depth[x] = d;

    p[x][0] = par;
    for(int i = 1; i < LG; i++)
        if(p[x][i - 1] + 1)
            p[x][i] = p[p[x][i - 1]][i - 1];

    for(auto y: adj[x])
        if(y != par)
            dfs(y, x, d + 1);
}

int lca(int x, int y) {
    if(depth[x] > depth[y])
        swap(x, y);

    for(int i = LG - 1; i >= 0; i--)
        if((p[y][i] + 1) && (depth[p[y][i]] >= depth[x]))
            y = p[y][i];

    if(x == y)
        return x;

    for(int i = LG - 1; i >= 0; i--)
        if((p[x][i] + 1) && (p[x][i] != p[y][i]))
            x = p[x][i], y = p[y][i];

    return p[x][0];
}

 /* Example */
int main( void ) {
    cin >> n;
    for(int i = 0; i < n; i++)
        adj[i].clear();

    for(int i = 0; i < n; i++) {
        int len;

        cin >> len;
        while(len--) {
            int x;

            cin >> x;
            adj[i].push_back(x);
            adj[x].push_back(i);
        }
    }

    /* Init and pre-process */
    init();
    dfs(0);

    /* Answer queries */
    int q;

    cin >> q;
    while(q--) {
        int x, y;

        cin >> x >> y;
        cout << lca(x, y) << endl;
    }

    return 0;
}

Suffix-Sort

suffix-sort

A C++ implementation of suffix sorting. The algorithm takes a string s as input and returns a vector sa where sa[i] is the position where the ith smallest suffix of s begins. This implementation takes time O(n lg n lg n) where n is the length of s.`

API

• suffixSort(s); // Create and return a suffix-array (vector of integers)

Implementation

#include <cstdio>
#include <string>
#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;

struct Suffix {
    int index;
    int rank[2];

    Suffix() {}
    Suffix(int index_, int rank_a, int rank_b) {
        index = index_;
        rank[0] = rank_a;
        rank[1] = rank_b;
    }
};

bool suffCmp(const Suffix &S, const Suffix &T) {
    if(S.rank[0] < T.rank[0])
        return true;
    else if(S.rank[0] == T.rank[0])
        return (S.rank[1] < T.rank[1]);
    return false;
}

vector<int> suffixSort( string &s ) {

    int n = (int)s.size();

    vector<int> rnk(n);
    for(int i = 0; i < n; i++)
        rnk[i] = (int)s[i];

    vector<Suffix> suff(n);
    for(int len = 1; ; len *= 2) {
        for(int i = 0; i < n; i++)
            suff[i] = Suffix(
                i,
                rnk[i],
                ((i + len < n) ? rnk[i + len]  : -1)
            );

        sort(suff.begin(), suff.end(), suffCmp);

        rnk[suff[0].index] = 0;
        for(int i = 1; i < n; i++)
                rnk[suff[i].index] = rnk[suff[i - 1].index] +
                    (suffCmp(suff[i - 1], suff[i]) ? 1 : 0);

        if(rnk[suff.back().index] == n - 1)
            break;
    }

    vector<int> sa(n);
    for(int i = 0; i < n; i++)
        sa[i] = suff[i].index;

    return sa;
}

/* Example */
int main( void ) {

    string s;
    cin >> s;

    vector<int> sa = suffixSort(s);

    int n = (int)s.size();
    for(int i = 0; i < n; i++)
        cout << sa[i] << " ";
    cout << endl;

    return 0;
}

Segment Tree

Segment Tree Data Structure

Description:

Given an array. We perform some changes and queries on continuous segments. It mainly supports 2 operations:

1. Update one element in the array .
2. Find/Query a result of an operation (add, subtract, multiply, gcd, lcm...) on elements on some segment (range).

Input:

Array A, N: Size of the Array, K: Number of operations,
Type of the operation if it is UPDATE : it will require 2 arguments which are the index that should be updated and the new value. If it is QUERY: it will require 2 arguments which are left index and the right index of the segment/range.

Output:

Answer of the performed operation (add, subtract, multiply, gcd, lcm...) on a given segment.

Running Time :

• Constructing the tree : O(N)
• Update : O(Log N)
• Query : O(Log N)

Implementation:

#include <cstdio>
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct SegmentTree {
    vector<int> t;
    int n;

    SegmentTree() {}

    SegmentTree(int n_) {
        t.resize(4 * n_);
        fill(t.begin(), t.end(), 0);

        n = n_;
    }

    void build(vector<int> &a, int p, int l, int r) {
        if(l == r)
            t[p] = a[l];
        else {
            int mid = (l + r) / 2;
            build(a, 2 * p, l, mid);
            build(a, 2 * p + 1, mid + 1, r);
            t[p] = t[2 * p] + t[2 * p + 1]; // you return the operation that is required (sum, mul, sub, gcd, lcm...)
        }
    }

    /* [l,r] is node interval and [i,j] is query interval
       p is current node in tree
    */
    int query(int p, int l, int r, int i, int j) {
        if(r < i || j < l)
            return 0; /* Neutral element (does not change output) */

        if(l >= i && r <= j)
            return t[p];

        int mid = (l + r) / 2;
        int leftAns = query(2 * p, l, mid, i, j);
        int rightAns = query(2 * p + 1, mid + 1, r, i, j);
        return (leftAns + rightAns); // you return the operation that is required (sum, mul, sub, gcd, lcm...)
    }

    void update(int p, int l, int r, int pos, int newValue) {
        if(l == r)
            t[p] = newValue;
        else {
            int mid = (l + r) / 2;
            if(pos <= mid)
                update(2 * p, l, mid, pos, newValue);
            else
                update(2 * p + 1, mid + 1, r, pos, newValue);

            t[p] = t[2 * p] + t[2 * p + 1]; // you return the operation that is required (sum, mul, sub, gcd, lcm...)
        }
    }
};

SegmentTree build(vector<int> &a) {

    int n = (int)a.size();
    int l = 0;
    int r = n - 1;
    int p = 1;

    SegmentTree tree(n);
    tree.build(a, p, l, r);

    return tree;
}

int query(SegmentTree &tree, int l, int r) {
    return tree.query(1, 0, tree.n - 1, l, r);
}

void update(SegmentTree &tree, int pos, int value) {
    tree.update(1, 0, tree.n - 1, pos, value);
}

vector<int> V;

int main(void){
    int N, K, l, r, p;
    cin >> N >> K;
    char op;

    SegmentTree tree(N);

    while(K--){
        cin >> op;
        if(op == 'F'){
            cin >> p;
            if(query(tree, p - 1, p - 1) == 0)
                update(tree, p - 1, 1);
            else 
                update(tree, p - 1, 0);
        } 
        else {
            cin >> l >> r;
            cout << query(tree, l - 1, r - 1) << endl;
        }
    }

    return 0;
}

Union-Find

union-find

A C/C++ implementation of union by rank and find with path compression. The operations are fast and the implementation uses one array only. Applications include connectivity tests and finding minimum spanning trees (to name a few).

API

• init(); // Initialize module
• int root(int x); // Returns the representative of the disjoint set containing x
• void join(int x, int y); // Unify the sets containing x and y

Implementation

#include <cstdio>
#include <cassert>
#include <vector>
#include <iostream>

using namespace std;

const int N = 1000010;
int n;

int uf[N];

void init( void ) {
    for(int i = 0; i < N; i++)
        uf[i] = -1;
}

/* Find root of set containing x */
int root( int x ) {
    int r = x;

    /* Find root */
    while(uf[r] >= 0)
        r = uf[r];

    /* Compress path to root */
    while(uf[x] >= 0) {
        int tmp = uf[x];
        uf[x] = r;
        x = tmp;
    }

    return r;
}

/* Union of sets containing x and y */
void join( int x, int y ) {
    x = root(x);
    y = root(y);

    if(x != y) {
        if(uf[x] < uf[y]) {
            uf[x] += uf[y];
            uf[y] = x;
        }
        else {
            uf[y] += uf[x];
            uf[x] = y;
        }
    }
}

/* Example */
int main( void ) {

    init();

    assert(root(1) != root(2));
    join(1, 2);
    assert(root(1) == root(2));

    join(3, 4);
    join(2, 3);
    assert(root(1) == root(4));

    return 0;
}

bfs ( breath first search )

Problem

You are given a list of bidirectional edges describing a connected graph and a starting node and want to label every node according to its level or distance from the starting node ( distance in this case refers to shortest path since the graph is unweighted )

Input

the first line will contain two integers n ( number of nodes ) and m ( number of edges ). Followed by m lines, each one contains two integers u and v that means there is an edge between node u and node v. The last line contains one integers, the starting node s.

Output

A list of integers, where entry i is the distance from node s to node i

Implementation

#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

vector<int> bfs(int n, vector<vector<int> > &adj, int s) {
  vector<int> dist(n, -1);
  queue<int> q;

  q.push( s );
  dist[s] = 0;

  while( !q.empty() ) {
    int u = q.front();
    q.pop();

    for(int i = 0; i < adj[u].size(); i++) {
      int v = adj[u][i];

      // check if node v is visited
      if( dist[v] == -1 ) {
        dist[v] = dist[u] + 1;
        q.push( v );
      }
    }
  }

  return dist;
}

int main( void ) {
  int n, m;
  scanf("%d %d", &n, &m);

  vector<vector<int> > adj(n);
  for(int i = 0; i < m; i++) {
    int u, v; scanf("%d %d", &u, &v);
    adj[u].push_back( v );
    adj[v].push_back( u );
  }

  int s; scanf("%d", &s);

  vector<int> dist = bfs(n, adj, s);
  for(int i = 0; i < n; i++)
    printf("%d%c", dist[i], i == n - 1 ? '\n' : ' ');

  return 0;
}

Proof

In this section, we will look at why does BFS also computes the shortest path in an unweighted graph. This is only a quick explanation, you can find a better designed proof in CLRS.

The way we can see a bfs is as a level traversal so from the starting node which the zero level we follow its edges to the next level ( i.e. level one ). This means that we touch all the nodes we can get to using only one step every time. The point is that when you arrive to a node at a certain level, there is no way to get there with a lower level because if you do then that means that node ought to have been visited beforehand.

Notes

In the implementation above, you can see that in the vector declaration there is a space between two last > this is because in old c++ compilers >> in interpreted as a right bitwise shift; however, this issue has been resolved in C++11 so if you are compiling with C++11 then no worries. C++11 is now available on most platforms and is the one used during the onsite competitions.
inlay

Fast Prime Factorization

Fast Prime Factorization

Compute prime factors of a number in logarithmic time after computing sieve. The algorithm computes for each number a in the range [2..N) the lowest prime factor of a. Factorizing a number then becomes just repeated division by these lowest factors.

API / Data Structures

• int lf[N]; // lf[x] is lowest prime factor of x
• sieve(); // compute sieve
• factorize(x); // compute prime factors of x

Implementation

#include <iostream>

using namespace std;

const int N = 100010;
int lf[N]; // Lowest prime factor

void sieve( void ) {
    for(int i = 2; i < N; i += 2)
        lf[i] = 2;

    for(int i = 3; i < N; i += 2)
        if(lf[i] == 0) {
            lf[i] = i;
            for(int j = i + i; j < N; j += i) {
                if(lf[j] == 0)
                    lf[j] = i;
            }
        }
}

void factorize( int n ) {
    while(n > 1) {
        cout << lf[n] << " ";
        n /= lf[n];
    }
    cout << endl;
}

/* Example */
int main( void ) {
    sieve();
    for(int i = 1; i <= 100; i++)
        factorize(i);

    return 0;
}