Each month we plan on taking one or two problems and describing various approaches to solve them.  Since our first contest has just ended, I am going to describe the algorithm used to solve: http://www.codechef.com/MARCH09/problems/A2/

This problem is pretty simple, and there are two approaches to solving it.  If you read the problem carefully, you will notice that you need to determine if the beanstalk (or tree) is valid.  This is possible only when:

Approach-1 (Lowest to highest level):

1.  The number of leaves on every level is at most the number of stems brought over from the previous level.

2.  The tree will stop growing once there are no more stems.  At the last level the number of stems is zero (they should all be leaves).

Approach-2 (Highest to lowest level):

1.  The number of leaves at the last level is an even number (because the number of stems at any level will be twice the number of stems brought over from the previous level AND all stems at the last level will be converted to leaves).

2.  If the tree is valid, at any level you can add the number of leaves plus the number of stems and divide by 2 to get an integer representing the number of stems brought over from the previous level.

For example (for the input 0,0,1,3,6) :

At level N (last level): For a valid tree, the number of leaves is even.  In this case there are 6 leaves, the tree is valid so far.

At level N-1: The number of stems at this level will be 1/2 of 6 = 3.  For a valid tree, the number of leaves at this level must be an odd number so that the sum of stems and leaves is even.  In this case the number of leaves is 3, so the sum of stems (3) and leaves (3) is even (6) – the tree is valid so far.

At level N-2: The number of stems at this level will be 1/2 of 6 = 3.  For a valid tree, the number of leaves at this level must be an odd number so that the sum of stems and leaves is even.  In this case the number of leaves is 1, so the sum of stems (3) and leaves (1) is even (4) – the tree is valid so far.

At level N-3: The number of stems at this level will be 1/2 of 4 = 2.  And so on…

3.  To check the validity of your solution, ensure that the method above yields one stem in the first level.

Obviously, the first approach is much easier to follow, and also does not require you to store the entire contents of the input before you start processing it.  This is what most of the contestants have done.

However, both solutions have the same complexity of O(n) and are valid and acceptable solutions for this contest.

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!