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:

Bhavin (CEO Directi) speaks at CodeChef Meetupon 18/7/09 from CodeChef on Vimeo.

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:

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

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:

Length of Contest |
Unique Visitors |
Unique Participants |
Total Number of Submissions |
Percentage of user who have solved at least one problem |

12 days | 8,387 | 406 | 9656 | 57% |

Country | Total Participants | Average Score per User |

IN | 279 | 1.25 |

US | 63 | 1.99 |

Rest of World | 64 | 2.30 |

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

- API < br/ >
- CodeChef DSA Student Offer
- [Live Updates] ACM ICPC Kanpur Regional 2019-20
- Chef’s New Year Present
- [Live Updates] ACM ICPC Amritapuri Regional 2019-20

- About (14)
- ACM ICPC (25)
- Announcement (308)
- API (3)
- Campus Chapters (7)
- CCDSAP (7)
- CCDSAP Stories (5)
- Certification (9)
- College Contests (9)
- Contests (281)
- Events (57)
- FAQ (1)
- Features (53)
- Interviews (25)
- Languages (1)
- Meetup (4)
- Open Source (1)
- Practice Problems (8)
- Prizes (20)
- Problems (15)
- ProblemSetting (1)
- Programmer of the Month (34)
- Schools (13)
- SnackDown (2)
- Tech Talks (23)
- Tutorials (35)
- Uncategorized (1)
- Volunteers (4)
- Winners (123)

- Manraj Singh on In conversation with Taranpreet Singh – an accounting student turned 6-star coder!
- Bhagya Kamal Jain on CodeChef DSA Student Offer
- Avi Srivastava on Tutorial For Small Factorials
- Shloki Jha on Tutorial For Small Factorials
- Shloki Jha on Tutorial For Small Factorials

- January 2020
- December 2019
- September 2019
- July 2019
- June 2019
- May 2019
- March 2019
- February 2019
- January 2019
- December 2018
- November 2018
- October 2018
- September 2018
- August 2018
- July 2018
- June 2018
- April 2018
- March 2018
- February 2018
- January 2018
- December 2017
- November 2017
- September 2017
- August 2017
- July 2017
- June 2017
- 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