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

* * * * *

SCALA programming language

While coding in SPOJ. I came across a new programming language named SCALA. I searched a hell lot of things about the language.

Scala goes out of it's way to make sure you don't need to program in a functional style. This is the main criticism of Scala from functional folks, as a matter of fact: some do not consider a language functional unless it forces the programmer to write in functional style.
Scala already introduces some nice features, comparable to some stuff that's present in C++ but not Java, though they work in different fashion. In that respect, once you realize what such features are for and relate them to C++ stuff, you'll be much ahead of Java programmers, as you'll already know what to do with them.

Some of the downsides of Scala are not related at all to the relative youth of the language. After all, Scala, has about 5 years of age, and Java was very different 5 years into its own lifespan.
In particular, because Scala does not have the backing of an enterprise which considers it a strategic priority, so the support resources for it are rather lacking. For example:

* Lack of extensive tutorials
* Inferior quality of the documentation
* Non-existing localization of documentation
* Native libraries (Scala uses Java or .Net libraries as base for their own)

* * * * *

Optimization

During coding, what we need to keep in our minds is optimize the code. The direct code which hits our brain at the first instance is generally not that optimized. If given a large test case to examine the code, it fails to complete the execution in time. I came to know about this while playing online a coding event in which besides code to be right one's code should run in an asked period of time. For this we need to optimize our code a great extent.
I was asked to print all the prime numbers between given two numbers. The first code that comes to our mind is to run a loop and find all the prime numbers by dividing each number with every other number. Mind you, this takes a hell lot of time. One can optimize the code easily by discluding the numbers that get divided by 2,3,5. This takes away numbers out from the loop that prevent us from checking them. The time limit set hence becomes a little reachable.
The second thing is logic. One can even look at the problem at different angle. You can yourself Google and find that there are many other good methods of finding a prime number. One method needs the loop to run only for (n)^(1/2) times. This also reduces the time a great deal.

CODE IT.. OPTIMIZE IT!!

* * * * *

Back up your Gmail account

Gmail doesn't have to go down globally for our email access to be cut off—our internet could go down, or our account could even be disabled. Whatever the case, it's a good idea to have a backup plan just in case the worst should happen.

They've got us covered with a number of methods for backing up our Gmail, starting with the really obvious solution of just using Thunderbird to back up our email with POP access, but we can backup our email with Fetchmail on Windows, Getmail on Linux, the standalone Gmail Backup tool, or even use Google Groups to backup your Gmail account.

So, don't think much.. just get urself backed up!!

* * * * *

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

* * * * *