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..!! :)

* * * * *

Google Code Jam 2009

This was the first time I registered for Google Code Jam. Researching about this great event I came to know that it gives way to free use of languages. Google allows its participants to code in any language they wish to. Starting from c, c++, java, batch files to php, perl, brainf*ck and all.

It was the qualification round in which I scratched my 'hairless' head throughout the day. The round consisted of three questions. One had to submit an output file of solution of test cases. Each question consisted of two test cases small and large. 4 minutes of time was given to a participant to upload his source code file and the output file in small test cases. Time was increased to 8 mins in case of large test cases. It was necessary to solve at least one small test case and one large test case of any question to qualify for next round. I was able to solve a small one.. :)

The question I solved was called "Alien Language". One can easily 'google' the whole question. I m giving the source code which I submitted :

using namespace std;
int change(string strConvert)
{
int intReturn;
intReturn = atoi(strConvert.c_str());
return(intReturn);
}

void main()
{
ifstream myfile("g1.txt");
ofstream opens("g2.txt");
string line;
int cases=0;
char words[800][800],letters[800][800],answers[800][800];
int L,D,N,r=0,c=0,f=0,m;
getline(myfile,line,' ');
L=change(line);
getline(myfile,line,' ');
D=change(line);
getline(myfile,line,'\n');
N=change(line);
for(long int i=0;i++)
{
getline(myfile,line,'\n');
for(int j=0;j++)
{
words[i][j]=line[j];
}
words[i][L]='\0';
}
for(int q=0;q++)
{
cases=0;
r=0;
getline(myfile,line,'\n');
f=0;
m=line.size();
while(f!=m)
{
if(line[f]=='(')
{
while(line[f]!=')')
{
f++;
if(line[f]!=')')
{
letters[r][c]=line[f];
c++;
}
}
letters[r][c]=NULL;
f++;
r++;
c=0;
}
else
{
letters[r][c++]=line[f];
letters[r][c]=NULL;
r++;
c=0;
f++;
}
}
for(long int s=0;s++)
{
f=0;
for(long int k=0;k+)
{
for(long int a=0;a++)
{
if(words[s][k]==letters[k][a])
{
f++;
break;
}
}
}
if(f==L)
cases++;
}
opens<<"Case #"<<<": "<<<"\n";

}
getch();

}

Explanation of code:

What I did in the program is that I took each word of language into a double dimension array called 'words'. Each test case was then bifercated into letters in another double dimension array called 'letters'. The first letter in words was then regularly checked in the different letters of each test case. The moment it matched the loop got broken with an increment of a flag called 'f'. The moment flag became equal to length of word it was sure that the given combination exists, hence, the case variable gets incremented which is ultimately our answer and gets written in the output file.

The only problem that came with this solution was during the execution of large test case. It would have been easily implemented through vectors but lack of time compelled me to quit upon it. Actually, due to continuous memory allocation sometimes due to large datasets, the values get written on read only part of memory which generates errors.

So, I settled with a 10 point mark.. BTW my first experience with Google Code Jam was awesome..!!

* * * * *