It’s been just over a month since we’ve launched and we’re really excited about the way things are going.  We now have over a thousand registered users and accept hundreds of code submissions a day.  The response has been great, but we’re not done.   As a way to continue to challenge, engage and give back to the developer community, we’re pumped to announced a few new initiatives.

CodeChef Campus Chapters – Are you a student interested in setting up a CodeChef Chapter on your campus?  Each month we’ll send you optimal solutions to specific contest problems, tips & tools to become better software developers and (of course) some awesome CodeChef merchandise (everyone looks cool in chef’s hat).

Blogger Community Program – Are you a blogger interested in spreading the word about CodeChef?  We got what you need: exclusive access to content, press passes and more.

User Group Outreach Program – Are you part of a user group which is enthusiastic about programming?  We’ll give you a place for your meetings, and a chance for your users to network and gain recognition.

First contest starts Sunday, keep practicing…

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.

This post will try and introduce newcomers to the first and most basic thing they need to learn before submitting programs — How to properly accept Input and print Output (I/O). I’ll start off with a few guidelines and then conclude with an example from the CodeChef site.

For all the questions on our site, the input will be given to you from standard input (stdin for C users) and the result is expected on standard output (stdout for C users). This is the same as writing a program that accepts input from the keyboard and displays the results on the screen. I’m sure most of you have been programming that way already. However, a major difference is that you don’t need to prompt the user for input, so stuff like:

“Please enter your name: ”

are a big NO NO! You need to assume that the user entering the data at the other end knows what to enter and when to enter it. Similarly, while displaying the results, you need to display it in the exact format as is specified in the problem statement.

For figuring out the format in which data will be entered (given to you) and how you should display the results, you need to refer to the “Input” and “Output” section of the problem statement respectively. Please make sure that you are following the output specification to the decimal point. If you have one character out of place, your submission will be marked as incorrect

After reading the problem statement, you will be given a sample “Input” and the resulting expected “Output” your program should submit. Typically, you will be asked to run your program against multiple test cases. The number of test cases and the format of each test case will be clearly mentioned in the problem statement’s “Input” section. More often than not, you will be required to display the result for each test case, so you will have as many results displayed as there are test cases.

Why so many test cases?

You must have studied about the different types of tests that you can run your program against in school. Some of them are:

1. Boundary value testing
2. Negative testing
3. Stress testing
4. and so on….

Now, each of these have a specific purpose, so the problem setter has kept many different types of tests to test the correctness and performance of your program for different types of inputs.

Let us move on to a specific example to see what is happening.

The problem we shall be tacking here is: Life, the Universe, and Everything

The problem statement:

Your program is to use the brute-force approach in order to find the Answer to Life, the Universe, and Everything. More precisely… rewrite small numbers from input to output. Stop processing input after reading in the number 42. All numbers at input are integers of one or two digits.

Input:

A list of integers separated by a new line.

Output:

All the integers before the integer ’42′.

Sample Input:
1
2
88
42
99

Sample Output:

1
2
88

Here, the constraint on the input we have is that any input number n will be such that (0 <= n < 100).

The problem statement is pretty straightforward, but for this toy program, the problem setter may construct test cases where:

1. The 1st number is 42
2. The last number if 42
3. There are 10000000 numbers before 42

The first 2 tests are boundary value tests, and the 3^rd one is a performance test. Generally these problems have a time limit associated with them. You are required to solve the problem with the given constraints in the given time limit. This time limit is chosen such that a good solution in any language would be accepted.If you are stuck, the answers to this problem, in over 25 programming languages can be found in our forums.

You can now go ahead and try out the problems in the easy set. If you have problems, post a message in the Forums.

Enjoy!

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.

Tatertots,
We’re pleased to announce the prizes for our first contest. Lucky winners will get an Asus Eee Netbook (probably the coolest thing we’ve ever seen), iPod touch (for your jailbreaking and modding pleasure), or a Nokia 5800 (you know you want it). We’re also giving away a ton of CodeChef t-shirts.

If you have any ideas for prizes for the next contest, let us know at prizes[at]codechef.com

Hey everyone, we’ve recently made some updates to the site. On each problem page (for example Small Factorials), you will now see a leaderboard of best solutions for that problem. For now, only time to execute is used to determine ranking (though we might expand this in the near future), if two people submitted solutions with identical times, then whoever submitted first will appear higher on the leader board. Also on the problem page, recent activity only shows activity related to that problem.

We have some more fun stuff in the works. We’re almost done with our ranking system – soon you’ll be able to work your way up from a dishwasher to head chef. Enjoy!

Congratulations to our TechFest Challenge Winner – Hrishikesh Rajesh Terdalkar from Chennai Mathematical Instiute. He is the proud (soon-to-be) owner of a new Nintendo Wii. Thank you to everyone who participated. We’ll be giving out more great prizes at our first contest March 1st.