Candy Corns,
By popular demand you can now view all submissions for practice problems which you have successfully solved. You’ve solved a problem in Java, you can now see how someone else solved it in C. Hopefully you will use this power for good, and learn from other members as well as assist those who are having trouble.

How else can we improve the site? What can we do, to help you become better programmers?

Let us know,
Amit

Cupcakes,
You’ve asked for it, we’ve done it. A big complaint people have had was the time limits were too strict for programming languages that didn’t start with a C. There are now variable time limits depending on the programming language you have used to submit your solution. The current time limits are as follows (as a multiplier to the time limit listed on the problem page):

• Java - 2X
• Python - 2X
• Ruby - 3X
• PHP - 3X
• Lisp - 3X
• All other languages - 1X

We will continue to tweak the exact multipliers  and will let you know if there are any other modifications.  Solutions will not be rejudged, you will be required to submit new solutions to see if your program now satisfies the time limit conditions.

Cheers,

The Chef

Hello people…. Today, we are going to make our first non-trivial program submission, and I am going to guide you through reading the problem statement through making a successful submission. I will also be touching the issue of “time limit” and “source limit” in this tutorial. However, I won’t be revealing too much in terms of code, so you will still have to do the hard work!

I’ll be using the Small Factorials problem as the program driving this tutorial.

---

Here is the problem statement:

You are asked to calculate factorials of some small positive integers.

Input:
An integer t, 1<=t<=100, denoting the number of test cases, followed by t lines, each containing a single integer n, 1<=n<=100.

Output:
For each integer n given at input, display a line with the value of n!

Example
Sample input:
4
1
2
5
3

Sample output:
1
2
120
6

Time limit: 1s

Source limit:2000B

---

The problem statement is fairly simple. We all recall that the factorial of a natural number n is the product of all numbers from 1 through n. Recursively, we can define the factorial of a natural number n as the product of n and factorial of (n-1). So, factorial(n) = n X factorial(n-1) and factorial(1) = 1.

You may ask why we haven’t considered factorial(0) = 1? Well, if you read the problem statement carefully, the least number that you will ever be asked to compute the factorial for is 1, so we don’t bother about any number less than 1.

As a first attempt, we would try and think that this program can be trivially coded up using integers or even long long integers, but a quick glance at the upper bound on the input number suggests otherwise. How do you figure out the number of digits in the factorial of 100? We can surely try and find a pessimistic approximation. Do you remember that the number of digits in the product x*y is either digits_in(x) + digits_in(y) or digits_in(x) + digits_in(y) - 1. So let’s try and find out the number of digits for 100!.

Pessimistically, it must be:

digits_in(100) + digits_in(99!), which is:

3 + digits_in(99) + digits_in(98!)

…. and so on….

which is 3+2*90+1*9 = 192

so, in the worst case, we have 192 digits in the result.

This itself should prompt us to not use integers because it will overflow even the biggest integral data type(64-bit) that we have.

The next thing we may think of is to use floating point numbers, but that too can be ignored for the same reasons.

Now that we find ourselves in a fix, we will try and resort to creating our own big integer class. This is where selection of programming language comes into play. Usually, C/C++ is the programming language of choice because of it’s speed and wide adoption. However, now is a good time to look at languages like Java, Python, Caml, etc…. which have built-in support for indefinitely long integral values. So, if you know any of those languages, this problem should be a breeze to solve! And CodeChef allows you to choose one of 30+ different programming languages for coding your solution in!

Once you have coded up a solution in your language of choice and submit it, you find that it says “Wrong Answer”. You wonder “How could that happen” and try to figure out where to start debugging. You enter integers 4, 5, 6 and get the answers as 24, 120, and 720 respectively which are correct. Then you enter the number 50 and you get a really huge number. However, you wonder to yourself “How do I know if this is the correct value of 50!?”. You think for a while and then let it go. Here is where you should think some more.

As a first level of sanity checking, the output should have at least 5 zeros at the end because 50! involves multiplying 10, 20, 30, 40 and 50. If not, you can start debugging. However, even better would be if you knew the exact number of zeros to expect at the end of the output.

Here is how you can find that out. You need to know that you can get a zero at the end of the product of 2 numbers if and only if 10 is a factor of the number. This is possible only if 2 and 5 both are factors of the product.

You can write a simple program to count the number of times a factor of 5 or 2 occurs in all the numbers from 1 to 50, and the number of zeros to expect is the least of the two values. This should validate(to a great extent) your solution’s output.(This co-incidentally is the solution to another problem in the easy set).

What does the “Time limit” mean? It means that the program that you write should be able to compute the factorial of 100 numbers, each of which are <=100 in 1 second.

If I was solving this problem and I saw the constraints mentioned, I would just pre-compute all the values for factorials of numbers from 1 to 100 and store it as strings in my program’s code, and the display the required string depending upon the input. However, to thwart lazy coders like me, the problem setter has set a Code size limit which is “Source limit”. So your program’s source code must be at most 2000 Bytes.

We have already computed the largest result as having at most 192 digits. So, on the average, you can expect each result as having at most 96 digits. If I wanted to store all the values, I would need at least 96*100 bytes of storage, which is 9600 bytes, which exceeds the source limit. This makes it fairly impossible for me to hard-code the answers in the program.

CodeCheffers,
By popular demand we have added a trivial sample question: Life, the Universe, and Everything.   Solutions in 25 programming languages can be found in our forums.

Additionally we’ve added a few new, easy practice problems:

Enormous Input Test
Sums in a Triangle
Turbo Sort
The Way to a Friends House Is Never Too Long

Finally we moved some of the more difficult of the easy problems to medium.  As always your feedback appreciated.

There are now 23 practice problems available! The problems range in degree of difficulty, we’ve bucketed them in easy, medium and hard. The easiest problem is the ATM. If you’re new to online coding competitions, why don’t you give that a shot first? We will continue to add problems regularly and send out updates through the blog. If you have any questions, check out our forums.