C++ Contest Template file (Header file and Pre-Processor template)


// @BEGIN_OF_SOURCE_CODE

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <cctype>
#include <stack>
#include <queue>
#include <list>
#include <vector>
#include <map>
#include <sstream>
#include <cmath>
#include <bitset>
#include <utility>
#include <set>
#include <numeric>
#include <ctime>

#define Inf 2147483647
#define Pi acos(-1.0)
#define N 1000000
#define LL long long

inline LL Power(int b, int p) { LL ret = 1; for ( int i = 1; i <= p; i++ ) ret *= b; return ret; }
const int dr [] = {-1, -1, 0, 1, 1, 1, 0, -1};
const int dc [] = {0, 1, 1, 1, 0, -1, -1, -1};

#define F(i, a) for( int i = (0); i < (a); i++ )
#define Fs(i, sz) for( size_t i = 0; i < sz.size (); i++ )
#define Fe(i, x) for(typeof (x.begin()) i = x.begin(); i != x.end (); i++)
#define Set(a, s) memset(a, s, sizeof (a))
#define Max(a, b)  (a < b ? b : a)
#define Min(a, b)  (a > b ? b : a)

using namespace std;

int main(int argc, const char ** argv[]) 
{
    
    return 0;	
}

// @END_OF_SOURCE_CODE

Union Find Algorithm Source Code (C/C++)



// @BEGIN_OF_SOURCE_CODE

#include <cstdio>
#include <cstring>

#define N 1000000
using namespace std;

int parent [N];

int findParent (int p)
{
    if ( parent [p] < 0 ) return p;
    return parent [p] = findParent(parent [p]);
}

int main ()
{
    int edges;
    scanf ("%d", &edges);

    memset (parent, -1, sizeof (parent)); // one child, ownself

    for ( int i = 0; i < edges; i++ ) {
        int a, b;
	scanf ("%d %d", &a, &b);

        int p = findParent (a);
        int q = findParent (b);

        if ( parent [p] < parent [q] ) { // p has more child
            parent [p] += parent [q];
            parent [q] = p;
        }

        else {
            parent [q] += parent [p];
            parent [p] = q;
        }
    }

    return 0;
}

// @END_OF_SOURCE_CODE

Travelling Salesman Problem (TSP) Algorithm Source Code (C/C++)



// @BEGIN_OF_SOURCE_CODE

#include <cstdio>
#include <cstring>
using namespace std;

bool vis [CITY] [1 << CITY]; // is_visited
int val [CITY] [1 << CITY]; // cost at particular state
int weight [CITY] [CITY]; // given weight

int dp (int at, int mask)
{
    if ( mask ==  (1 << CITY) - 1 ) { // all visited
        vis [at] [mask] = true;
        return val [at] [mask];
    }

    if ( vis [at] [mask] ) return val [at] [mask];
    vis [at] [mask] = true;

    int ans = inf;
    int cost;

    for ( int i = 0; i < CITY; i++ ) {
        if ( weight [at] [i] != -1 && (mask & (1 << i)) == 0 ) {
            cost = dp (i, mask | (1 << i)) + weight [at] [i];
            if ( ans > cost ) ans = cost;
        }
    }

    return val [at] [mask] = ans;
}

int main ()
{
    memset (vis, false, sizeof (vis));
    memset (weight, -1, sizeof (weight));
    printf ("Cost : %d\n", dp (0, 1));

    return 0;
}

// @END_OF_SOURCE_CODE

Topological Algorithm Source Code (C/C++)



// @BEGIN_OF_SOURCE_CODE

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

int main ()
{
    vector <int> matrix [100];

    for ( int i = 0; i < edges; i++ ) {
        matrix [a].push_back (b);
        inDegree [b]++;
    }

    queue <int> Q;

    for ( int i = 1; i <= vertex; i++ ) {
        if ( inDegree [i] == 0 )
            Q.push (i);
    }

    vector <int> sortedList;

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

        sortedList.push_back (pop);

        for ( int i = 0; i < matrix [pop].size (); i++ ) {
            inDegree [matrix [pop] [i]]--;
            if ( inDegree [matrix [pop] [i]] == 0 )
                Q.push (matrix [pop] [i]);
        }
    }

    return 0;
}

// @END_OF_SOURCE_CODE

Minimum Spanning Tree: Kruskal Algorithm Source code (C/C++)



// @BEGIN_OF_SOURCE_CODE

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <cctype>
#include <stack>
#include <queue>
#include <list>
#include <vector>
#include <map>
#include <sstream>
#include <utility>
#include <set>
#include <math.h>

#define pi acos(-1.0)
#define N 1000000

using namespace std;

struct list {
    int start;
    int end;
    int distance;
} a [100 * 100]; // vertex * vertex

int parent [100]; // total vertex

bool cmp (list p, list q)
{
    if ( p.distance < q.distance ) return true;
    return false;
}

void reset ()
{
    for ( int i = 0; i < 100; i++ )
        parent [i] = i;
}

int parentOf (int n)
{
    if ( n == parent [n] ) return n;
    return parent [n] = parentOf ( parent [n] );
}

int main ()
{
    int edges;
    scanf ("%d", &edges);

    reset ();
    
    int length_a = 0;

    for ( int i = 1; i <= edges; i++ ) {
        int v1, v2, dist;
        a [length_a].start = v1;
        a [length_a].end = v2;
        a [length_a++].distance = dist;
    }

    sort (a, a + length_a, cmp);

    int outputCost = 0;
    int selectedEdges = edges - 1;

    for ( int i = 0; i < length_a && selectedEdges; i++ ) {
        int p = parentOf (a [i].start);
        int q = parentOf (a [i].end);

        if ( p != q ) {
            parent [p] = q;
            selectedEdges--;
            outputCost += a [i].distance;
        }
    }

    printf ("%d\n", outputCost);

    return 0;
}

// @END_OF_SOURCE_CODE

Simple Online Judge Program: Run C/C++ Code with Input Test Case Data Set


Purpose:
We are going to make a simple Online judge program

Statement:
a problem in any online judge has huge data set. Usually these are stored in input files. There are also corresponding output files. When you submit your program in online judge site, then your program are executed against the input files and produces, your program generated output files. Now there are two sets of output files. One is the correct output file set and other is the output file set produced by your program. Then the output files are compared and if they match exactly then your program is correct otherwise wrong.

Situation:
Guess you have the input data set files. For example, there are 10 input files. Each one contains one test case. Now very likely you have to run your code 10 times and with each time you need to change the input file name and run the code, then match the two set of output files manually, this is troublesome.

Background:
Once i was trying to solve the CROATIAN OPEN COMPETITION IN INFORMATICS past contest problems. You will find the problem set along with judgeData and sample solutions.

I try to solve the problem first and run my code against data set and if my code get accepted then i see the solution for a better idea.
As you can see they do not have any robot online judge, so i had to manually check the input data set files

finally i made a simple online judge program, which do the troublesome task for me

I just need to paste my code and change the input file name and bang! the rest of the task is gonna done by the simple online judge program.

Notes:
this code is applicable for Contest 1 Task name: Modulo

you have 10 input files named:
modulo.in.1
modulo.in.2
.
.
.
modulo.in.10

and 10 output files named:
modulo.out.1
modulo.out.2
.
.
.
modulo.out.10

my generated output files will be named:
modulo.thisOut.1
modulo.thisOut.2
.
.
.
modulo.thisOut.10

How to run:
paste the input files and output files in folder named test_data/ inside your execution directory

#37: change the name with the first part of the file name, in this case modulo
#38: enter the number of files
#47: use the function callOut() as if it is main() function

now run this program


// @BEGIN_OF_SOURCE_CODE

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <cctype>
#include <stack>
#include <queue>
#include <list>
#include <vector>
#include <map>
#include <sstream>
#include <cmath>
#include <bitset>
#include <utility>
#include <set>
#include <numeric>
#include <ctime>
#include <unistd.h>

#define Inf 2147483647
#define Pi acos(-1.0)
#define N 1000000
#define LL long long

inline LL Power(int b, int p) { LL ret = 1; for ( int i = 1; i <= p; i++ ) ret *= b; return ret; }

#define F(i, a, b) for( int i = (a); i < (b); i++ )
#define Fs(i, sz) for( size_t i = 0; i < sz.size (); i++ )
#define Fe(i, x) for(typeof (x.begin()) i = x.begin(); i != x.end (); i++)
#define Set(a, s) memset(a, s, sizeof (a))
#define max(a, b)  (a < b ? b : a)
#define min(a, b)  (a > b ? b : a)

#define FILENAME "modulo"   // input data file name
#define CASES 10            // number of input files 

using namespace std;

/*
    This is the code function
    Use this function as if it is the "main()" function  
*/

void callOut()
{
    int ret = 0;
    bool vis [42];
    int num;

    Set (vis, false);

    for ( int i = 0; i < 10; i++ ) {
        scanf ("%d", &num);

        vis [num % 42] = true;
    }

    for ( int i = 0; i < 42; i++ ) {
        if ( vis [i] ) {
            ret++;
        }
    }

	printf ("%d\n", ret);
}

bool startCase(int caseNum)
{
    string pathName = "test_data/";
    pathName += FILENAME;

    string inStream = ".in.";
    string outStream = ".out.";

    string caseNumber = static_cast<ostringstream*>( &(ostringstream() << caseNum) )->str();

    string inputPath = pathName + ".in." + caseNumber;
    string outputPath = pathName + ".out." + caseNumber;
    string thisOutputPath = pathName + ".thisOut." + caseNumber;

    //cout << "Input: " << inputPath << endl;
    //cout << "Output: " << outputPath << endl;
    //cout << "thisOutput: " << thisOutputPath << endl;

    int    fd;
    fpos_t pos;

    fflush(stdout);
    fgetpos(stdout, &pos);
    fd = dup(fileno(stdout));

    freopen (inputPath.c_str(), "r", stdin);
    freopen (thisOutputPath.c_str(), "w", stdout);

    callOut();

    fclose(stdin);

	fflush(stdout);
    dup2(fd, fileno(stdout));
    close(fd);
    clearerr(stdout);
    fsetpos(stdout, &pos);

	char bufferIn [N];
	char bufferOut [N];

	FILE *inFile = fopen (outputPath.c_str() , "r");
	FILE *outFile = fopen (thisOutputPath.c_str(), "r");

	do {
        size_t fpIn = fread (bufferIn, 1, N, inFile);
        size_t fpOut = fread (bufferOut, 1, N, outFile);

        if (fpIn != fpOut || memcmp (bufferIn, bufferOut, fpIn)) {
            return false;
        }
	} while (!feof (inFile) && !feof(outFile));

	return feof(inFile) && feof(outFile);
}

int main ()
{
    for ( int i = 1; i <= CASES; i++ ) {
        printf ("Case %d: ", i);
        if (startCase(i)) {
            printf ("*Yes*\n");
        } else {
            printf ("Wrong ans!\n");
        }
    }

	return 0;
}

// @END_OF_SOURCE_CODE

Strongly Connected Components (SCC) Algorithm Source code (C/C++)



// @BEGIN_OF_SOURCE_CODE

#include <cstdio>
#include <cstring>
#include <vector>

#define N 1000000

using namespace std;

vector <int> edges [N];
vector <int> rEdges [N];    // reversed edges 
vector <int> sortedNode;

bool vis [N];

int comp [N];               // component number of a node 
int inDegree [N];           // in-degree of a component 

void reset ()
{
    for ( int i = 0; i < N; i++ ) {
        edges [i].clear();
        rEdges [i].clear();
    }

    sortedNode.clear();

    memset (vis, false, sizeof vis);
    memset (inDegree, 0, sizeof inDegree);
}

void dfs1 (int x)
{
    vis [x] = true;

    for ( size_t u = 0; u < edges [x].size(); u++ ) {
        if ( !vis [edges [x] [u]] )
            dfs1(edges [x] [u]);
    }

    sortedNode.push_back(x);
}

void dfs2 (int x, int c)
{
    vis [x] = false;

    comp [x] = c;

    for ( size_t u = 0; u < rEdges [x].size(); u++ ) {
        if ( vis [rEdges [x] [u]] )
            dfs2(rEdges [x] [u], c);
    }
}

int main ()
{
    int numberOfNodes;
    int numberOfEdges;

    reset ();

    for ( int i = 0; i < numberOfEdges; i++ ) {
        int from;       // edges from
        int to;         // edges to
        
        // take input in "form" and "to" 

        edges [from].push_back(to);
        rEdges [to].push_back(from);
    }

    for ( int i = 0; i < numberOfNodes; i++ ) {
        if ( !vis [i] ) 
            dfs1 (i);
    }

    int componentId = 0;

    for ( int i = sortedNode.size() - 1; i >= 0; i-- ) {
        if ( vis [sortedNode [i]] )
         dfs2(sortedNode [i], ++componentId);
    }

    // component indegree 
    for ( int i = 0; i < numberOfNodes; i++ ) {
        for ( size_t j = 0; j < edges [i].size(); j++ ) {
            if ( comp [i] != comp [edges [i] [j]] )
                inDegree [comp [edges [i] [j]]]++;
        }
    }

    return 0;
}

// @END_OF_SOURCE_CODE