Google Code Jam - C++ base code

The qualification round is over! I found myself checking other people's code and I decided for the next rounds I'd need some common code to cut short the development time. There is no point in keeping this a secret, because, anyone can read other people's code and *a lot of far better, and really good code* are there if you check the code of the top 20 or so.

I plan to stick with python, however if speed of execution becomes very crucial, this will be my plan B (my plan A - using pypy ;) ).

I am treating each test case as a separate object. And since there is usually no common data  shared between  test cases, they can and should be parallelized. Pthreads are doing the job well enough, though I will try to check something with OpenMP's #pragma directive.

Note that while using pthreads and treating each test case as completely different gives us some gain, memoizing becomes a little bit more painful.

I also couldn't resist the urge to implement an ugly forAll kind of function. The doWork() is just something to test the performance gain, run this using perf in linux... and read the code and do comment if you have any suggestion, or I'll simply hunt your code down and read and learn from it ;)

#include < iostream >
#include < vector >
#include < pthread.h >

using namespace std;

class TestCase{

    private:
        int begin,end,result;

    public:
        TestCase(){begin = end = result = 0;}
        TestCase(int x, int y):begin(x),end(y){}
        void doWork();
        friend ostream & operator < < (ostream & out1,TestCase &t1);
        friend istream & operator >> (istream & in1,TestCase &t1);
};

void TestCase::doWork(){
    for(int i = 0; i < begin; i++){
        for(int j = 0; j < end*10;j++){
            for(int k = 0; k < begin; k++){
                result += 1;
            }
        }
    }
}

ostream & operator << (ostream & out1,TestCase &t1){
    out1&lt&ltt1.result;
    return out1;
}

istream & operator >> (istream & in1,TestCase &t1){
    in1 >> t1.begin &gt&gt t1.end;
    return in1;
}


inline void forAllTestCases(const int &num_testcases, vector<TestCase *> &tarr, void (*func)(TestCase * tptr)){
    int i = 0;
    while(num_testcases - i){
        func(tarr[i++]);
    }
}

void try1(TestCase * tptr){
    tptr-&gtdoWork();
}

void *doWork(void *threadArg){
    TestCase *tmp;
    tmp = reinterpret_cast<TestCase *>(threadArg);
    tmp->doWork();
}

int main(){
    int num_testcases,i;
    vector<TestCase *> tarr;
    cin>>num_testcases;

//read the input - I usually redirect the stdin
    TestCase *tptr;
    for(i=0;i<num_testcases;i++){
        tptr = new TestCase;
        cin >> *tptr;
        tarr.push_back(tptr);
    }

    vector<pthread_t> mythreads(100);
    pthread_attr_t attr;
    pthread_attr_init(&attr);
    pthread_attr_setdetachstate(&attr,PTHREAD_CREATE_JOINABLE);
    void *status;
    int rc;

   
    for(i=0;i<num_testcases;i++)
    {
        rc = pthread_create(&mythreads[i],&attr,doWork, (void *) tarr[i]);
    }

    pthread_attr_destroy(&attr);

    //forAllTestCases(num_testcases,tarr,&try1);

//print the output
    for(i = 0; i < num_testcases; i++){
        rc = pthread_join(mythreads[i],&status);
        cout<<*tarr[i]<<endl;
    }

   
}

Store Credit - Google Code Jam 2010

Here is a solution for Google's Code Jam 2010 Store Credit problem.

In Python the code is very simple. It is a brute force kindda solution.

if __name__ == "__main__":
   
    fin = open('storeInput.inp','r')
    inputdata = fin.readlines()
    fin.close()
   
    it = iter(inputdata)

    numTestCases = int(it.next())
   
    fout = open('storeOutput.txt','w')

    for i in range(1,numTestCases+1):
        str1 = "Case #%d: " %(i)
        fout.write(str1)
       
        mycredit = int(it.next())
       
        num_items = int(it.next())

        items_cost = [int(y) for y in it.next().split()]
       
        found = False
        for j in range(len(items_cost)-1):
            if found:
                break
            for k in range(j+1,len(items_cost)):
                if((items_cost[j]+items_cost[k])==mycredit):
                    fout.write(str(j+1) + " "+ str(k+1) + "\n")
                    found = True
                    break
    fout.close()

In C, code for the same process is as follows,

#include
#include

void process(FILE *fin, FILE *fout)
{
    int storeCredit,I,*p, i,iActual = 0,j;
    fscanf(fin,"%d",&storeCredit);
    fscanf(fin,"%d",&I);
   
    p = (int *)malloc(sizeof(int)*I);
    for(i=0;i   

    for(i=0;i < I - 1; i++)
      for(j = i+1; j < I; j++)
            if((*(p+i) + *(p+j)) == storeCredit)
            {
                fprintf(fout,"%d %d\n",i+1,j+1);
                i = I;
                break;
            }
    free(p);
}

int main()
{
    FILE *fin,*fout;
    int N,i;
    fin = fopen("storeInput.inp","r");
    fout = fopen("storeOutput.txt","w");
   
    fscanf(fin,"%d",&N);
    for(i=0;i    {
        fprintf(fout,"Case #%d: ",i+1);
        process(fin, fout);
    }

    fclose(fin);
    fclose(fout);
}

To make the C code, even faster, I tried another one using pthreads. I'll update that later.