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

* * * * *

cmath v/s math.h

Here's a problem with pow() function in cmath and math.h:

With gcc set up, math.h just contains the the usual C function pow(double, double) - so all the functions work because with pow(int, int) both ints get promoted to double by compiler and all is OK.
cmath in more than a wrapper for math.h. First it includes math.h and then undefines a whole lot of stuff that math.h defined, and substitutes the c++ versions.
This includes the pow function declaration.
As the c++ overloaded functions (same as any other c++ compiler), you will get the ambiguity problem - when using pow(int, int).

P.S. - The ambiguity occurs with pow(int, int) because integers can be promoted to floats or doubles, which means that pow(int, int) can fit the so overloaded c++ pow function - so the compiler gets confused.

* * * * *

My way of writing a Quine

Here I m presenting a Quine written by me few days before. A Quine is a program that prints its own source code. In my source code user has an option of printing the source code n number of times.

Here is the code written in c:

#include < stdio.h >
int main()
{
 int n;
 char c;
 FILE *f;
 f=fopen(__FILE__,"r");
 scanf("%d",&n);
 while(n--)
 {
  while((c=getc(f))!=EOF)
  putchar(c);
  fseek(f,0,0);
 }
 return 0;
}

Here is the code written in c++:

#include <fstream>
#include<iostream>
#include <cstdio>
using namespace std;
int main()
{
    int n;
    string a;
    cin>>n;
    while(n--)
    {
        ifstream fin(__FILE__);
        while(!fin.eof())
        {
             getline(fin,a,'\n');
             cout<<a><<"\n";           
                }      
           }      
     return 0;
 }

* * * * *

How to handle very large test cases in c++

Most of us come across some c++ problems where we are asked to get some simple calculations done. For example: we can get a problem of subtracting 1 from a 100 digit number. Now, subtracting one is not a big problem for us but the problem is '100 digit number'.

None of the datatype has capacity to store such a large number. Stop thinking about unsigned long long.. even it cant..!! So, here's a short solution to this cute problemo..

We can take the input as a string and process each of its elements as in elementary mathematics i.e. if last digit is'nt 0 then reduce it by 1(dont forget it to convert to int and then back to string).. if last digit is zero then make it nine and move back to the adjacent digit following the same procedure. Simple :)

Here's the source code..

#include
using namespace std;
int main()
{
int i,t=40;
string z;
cin>>z;
i=z.size()-1;
do
{
if(z[i]!='0')
{
z[i]=int(z[i])-1;
break;
}
z[i--]=57;

}while(i>=0);

Then print the string a.

The only problem comes when we give input as 10, 100, 1000, 10000 ... the answer comes out as 09, 099, 0999, 09999... instead of normal numbers such as.. 9, 99, 999, 9999... I have resolved this problem for myself.. I'll not upload the source.. try it out yourself..!! ;)

* * * * *

Getting started with TopCoder..

After successfully coding the first time in Topcoder, I really feel greatful in sharing my experience with all. Simply, it was great. Got to learn a lot of new things. I have started it too late but being in UPTU and that too in a college where seniors are not that into coding, it was still very early.. ;)

So, m writing this post to acquaint my mates with the TopCoder Competitions. What I m goin to discuss is all about the algorithm competitions.
Top Coder is a programming arena where you are given a set of problems and you have to solve them (in your preferred language) in a given amount of time. There are some simple steps to follow before starting with the coding competition:

• Goto Topcoder site and get yourself registered.
• Now when you are registered, download the Topcoder arena. You will need Java to be installed in your system for making the applet run.
• Get yourself an editor(I use KawigiEdit). The editor helps in generating the code required for the competition. If you need help to install it.. read this.
• Start the contest application and start navigating. There are practice rooms where you can practice the earlier SRM's(single round matches).
  

SRM are the single round matches which are organized twice every month. You are given three problems to solve. What you need to do is to generate the code using KawigiEdit and simply put your logic in the function provided.
The important point about TopCoder is that you don't use the main() method in your code. All your logic is dumped inside a function and you have to return your answer instead of printing it.
The several phases of the competition are:

• Coding Phase: During this phase you are given 75mins of time to solve as many problems as you can. What you need to do is to write your code, compile it and after rigourous testing on test cases provided and some of your own test cases, "submit" it.
• Intermission: 5mins intermission.. I hear a song usually.. :)
• Challenge Phase: During this phase in 20mins time any of the room members can see your code or you can see theirs. If anyone finds anything wrong with anyone's code, he can simply challenge it. If he succeeds the submitted problem will be discarded and points will fall back to 0.00
• System Testing Phase: After the challenge phase comes System Testing Phase. This takes a fare bit of time. After near about 20mins you can goto tools and room summary for checking whether your code passed the System Testing or not.
  

After about 2 hrs of play the result is out..!! If you see your name coloured (Green,Blue,Yellow,Red), feel like a champ. If you are Grey, you need to practice more and more. The colors listed above are in hierarchical order.. i mean Red is the highest pointer(2200+) whereas grey is the lowest(001-899).

Being associated with IEEE, TopCoder is a good platform for being recruited. Moreover, it hons your programming skills, giving your career a boost.

You can watch your entire TopCoder profile by just entering your username in the handle.
I m listing some of the TopCoder handles that will inspire you a lot..
Some foreigners:
ACRUSH
petr

Some Indians:
konqueror
innocentboy
vijay03
shalinmangar (from JSS.. a thing to feel proud of..)

Here's my handle.. its not that good.. I'll improve it further.. m sure..
vaibhavpandey

* * * * *

SIGSEGV error in c++ programs

While solving a question TOANDFRO in spoj I was introduced to the SIGSEGV (segmentation fault) error. The very first thing, as I often do, I googled the error. The forums I visited and info I got simply did'nt tell me what exactly went wrong with my code. So, after a "deep-deep" analysis I m here to provide my readers with the solution to such an error.

There are various causes of segmentation faults, but fundamentally, you are accessing memory incorrectly. This could be caused by dereferencing a null pointer, or by trying to modify read only memory, or by using a pointer to somewhere that is not mapped into the memory space of your process.
A segfault basically means you did something bad with pointers. This is probably a segfault:

char *c = NULL;
...
*c; // dereferencing a NULL pointer

Or this:

char *c = "Hello";
...
c[10] = 'z'; // out of bounds, or in this case, writing into read-only memory

Or maybe this:

char *c = new char[10];
...
delete [] c;
...
c[2] = 'z'; // accessing freed memory

* * * * *

Getting started with SPOJ (Sphere Online Judge)

After successfully getting involved in SPOJ I think I must give a little idea of it to others too. SPOJ is an online coding website for practicing ACM-ICPC style problems.
You need to join this website if you are interested in coding and have a thirst to solve new problems otherwise you can sit back and relax hearing your music stuff.. :p

To start with you can register for SPOJ here.
After getting registered you can see number of problems. Right now there are around 4K+ problems at SPOJ. For submitting a problem in whichever language you desire you can click submit and submit your file or directly the source code. One of the best things about online judges is their instant feedback. You dont have to wait for your program to get judged! The judge results are:

• Accepted – The output from your program perfectly matched the required output. This problem is then added to your list of accepted problems.
• Time Limit Exceeded – It means your program took too long to execute. Try optimizing your program and check for accidental infinite loops.
• Wrong Answer – Your program ran on time, but it did not produce the required output.
• Compile Error -Your program had some syntax error. For these errors, click on the text “Compile Error” in the judge result. It`ll take you a page which will list the compile errors and their line numbers in your program. The compilation error can also be sent to you as mail.
• Runtime Error – This is usually accompanied by a code like SIGSEV. It can happen due to a lot of reasons, but the two most common are using too much memory ( you can use around 6000*6000*4 bytes of memory ) and not remembering to use int main() and return 0 in your programs. (NZEC error).

Your ranking in SPOJ arena is dynamic. More the number of users who solve the problem you'v solved lesser will be points gained. The points you gain in SPOJ come with the formula:

points= 80/(40+users successfully solved the problem)

So, more the difficult question you solve more points you get and higher is your rank. Even your institute gets ranked on your points. Check your institute's rank here.

Here is my SPOJ handle.. vaibhav_pandey

Start coding now!!!

* * * * *

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

* * * * *

Cool query 'bout pointers

While studying 'bout pointers I came about a cool phenomenon. Plzz don't laugh if its a but obvious thing for you. You might be a better coder than me for sure. I figured it out after a number of trials so I can't stop myself sharing it with everyone.

My question is.. Whats the difference between two statements..

int a=1;
int *p;
*p=a;//statement 1

AND

int a=1;
int *p;
p=&a;//statement 2

I played with number of printf's to come out with a simple answer. I again warn you if its a but obvious thing plzz do ignore it but it was a beautiful discovery for me though.

p=&a : in this statement, as we all know, the address of variable 'a' gets stored in pointer p and we say that pointer p points towards the variable a.

*p=a : (value of p is equal to a) in this statement, "as now I know", a new address is designated as value 1 and the pointer points to that address rather than pointing towards a. In simple words the address stored in p is not the address of a.

try two statements with..
printf("%u" "%u",p,&a);
In first you will find same address and different in the second.

* * * * *