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

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:

- Boundary value testing
- Negative testing
- Stress testing
- 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:

- The 1st number is 42
- The last number if 42
- 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!

- Here’s why there was a delay in updating the March contests’ ratings
- SnackDown 2017 is here and this time it is truly Open!
- A Star Studded Rating System
- New Goodies, New Categories & New Prizes Every Contest
- CodeChef’s 8, mate!

- About (12)
- ACM ICPC (20)
- Announcement (284)
- Campus Chapters (7)
- College Contests (9)
- Contests (264)
- Events (50)
- FAQ (1)
- Features (49)
- Interviews (18)
- Languages (1)
- Meetup (4)
- Open Source (1)
- Practice Problems (8)
- Prizes (20)
- Problems (6)
- ProblemSetting (1)
- Programmer of the Month (34)
- Schools (9)
- Tech Talks (23)
- Tutorials (25)
- Uncategorized (1)
- Volunteers (2)
- Winners (119)

- abhinav vinci on The new Karma system
- Ashu on A Star Studded Rating System
- Hemant Mangla on New Goodies, New Categories & New Prizes Every Contest
- Protap Ghose on New Goodies, New Categories & New Prizes Every Contest
- Shivam Fialok on New Goodies, New Categories & New Prizes Every Contest

- March 2017
- February 2017
- January 2017
- December 2016
- November 2016
- October 2016
- September 2016
- August 2016
- July 2016
- June 2016
- May 2016
- April 2016
- March 2016
- February 2016
- January 2016
- December 2015
- November 2015
- October 2015
- September 2015
- August 2015
- July 2015
- June 2015
- May 2015
- April 2015
- March 2015
- February 2015
- January 2015
- December 2014
- November 2014
- September 2014
- August 2014
- July 2014
- June 2014
- May 2014
- April 2014
- March 2014
- January 2014
- December 2013
- November 2013
- October 2013
- September 2013
- August 2013
- July 2013
- June 2013
- May 2013
- April 2013
- March 2013
- February 2013
- January 2013
- December 2012
- October 2012
- September 2012
- August 2012
- July 2012
- June 2012
- May 2012
- April 2012
- March 2012
- February 2012
- January 2012
- December 2011
- November 2011
- October 2011
- September 2011
- August 2011
- July 2011
- June 2011
- May 2011
- April 2011
- March 2011
- February 2011
- January 2011
- December 2010
- November 2010
- October 2010
- September 2010
- August 2010
- July 2010
- June 2010
- May 2010
- April 2010
- March 2010
- February 2010
- January 2010
- December 2009
- November 2009
- October 2009
- September 2009
- August 2009
- July 2009
- June 2009
- May 2009
- April 2009
- March 2009
- February 2009
- January 2009

© 2009, Directi Group. All Rights Reserved.