CodeChef Tutorial: Your First Non-Trivial Problem

3 min read

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.

February Long Challenge Surprise

The February Long Challenge will start soon and with it the countdown to the Chef’s 11th Birthday! As a pre-birthday present, the Chef has...
shwetali1602
2 min read

[Live Updates] ACM ICPC 2019-20 Gwalior/Pune Regional

Welcome to our coverage of the 2nd Indian regional this year, being held in Gwalior and Pune. The contest shall begin shortly. Link to...
teenage_witch
1 min read

CodeChef introduces a brand new discussion forum

In our recent annual recap, we talked about what a huge year this has been for us. Not only did we embark on a...
teenage_witch
1 min read

29 Replies to “CodeChef Tutorial: Your First Non-Trivial Problem”

  1. You are right about all this but what about someone who has done it in C++ only. Since C++ won’t allow you to go beyond a certain value, you can’t help it. Many use 32 bit system so max value one can use is around 2700000000. Can you suggest something about this ?

  2. You are right about all this but what about someone who has done it in C++ only. Since C++ won’t allow you to go beyond a certain value, you can’t help it. Many use 32 bit system so max value one can use is around 2700000000. Can you suggest something about this ?

  3. Man Exactly. I am getting freaky like anything while doing online programming. Similar thing happens to me while doing programming at spoj.pl and projecteuler.com

    Everytime I try write a code in C++ using simple turbo, it works fine, and gives the required result. But that program fails when a large input is given.

    HELP ME! I AM A C++ CODER…

    please moderator ji do reply.

  4. Man Exactly. I am getting freaky like anything while doing online programming. Similar thing happens to me while doing programming at spoj.pl and projecteuler.com

    Everytime I try write a code in C++ using simple turbo, it works fine, and gives the required result. But that program fails when a large input is given.

    HELP ME! I AM A C++ CODER…

    please moderator ji do reply.

  5. ou are right about all this but what about someone who has done it in C++ only. Since C++ won’t allow you to go beyond a certain value, you can’t help it. Many use 32 bit system so max value one can use is around 2700000000. Can you suggest something about this ?

    I also want the answer to Alok’s problem. I have the same problem. Please help.

  6. ou are right about all this but what about someone who has done it in C++ only. Since C++ won’t allow you to go beyond a certain value, you can’t help it. Many use 32 bit system so max value one can use is around 2700000000. Can you suggest something about this ?

    I also want the answer to Alok’s problem. I have the same problem. Please help.

  7. I have implemented this algorithm to find the no. of zeros in the factorial of a no. by simply finding the no. of factors of 5 and 2 and then printing the min of them. But the answer is coming out to be wrong. As in 60 there are 14 zeros and this algorithm gives the output 12. what should i do ?

  8. I have implemented this algorithm to find the no. of zeros in the factorial of a no. by simply finding the no. of factors of 5 and 2 and then printing the min of them. But the answer is coming out to be wrong. As in 60 there are 14 zeros and this algorithm gives the output 12. what should i do ?

  9. It would be much easier, if instead of stdin and stdout, you would allow the programs to read through file and then write to a file. This thing bugs me off. I want to know if
    (1) We need to take one input line at a time, process it and show the solution? OR
    (2) We need to accept all input lines at one go, and then process and show the results in one go

  10. It would be much easier, if instead of stdin and stdout, you would allow the programs to read through file and then write to a file. This thing bugs me off. I want to know if
    (1) We need to take one input line at a time, process it and show the solution? OR
    (2) We need to accept all input lines at one go, and then process and show the results in one go

  11. @Pranav:
    Do it either way. All you need to do is make sure your output is FORMATTED properly. It doesn’t matter if the output comes inbetween your program while running.

  12. @Pranav:
    Do it either way. All you need to do is make sure your output is FORMATTED properly. It doesn’t matter if the output comes inbetween your program while running.

  13. I am getting compiling error..
    I code in Java. i exactly wanted to know what is the difference between java and JAR.
    More over i use netbeans as my IDE and hence want to know what should I do to rectify and correct the Compilation error as the program works fine at my home PC.
    Please help me with this.
    -Thank u.

  14. I am getting compiling error..
    I code in Java. i exactly wanted to know what is the difference between java and JAR.
    More over i use netbeans as my IDE and hence want to know what should I do to rectify and correct the Compilation error as the program works fine at my home PC.
    Please help me with this.
    -Thank u.

Leave a Reply to Dhruv Cancel reply