Crème brûlées,
Based on the feedback we received from the July contest we have slightly modified the rules for the August Challenge. This time around we will not be rejudging submissions with new test data. To prevent people from precomputing solutions we will limit the number of submissions to the challenge problem to 20 per calendar day. We will reevaluate after the competition to see if this method has the intended results.

We would like to mention once and hopefully for the last time the guidelines for disqualification:

• Any form of collaboration including (but not limited to) discussing problems, asking someone to review your code, asking for output for a set of inputs, posting questions on other forums, etc…
• Hardcoding output for a specific set of inputs. It is ok to run tests to verify the size of inputs and some min/max conditions to help you design your algorithms. But hardcoding output for a specific set of inputs is not allowed.

We reserve the right to ban users based on suspicion of cheating.

We are also happy to announce a weekend long competition at the end of August. Details on this will be announced soon. We are also planning a team based competition for September, this may be judged in the style of ACM-ICPC competitions (time-based, penalities for incorrect submissions). We’ll let you know.

Best of luck!

Cheers,
Cheffy

No surprises with this announcement, right? Anshuman has been a force to reckon with on CodeChef since the very beginning. He’s won the March, April and May challenge back to back and because of his excellent performance, he even interned with us at Directi during the summer (of course, the ulterior motive was to stop him from winning through June and July )

Without further ado, here’s Anshuman, our Programmer of the Month for August 2009!

Name: Anshuman Singh
Age: 21
Institute: IIIT, Hyderabad
Userid: anshuman_singh
Twitter ID: anshuman26

Brief introduction about yourself (under 140 characters):
A pretty normal guy with high expectations from life.

How/When did you start programming?
I started programming when I was in high school but wasn’t very serious about it till my first year in college. That was the time when I was influenced to some extent by my seniors and managed to get a little guidance from them. From then on, it gradually changed from a mere interest to a passion.

What do you do when you’re not programming?
I’d definitely be watching a movie or some sitcom. I am a big movie buff. I frequently (on weekends or on some occasion skipping classes) take a day out watching movies/show on a full trot. I, along with my friends, have planned numerous night outs where we continuously watch movies and then sleep throughout the day.

What do you like most about CodeChef?
Prizes. To be very honest, almost everything. The problem set is nice along with the organization. I am really thankful to the CodeChef team for having something like this and let us be a part of it.

How many hours a day do you program?
Depends. It varies from 7-8 hours of programming to nothing at all. The numbers increase when preparing for ICPC or something similar.

What’s your favourite book and why?
I am not much of a book guy. Course books are already a lot to contend with . Anyhow, I did enjoy reading Harry Potter (All volumes).

If you could eat dinner with any famous person (past or present), who would it be and what dish would you have?
For Dinner, Megan Fox definitely . Donald Knuth is someone whom I would like to meet personally. Dish: Anything works.

What are your plans for the future?
Not sure at all. I will probably go for higher studies to work on something challenging.

Blueberries,
Last weekend we held our first CodeChef meetup. As promised below are the videos. First Bhavin gave an introduction to CodeChef and an overview of our goals:

At the end of the meetup, Varun gave a session on advanced data structures:

Stay tuned for updates on the next meetup.
Cheers,
Chef

For the past few weeks we have been getting questions from people interested in setting problems for our contests. Here is a quick FAQ as to what you need to do before sending us the problems and if/how your problems will be used in our contests. Now, at present, we have 2 types of problems in our contest. The first category is the exact algorithm contest problems which have either a wrong or a correct answer. The other type is the challenge problem that we have in each contest. This problem is such that it does not have a deterministic solution. Which means that there is no algorithm that will give an optimal answer for the problem. Submitting problems for both these categories is slightly different.

Exact Algorithm Problems :

Q. What kind of problems are you looking for in the Exact Algorithm Problems category?
A. We are looking for problems which are not standard ones or ones which are not easily ‘googleable’. The problem should be such that it induces the solver to spend time to think of a solution to the problem rather than search for it online.

Q. What files do I need to submit along with the problem?
A. You need to submit the following files :
1) The problem story line. This is the main body of the problem that the participant will read. This should not be ambiguous and should be clear and interesting. It should specify the input format, the output format as well as the constraints on the input and if any, on the output.
2) The solution in a programming language of your choice. This solution should be such that it takes in the input data in the specified format and produces the correct output according to the output format.
3) The test input data. This input data should have all the corner cases covered and should have a few randomly generated test cases too. If there are multiple input files, label them as 0.in, 1.in, 2.in and so on and place all of them in a folder called ‘input’.
4) The output test data. This is the output data corresponding to the input data mentioned previously. The expected output for 0.in should be placed in 0.out, for 1.in should be in 1.out and so on. Place all these files in a folder called ‘output’.
5) A small write-up of the approach taken. You need to give us a small write-up about the approach taken to solve the problem.

Q. How do I send you all the files?
A. Place all the files and folders in another folder named whatever you wish to call the problem. Archive it using an archiver, preferably in .zip or .tar.gz format. Send this archived file as an attachment along with your contact information to admin@codechef.com

Q. How many problems can I submit?
A. You can submit as many problems as you like. If we like a problem, we will use it in one of our contests. If we decide to use your problem in our contest, you would not be eligible to participate in that month’s contest. You might want to send us a set of 4-5 problems so that we might use a higher number of problems in the same contest.

Q. How much do I get paid for submitting the problem?
A. There is no payment for submitting a problem. However, if we decide to use your problem in our contest, we will compensate you accordingly. The compensation would depend on the quality of problems you have submitted. An easy problem would have less compensation compared to a hard one.

Challenge Problems :

There are a couple of things different for challenge problems.

Q. What kind of problems are you looking for in the Challenge Problem category?
A. We are again looking for problems which are not very highly researched. The approaches for such problems should not be available online easily. The problems should not have a polynomial time solution. The challenge problem has a scoring mechanism based on certain parameters. This scoring mechanism needs to be explained properly in the problem statement submitted by you. Also, you need to specify whether the optimal solution minimizes this score or maximizes this score.

Q. What files do I need to submit along with the problem?
A. You need to submit the following files :
1) The problem story line. This is the same as the earlier category. Along with the constraints and other things, you need to mention how the problem is scored and also whether the optimal approach should maximize or minimize the score.
2) The input test data. This should have random and large test cases. Place all the input files in a folder called ‘input’.
3) A program in a programming language of your choice that reads the output and returns the score for that output based on the scoring parameters.
4) A write-up specifying why the problem does not have a polynomial time solution. Some links or research papers pointing to this would be appreciated.

Twinkies,
This past weekend we had our first CodeChef meetup! Against all odds, we were able to host it in our new office, and despite the weather, about 60 people showed up.

We really enjoyed meeting some of you in person. Bhavin started off with the inspiration behind CodeChef and our goals:

Next we asked CodeCheffers to go around and learn more about each other. Everyone received a piece of paper with statements like: Speaks 3 languages, Loves South Indian Movies, Is proficient in Erlang, Has solved 3 hard CodeChef problems. The goal was to get signatures from other people with those attributes:

After some quick snacks:

Go ahead Anshuman... one more Samosa never hurt anyone...

We tested people’s logic skills by having them solve a murder mystery:

No Bhavin the butler didn't do it!

Finally, Varun (aka syco) gave a rousing session on advanced data structures covering stacks, queues, heaps, binary index trees, and segment trees:

The videos from both Bhavin and Varun’s sessions, will be uploaded shortly. We look forward to future meetups in other cities as well. If anyone has any feedback in terms of how we could have made the meetup better, please let us know.

Cheers,
Chef

Pumpkin Pies,
We are pleased to announce the winners for the July Algorithm Challenge.  Drum roll please…

Top 5 (India):
1st – Varun Jalan (6.886)
2nd -Ashutosh Mehra (6.873)
3rd – Imran (6.868)
4th – Prunthaban K (6.854)
5th – Surendra (6.815)

Top 5 (US):
1st – Tomasz Czajka (7)
2nd – Josh Metzler (6.97)
3rd – Balakrishnan Varadarajan (6.964)
4th – Rahul Garg (6.917)
5th – Chris Narrikkattu (6.904)

All problems are now available in the practice arena. Test cases for all contest problems can be found here in three parts: Part 1, Part 2, Part 3.

Here are some additional statistics about the contest:

There was definitely room for improvement in this contest, and we hope to incorporate all the feedback we have received into making the next contest an even bigger success.

Thank you to everyone who participated.
Cheers,
Chef

Sweet Potatoes,
The July contest is officially closed. While we are calculating the results, we wanted to share some feedback and ideas for improvement for the next contest:

• We need one or two harder questions.  As many of you know, it is difficult to come up with challenging problems.  If anyone is interested in setting problems for future contest, get in touch with us at problems@codechef.com – we will pay for any problems we use.
• The contest needs to be shorter.  Next month’s contest will be one week long.  We will also be including a shorter duration contest at the end of next month (a few hours to a weekend – still deciding).
• We need to figure out a better way to determine winners for the challenge.  Rejudging all submissions with new test data doesn’t make sense, you can submit a bunch of variations which will perform differently for different input data.  There are two approaches we are considering: either limit the number of successful submissions one can submit for a problem (to let’s say 15) and not rejudge, only rejudge the last few accepted solutions (say 5), or only allow a certain number of submissions to the challenge problem a day (let’s say 10).  Your thoughts on this appreciated.
• We need to define rules better.  There can be no collaboration involved between contestants.  Any form of collaboration (whether it’s reviewing code, asking for output for a set of inputs, or asking for time complexity of an accepted solution) is not allowed.  We will immediately ban you on suspicion.  More on this in a subsequent post.

If anyone has any other suggestions on improvements for the contest format, types of problems, new competitions, etc… please let us know.

Cheers,

Chefarino

Hello,

The problem “Paying Up” was one of the easy ones in the March 2009 contest on Codechef. It is considered an easy problem, because it has a couple of approaches that work. The problem statement boils down to finding a subset of banknotes such that their sum is exactly equal to a certain value. Now, this problem is somewhat similar to the knapsack problem which asks for ways to fill up a knapsack of a certain size optimally with the given blocks. There is a solution based on dynamic programming for this problem, but we will be taking up a solution which makes good use of the way integers are represented in binary to solve this problem.

Now, the limit on the number of banknotes is ‘n’. Let us see how many subsets exist for these banknotes. For finding the number of subsets, we see that for every banknote, we have two choices, either to choose it in our calculation for the sum of notes or to ignore it in calculating the sum. Thus, we have 2 options per banknote and ‘n’ banknotes. So, the total number of subsets thus becomes 2^n where ^ represents the power operation. The number of subsets are small enough for us to bruteforce through them and the program to run in time.

An interesting way to generate all subsets of ‘n’ objects when ‘n’ is considerably small (n <= 20) is to use the properties of how unsigned integers are stored. Consider the number 2^n. This number is represented in binary form as ’10000…0′, that is, 1 followed by n 0s. Also, any number containing a 1 at the same position will surely be greater than 2^n. Thus, all numbers below 2^n do not have a 1 in a position greater than or equal to ‘n’ starting from the LSB. By induction, we can do the same for values of n = n-1 and n-2 and so on. Thus, we can see that any number between 2^(n-1) and 2^n will have a 1 in the position n-1. Extending this logic, we can say that if we consider the numbers from 1 to 2^n, we would be considering all possible ways in which we can choose some objects from ‘n’ objects.

For example, consider n = 3, so 2^n = 8. Let us list ‘i’ and its binary representation
i    Binary representation using ‘n’ bits
0    000
1    001
2    010
3    011
4    100
5    101
6    110
7    111

As you can see, if we consider that 1 means that we have selected object at that position and 0 means that we have not selected the object at that position, we can get all possible subsets of ‘n’ objects by looping over numbers from 1 to 2^n.

For calculating the sum of the subset represented by ‘i’, we loop from 0 to ‘n’ and we check whether the corresponding bit is set in the value for ‘i’ or not. If it is, we include that object in calculating our sum else we don’t. In this way, we can get the sum for all possible subsets of the ‘n’ objects.

This is exactly what we need for this problem. After taking in the number of objects, we loop ‘i’ from 1 to 2^n incrementing the value of ‘i’ by 1 at every stage to give us a new subset. Then for a particular value of ‘i’, we loop ‘j’ from 0 to n and check if the bit at that particular value is set or not. Languages like C / C++ provide bit-wise operators for leftshift and rightshift. For checking if the bit is set at position ‘j’(starting from 0) we can just check if the value of (i & (1<<j)) is 0. If it is 0, then the bit is not set, while if it is greater than 0, then the bit is set. Alternatively, we can also loop from 0 to n and at each stage check whether ‘i’ modulo 2 is equal to 1 or not. If it is 1, then the bit at that position is set, else it’s not. Then we divide ‘i’ by 2 and proceed. At the end of the ‘n’ iterations, ‘i’ will equal 0. The problem with this appraoch is that the modulo operations take much more time compared to the bitwise operations. Thus, now that we know how to check if the bit is set, we initialize a value ‘sum’ equal to 0 at the start of the ‘n’ iterations for a value of ‘i’ and if the bit at position ‘j’ is set, we add the corresponding banknote value to ‘sum’ else we don’t. At the end of these iterations, we check if the value of ‘sum’ equals the required value. If it does, then we have found a subset with the required sum and so we print a “Yes” and exit. Else, if at the end of 2^n iterations of ‘i’ we don’t have a subset with the required sum, then we print a “No” and exit.

The program should look something like this :

Start

Take in the value of 'n' and the required value of sum 'm'

Take in all the values for the banknotes in array 'd[]'

For i = 1 and i < (2^n)

    sum = 0

    For j = 0 and j < n

        if jth bit of i is set

            sum = sum + d[j]

    if sum equals m

        print Yes and return

Print No and return

We are pleased to announce our first CodeChef Meetup – an opportunity for local programmers to meet face-to-face, learn from each other, hangout together and just have some fun. The first meetup will take place in Mumbai on 18th July, Saturday. We hope to expand to other cities soon.

For the first meetup in Mumbai, we’re going to have Varun Jalan, winner of The CodeChef May and June Challenge, take a session on Advanced Data Structures. In addition to that there will be a round of puzzles and you can hang out with the top CodeChef performers.

Click here to RSVP. Check out the complete details of the meetup on the CodeChef Meetup Page.
Looking forward to seeing you there!

Hello all !

The problem that we will be taking up is http://www.codechef.com/problems/FCTRL2/
This problem basically asks you to calculate the factorial of a number up to 100. Now, I guess most of you know what a “factorial” is. For those who don’t, the factorial of a number N is 1*2*…*N. This problem would be very simple, had it not been for the maximum value of N. The structure of the problem is such that it asks the user to take the number of test cases as the first input. Then ‘t’ integers follow where ‘t’ is the number of test cases which was given as input previously.

For every integer here, we have to calculate the factorial. This is very simple in languages like python or java which have built-in support for big integer types. It proves to be a hassle for people using C / C++ or languages that do not have a built-in biginteger type. Let’s think about how we can store the the result.

Now, the maximum number that we can store in an unsigned 32 bit integer is 2 ^ 32 – 1 and in an unsigned 64 bit integer is 2 ^ 64 – 1. Something like 100!(‘!’ is the notation
for factorial) has over 150 decimal digits. The data types mentioned earlier can store numbers having at most 9 and 19 decimal digits respectively. So, we need to find a way to store the 150+ digits that we will get as the answer. The simplest data structure that we can use is an integer array of size of about 200 to be on the safe side.

In the simplest form, let us store one decimal digit per array index. So, if the number is say 120, then the array will have the numbers as follows:

Say a[200] is how we declare the array, then
a[0] = 0
a[1] = 2
a[2] = 1

The least significant digit is stored in the lowest index 0. The next one in index 1 and so on. Along with the array, we need an integer specifying the total number of digits in the array at the given moment. Let this number be ‘m‘. Initially, a[0] will be 1 and the value of ‘m‘ will be 1 specifying that we have just one digit in the array.

Let’s take a simple example first. Consider that the array has some value like 45 and we need to multiply it with a value 37. This can be done in the following way.
The array will be:
a[0] = 5
a[1] = 4
and the value of m will be 2 specifying that there are 2 digits in the array currently.

Now, to multiply this array with the value 37. We start off from the index 0 of the array to index 1. At every iteration, we calculate 37 * a[index]. We also maintain a temporary variable called temp which is initialized to 0. Now, at every step, we calculate x = a[index] * 37 + temp. The new value of a[index] will be x % 10 and the new value of temp will be temp / 10. We are simply carrying out multiplication the way it is carried out usually. So, for the current situation, the iterations will be something like this.

Initialize temp = 0
Iteration 1 :
array = (5, 4)
temp = 0
index = 0, a[index] = 5
x = a[index] * 37 + temp = 5 * 37 + 0 = 185.
the new value of a[index] = 185 % 10 which is 5 and the new value of temp is 185 / 10 which is 18

Iteration 2 :
array : (5, 4)
temp = 18
index = 1, a[index] = 4
x = a[index] * 37 + temp = 4 * 37 + 18 = 166.
the new value of a[index] = 166 % 10 which is 6 and the new value of temp is 166 / 10 which is 16

We have finished 2 iterations and this is the value of ‘m‘, the array size at the moment. The required number of iterations is now over, but the value of temp is still greater than 0. This means that the current value of temp is to be incorporated into the array. For that, we keep appending the last digit of temp to the array and divide temp by 10 till temp becomes 0. So, we will get something like
Iteration 1 :
temp = 16 , array = (5, 6)
So, we add 16 % 10 to the array so that the array becomes (5, 6, 6) and we divide temp by 10 so that temp becomes 1. We update the value of ‘m’ to m + 1 that is m = 3
Iteration 2 :
temp = 1, array = (5, 6, 6)
Now, we add 1 % 10 to the array so the array becomes (5, 6, 6, 1) and we divide temp by 10 so that temp becomes 0. We update the value of ‘m’ to m + 1 that is m = 4

The value of temp is now 0 and our multiplication is now over. The final array we get is (5, 6, 6, 1)

Voila, we have the answer to 45 * 37 in our array with the Least significant digit in the 0th position.

For finding the factorial, we need to carry out this exact multiplication operation at every step as we loop from 1 to N. At the end of the Nth iteration, our array will contain
the answer and the value of m will be the number of digits in the answer. We can then just print the array from the Most significant digit to the least for the answer.

The basic flow of the program will be as below :

Start

Take in the number of test cases

While there is a test case remaining to be handled

    Take in the number whose factorial is to be found, let it be N

    Initialize the array's 0th index to 1 and m to 1

    Initialize i to 1

    While i is less than or equal to N

       	Carry out multiplication of the array with 'i' as shown above.

    Print the contents of the array starting from the most significant digit and ending with the least significant digit.

Stop

Certain improvements can be made to the above mentioned method. We are storing only one digit per array index, We can store more than 1 digit per index so that the number of computations are reduced. The method to do that is the same as above. We leave it to the reader as an exercise