UVa, SPOJ & TopCoder

First of all, thanks to Fahim vai, he gave me the idea first...

This is a very easy way to add a cool bookmark item on your browser which can easily locate UVa, SPOJ & TopCoder problems for you. After you follow these steps, you will be able to open any UVa / SPOJ problem with just a click, you even do not need to enter any web address !

UVa Locator:

Right click on bookmark toolbar of your browser. Then right click on it and select "New Bookmark...". So the new bookmark box will arrive. On the name field, put whatever you want, like "UVa" or something else and on the location field, paste the following javascript:

javascript:var%20pid=prompt('Enter%20problem%20number:');
location.href='http://uva.onlinejudge.org/external/'+pid.substring(0,pid.length-2)+'/'+pid+'.html';

Now, after clicking "Add", you will see a new bookmark item has been added to your browser's toolbar, just click on it and enter the problem number.. that's it!

Spoj Locator:

Similar process, add e new bookmark item, now, give a different name, for example, "SPOJ" and on the location, paste the following javascript:

javascript:var%20pid=prompt('Enter%20problem%20name:');
location.href='https://www.spoj.pl/problems/'+pid.toUpperCase()+'/'

Click "Add" and done!. Now you will get a similar bookmark item as the previous one. But as you know, spoj problems are recognized with their codnames, not numbers. So enter a code name in the textbox, don't bother about case, and click ok. It will open the page of the problem if it is there. For example, to open the problem "Longest Common Substring", it has a codename LCS, you should enter "LCS" in the box, (not necessarily all should be uppercase).

TopCoder Locator:

Similarly, topcoder problems are known by their respective class names, you can add a simple search box for topcoder problems by adding the following javascript in the similar way stated above:

javascript:var%20pid=prompt('Enter%20class%20name:');
location.href='http://www.topcoder.com/tc?module=ProblemArchive&class='+pid

It will not open the problem, it is a simple javascript that calls the search engine on topcoder to find the class name you provide.

As these will open in current window, make sure you open a new tab before using these to save some back, forward clicks ><><><
Have Fun !!!

Bigint Library by Jan vai

Thanks to Jane Alam Jan vai for this, It will be a great help... :)

/*
    Author       :    Jan
    Problem Name :    Big int for contest
    Algorithm    :
    Complexity   :
*/

#include <cstdio>
#include <string>
#include <algorithm>
using namespace std;

struct Bigint {
    string a;
    int sign;

    Bigint() {}
    Bigint( string b ) { (*this) = b; }
    int size() { return a.size(); }
    Bigint inverseSign() { sign *= -1; return (*this); }
    Bigint normalize( int newSign ) {
        sign = newSign;
        for( int i = a.size() - 1; i > 0 && a[i] == '0'; i-- ) a.erase(a.begin() + i);
        if( a.size() == 1 && a[0] == '0' ) sign = 1;
        return (*this);
    }
    void operator = ( string b ) {
        a = b[0] == '-' ? b.substr(1) : b;
        reverse( a.begin(), a.end() );
        this->normalize( b[0] == '-' ? -1 : 1 );
    }
    bool operator < ( const Bigint &b ) const {
        if( a.size() != b.a.size() ) return a.size() < b.a.size();
        for( int i = a.size() - 1; i >= 0; i-- ) if( a[i] != b.a[i] ) return a[i] < b.a[i];
        return false;
    }
    Bigint operator + ( Bigint b ) {
        if( sign != b.sign ) return (*this) - b.inverseSign();
        Bigint c;
        for( int i = 0, carry = 0; i < (int)a.size() || i < (int)b.size() || carry; i++ ) {
            carry += (i < (int)a.size() ? a[i] - 48 : 0) + (i < (int)b.a.size() ? b.a[i] - 48 : 0);
            c.a += (carry % 10 + 48);
            carry /= 10;
        }
        return c.normalize(sign);
    }
    Bigint operator - ( Bigint b ) {
        if( sign != b.sign ) return (*this) + b.inverseSign();
        if( (*this) < b ) return (b - (*this)).inverseSign();
        Bigint c;
        for( int i = 0, borrow = 0; i < (int)a.size(); i++ ) {
            borrow = a[i] - borrow - (i < b.size() ? b.a[i] : 48);
            c.a += borrow >= 0 ? borrow + 48 : borrow + 58;
            borrow = borrow >= 0 ? 0 : 1;
        }
        return c.normalize(sign);
    }
    Bigint operator * ( Bigint b ) {
        Bigint c("0");
        for( int i = 0, k = a[i]; i < (int)a.size(); i++, k = a[i] ) {
            while(k-- - 48) c = c + b;
            b.a.insert(b.a.begin(), '0');
        }
        return c.normalize(sign * b.sign);
    }
    Bigint operator / ( Bigint b ) {
        if( b.size() == 1 && b.a[0] == '0' ) b.a[0] /= ( b.a[0] - 48 ) ;
        Bigint c("0"), d;
        for( int j = 0; j < (int)a.size(); j++ ) d.a += "0";
        int dSign = sign * b.sign; b.sign = 1;
        for( int i = a.size() - 1; i >= 0; i-- ) {
            c.a.insert( c.a.begin(), '0');
            c = c + a.substr( i, 1 );
            while( !( c < b ) ) c = c - b, d.a[i]++;
        }
        return d.normalize(dSign);
    }
    Bigint operator % ( Bigint b ) {
        if( b.size() == 1 && b.a[0] == '0' ) b.a[0] /= ( b.a[0] - 48 ) ;
        Bigint c("0");
        int cSign = sign * b.sign; b.sign = 1;
        for( int i = a.size() - 1; i >= 0; i-- ) {
            c.a.insert( c.a.begin(), '0');
            c = c + a.substr( i, 1 );
            while( !( c < b ) ) c = c - b;
        }
        return c.normalize(cSign);
    }
    void print() {
        if( sign == -1 ) putchar('-');
        for( int i = a.size() - 1; i >= 0; i-- ) putchar(a[i]);
    }
};

int main() {
    Bigint a, b, c;
    a = "511";
    b = "10";

    c = a + b;
    c.print();
    putchar('\n');

    c = a - b;
    c.print();
    putchar('\n');

    c = a * b;
    c.print();
    putchar('\n');

    c = a / b;
    c.print();
    putchar('\n');

    c = a % b;
    c.print();
    putchar('\n');

    return 0;
}

Hope this helps my friends as well. Actually many of us are afraid of big integers, and also the above code may look hard, but this is actually what we do when performing these operations in real life... Use with caution, not a very first algorithm. Do not attempt to use *, /, % if numbers are 10⁴ or more digits long.

FIFA World Cup 2010

FIFA World Cup South Africa 2010 Official Theme Song

Lyrics

ooooooh wooooooh

give me freedom, give me fire,
give me reason, take me higher
see the champions, take the field now,
you define us, make us feel proud...
in the streets are, exaliftin',
as we lose our inhabition,
celebration its around us,
every nation, all around us

singin' forever young,
singin' songs underneath that sun
lets rejoice in the beautiful game
and together at the end of the day.

[chorus]:
we all say...

when I get older I will be stronger
they'll call me freedom
just like a wavin' flag
and then it goes back |||

when I get older I will be stronger
they'll call me freedom
just like a wavin' flag
and then it goes back |||

Oooooooooooooh woooooooooohh hohoho

give you freedom, give you fire,
give you reason, take you higher
see the champions, take the field now,
you define us, make us feel proud
in the streets are, exaliftin,
every loser in ambition,
celebration, its around us,
every nations, all around us

singin' forever young,
singin' songs underneath that sun
lets rejoice in the beautiful game.
and together at the end of the day.

[chorus]

Oooooooooooooh woooooooooohh hohoho

[chorus]
___________________________________

Song: Wavin' Flag
Artist: K'naan

Blogger Code Formatter

Blogger is a wonderful place to write blogs and there are many code bloggers out there, who want to share their coding skills with the world! But, certainly there are some problems with blogger posting methods, for example, in a <pre> tag, it will ignore tabs, and it causes great problems with some operators like '<', '>' etcetera... So, we can easily write a simple program and use it easily as a code formatter for blogger. Here's an example:

#include <cstdio>

int main(int argc, char **argv) {
    FILE *in = fopen(argv[1], "r");
    FILE *out = fopen(argv[2], "w");
    char ch;
    if(argc < 3) {
        printf("Usage: $ %s <infile> <outfile>\n", argv[0]);
        return 1;
    }
    if(in==NULL) {
        printf("file %s can't be opened.\n", argv[1]);
        return 2;
    }
    if(out==NULL) {
        printf("file %s can't be opened.\n", argv[2]);
        return 3;
    }
    while(fscanf(in, "%c", &ch)==1) {
        if(ch=='>') fprintf(out, "&gt;");
        else if(ch=='<') fprintf(out, "&lt;");
        else if(ch=='&') fprintf(out, "&amp;");
        else if(ch=='\t') fprintf(out, "    ");
        else fprintf(out, "%c", ch);
    }
    fclose(in);
    fclose(out);
    printf("file %s was written succesfully.\n", argv[2]);
    return 0;
}

Windows:

In windows, execute this with any compiler and grab the .exe file, paste it in your C:\WINDOWS\system32 folder. So, for example, if the file name is "blog.cpp", you will get "blog.exe", just paste it to your system32 folder. So now you can use it as a command in command prompt. If you like to format a file, say, "test.cpp", cd to the directory where "test.cpp" is, and to transform, the command is "blog test.cpp blog_test.cpp". Now just open the "blog_test.cpp" file and paste it in the <pre> tags.

Linux

Run it with g++, command: "g++ -o blog blog.cpp", and give enough permissions to the executable "blog", command: "chmod 777 blog". Now, we need to paste it in the "/bin" directory, but as it is write protected, we'll need to log in as root. To do this, write on prompt: "sudo nautilus", it will ask your password, and then an explorer will be opened, and now, just go to the "/bin" directory using it and paste the file. The usage is similar as stated in the Windows part.

Makes life a bit easier...

Testing Bipartite Graph

We can use BFS to check whether an undirected graph is bipartite or not, with only a little modification...

We define bipartite graph as follows: A bipartite graph is an undirected graph G = (V, E) in which V can be partitioned into two sets V1 and V2 such that (u, v) ∈ E implies either u ∈ V1 and v ∈ V2 or u ∈ V2 and v ∈ V1. That is, all edges go between the two sets V1 and V2.

In other to determine if a graph G = (V, E) is bipartite, we perform a BFS on it with a little modification such that whenever the BFS is at a vertex u and encounters a vertex v that is already 'gray', i.e. visited, our modified BSF should check to see if the depth of both u and v are even, or if they are both odd. If either of these conditions holds which implies d[u] and d[v] have the same parity, then the graph is not bipartite. Note that this modification does not change the running time of BFS and remains Θ(V + E).

Here goes a simple implementation of the above idea. We'll just run a BFS, while tracking the partition in which every node falls. If, when visiting node v from node u, and they are members of same partition, then this graph is not bipartite. Well, this time, I think, we have nothing to do with the edge weights or costs, so it will also work on a weighted graph.

Formally, to check if the given graph is bipartite, the algorithm traverse the graph labelling the vertices 0 or 1 / 2 , corresponding to unvisited or visited, and partition 1 or partition 2 depending on which set the nodes are in. If an edge is detected between two vertices in the same partition, the algorithm returns false immediately.

Note: In this implementation, only one test at a time is possible, to run it for multiple cases, definitely cares must be taken about resetting the arrays and other values as necessary.

#include <cstdio>
#include <vector>
#include <queue>
using namespace std;

#define MAX 1001

int n, e;
int partition[MAX], visited[MAX];
vector< int > G[MAX];

bool is_bipartite() {
    int i, u, v, start;
    queue< int > Q;
    start = 1; // nodes labeled from 1
    Q.push(start);
    partition[start] = 1; // 1 left, 2 right
    visited[start] = 1; // set gray
    while(!Q.empty()) {
        u = Q.front(); Q.pop();
        for(i=0; i < G[u].size(); i++) {
            v = G[u][i];
            if(partition[u] == partition[v]) return false;
            if(visited[v] == 0) {
                visited[v] = 1;
                partition[v] = 3 - partition[u]; // alter 1 and 2
                Q.push(v);
            }
        }
    }
    return true;
}

int main() {
    int i, u, v;
    scanf("%d %d", &n, &e);
    for(i = 0; i < e; i++) {
        scanf("%d %d", &u, &v);
        G[u].push_back(v);
        G[v].push_back(u);
    }
    if(is_bipartite()) printf("Yes\n");
    else printf("No\n");
    return 0;
}

As this algorithm traverses the graph it labels the vertices with a partition number consisted with the graph being bipartite. If at any vertex, algorithm detects an inconsistency, it shows with an invalid return value. Partition value of u will always be a valid number as it was en-queued at some point and its partition was assigned at that point. Partition of v will be unchanged if it is already set, otherwise it will be set to a value opposite to that of vertex u. So, if the algorithm returns true, it means, the graph is bipartite, i.e. bi-color-able, and partition[] holds the colors for each vertex.

Have fun, and let me know about errors, if any. [Note: The definition of bipartite graph is taken from this wonderful site]