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

* * * * *

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

* * * * *