Google Code Jam - 2010

It was during GCJ 2009 when I got myself more involved in coding stuff. I still remember my last year's post about my performance at GCJ 2009. I can happily and proudly say that yes this year I showed some improvement..!!

Qualification Round:

The round started early morning and made me code even when the semesters were approaching..!! Nevertheless I went on for the third problem (Theme Park) first as it seemed much easier than others. Here's my code which I submitted for the correct submission.

#include<iostream>
#include<fstream>
#include<sstream>
#include<vector>

using namespace std;

int main()
{
   int t,i,e=0,c=0,r,k,n,x,ans=0,flag=0,j,m=0;
   vector<int> a,f;
   ifstream fin("C-small-attempt0.in");
   ofstream fout("output.in");
   //ofstream fout("output.in");
   fin>>t;
   //cout<<t<<"\n";
   while(t--)
   {
       m++;
       ans=0;
       e=0;c=0;
       a.clear();
       f.clear();
       fin>>r>>k>>n;
       for(i=0;i<n;i++)
       {
           fin>>x;
           a.push_back(x);
       }
       i=0;
       while(e!=r)
       {
           e++;
           c=0;
           f.clear();
           flag=0;
           while(c<=k)
           {
               if(i>=a.size()) break;
               c+=a[i];
               if(c>k) break;
               else
               {
                   f.push_back(a[i]);
                   ans+=a[i];
                   i++;
               }
           }
           for(j=0;j<f.size();j++)
               a.push_back(f[j]);
       }
       fout<<"Case #"<<m<<": "<<ans<<"\n";
   }
   return 0;
}

The code didn't suffice for the large test cases and I switched my attention to the first problem. After finding the logic of the problem it was a cake to write the code which even survived the large test cases and made our way to round-1 clear. Here's the code for problem-1 (Snapper Chain)

#include<iostream>
#include<fstream>
#include<math.h>

using namespace std;

int main()
{
   int t,n,k,c,s,m=0;
   ifstream fin("A-small-attempt1.in");
   ofstream fout("output1.in");
   fin>>t;
   while(t--)
   {
       m++;
       fin>>n>>k;
       c=pow(2,n)-1;
       if(k<c)
       {
           fout<<"Case #"<<m<<": "<<"OFF\n";
           continue;
       }
       else
       {
           s=c;
           while(s<k)
           {
               s+=(c+1);
           }
           //cout<<s<<" "<<k;
           if(s==k)
               fout<<"Case #"<<m<<": "<<"ON\n";
           else
               fout<<"Case #"<<m<<": "<<"OFF\n";
         
       }
   }
   return 0;
}

With 43 points I advanced to Round-1.

Round-1C

I was unable to code in round 1A and round 1B due to the sixth sem examination. Nevermind, I got my chance to survive in the last round. I successfully submitted the problem-1 (Rope Intranet) (both large and small datasets) for 22 pts. My code:

#include <iostream>
#include <fstream>
#include <algorithm>
#include <string>
#include <sstream>
#include <set>
#include <map>
#include <bitset>
#include <stack>
#include <queue>
#include <deque>
#include <vector>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <math.h>
#include <cctype>
#include <iterator>
#include <utility>

using namespace std;

int main()
{
   int m,t,ans,i,j,n,a,b;
   vector<int> b1,b2;
   ifstream fin("A-small-attempt0.in");
   ofstream fout("o.out");
   fin>>t;
   for(m=1;m<=t;m++)
   {
       ans=0;
       fin>>n;
       for(i=0;i<n;i++)
       {
           fin>>a>>b;
           b1.push_back(a);
           b2.push_back(b);
       }
       for(i=0;i<b1.size();i++)
       {
           for(j=0;j<b1.size();j++)
           {
               if(i==j) break;
               if((b1[i]<b1[j])&amp;&amp;(b2[i]>b2[j]))
                   ans++;
               else if((b1[i]>b1[j])&amp;&amp;(b2[i]<b2[j]))
                   ans++;
           }
       }
       b1.clear();
       b2.clear();
       fout<<"Case #"<<m<<": "<<ans<<"\n";
   }
}

Problem-2 (Load Testing) was really hard to understand and so was problem-3. After the competition ended I found myself placed at 1,950th position and losing the match by 950 ranks. Here's my complete performance.. GCJ-2010.
Khair, m happy but not satisfied. Will definitely improve the next time. Waiting for GCJ-2011 desperately..!! :)

* * * * *