Banana Splits,
This past week we were lucky enough to meet the winners of our March Challenge and personally deliver their prizes. Earlier in the week Bhavin (Directi’s CEO) was in Hyderabad and met up with Anshuman Singh and Ajay Somani (both from IIIT Hyderabad):

Anshuman, Bhavin and Ajay

Prateek Karandikar was nice enough to come into our Bangalore office to pick up his prize:

Prateek and his Nokia 5800

Congratulations once again.  Our April Challenge starts on April 1st at 15:00 IST.  Best of luck to everyone!

Cheers,
The Chef

Butter Rotis,
We are excited to announce our 3rd competition - The April CodeChef Challenge - which will run from April 1st 15:00 IST to April 15th 15:00 IST.  As discussed, all code submissions from the April contest will be available after the contest is over.  We have also extended the number of prizes from 3 to 5 including:

1. Cannon EOS 1000D camera
2. Bose Companion 5 Multimedia System
3. Nintendo Wii
4. 32 GB Pen Drive
5. LED Binary Watch

If you come in 1st place, you can choose any of the prizes, if you come in 2nd place you can choose any of the prizes from 2nd place down (i.e. not the Canon camera), 3rd place nets you any of the prizes from 3rd-5th, etc…

The format of the contest will stay the same as our March competition:

• Contest problems will become visible on April 1st at 15:00 IST.
• The contest will consist of 6 problems of varying difficulty.
• You will receive one point for solving a problem (passing all test cases - no partial credit), regardless of the level of difficulty of that problem.
• You can submit solutions as many times as you’d like, there are no penalties for incorrect submissions.
• Each contest will have one min/max tie breaker problem (i.e. Place the mines!), where the best solution will receive one point and all other solutions will receive a fraction based how close they come to the best solution.
• In the unlikely case of an overall tie (including the same score on the tie-breaker) a winner will be randomly chosen from the top scorers.

We are considering ways to improve the scoring and format of future contests based on feedback we have received and our May contest might have some changes.  As always, feel free to get in touch with us if you have questions or feedback.

Cheers,

The Chef

Hash Browns,

Our goals with CodeChef are to challenge and engage the developer community as well as provide a platform for competition and improvement.  We’ve heard from many people that when they get a wrong answer or time limit exceeded they aren’t sure how to debug their submissions.  We are working on a few ways to improve this:

• Additional tutorials describing various approaches to debugging and reducing execution time.
• An interactive mode which allows you to specify inputs which will run on our testing infrastructure and display the output (possibly only available in the practice arena).  This will allow you to debug any infrastructure or compiler differences and see how your code runs on the machine it is evaluated on.
• Additional information on submissions (possibly only available in the practice arena) - For each test case, the number of inputs, the result, execution time and time limit.   This will let you know if your approach is correct and you just need to optimize your solution to fit within the time limits, or if it’s back to the drawing board.

For our April Contest, we will also be experimenting with another major change.  After the contest is over we will make all code submissions for problems within that contest, publicly available.  Eventually we plan to allow comments on individual submissions as well.  We hope this will allow less experienced developers to learn from their peers and generally promote knowledge sharing.  We look forward to hearing your feedback on these initiatives.

Cheers,

The Chef

Fish Sticks,

We’re happy to announce a new contest held in conjunction with IIT Roorkee - Insomnia.  There are two rounds:

• Speed Round - March 20th 4pm - 8pm IST
• Thought Round - March 21st 9pm - March 22nd 9am (they don’t call it Insomnia for ‘nuthin)

Check out the contest landing pages for details.  Winners will receive cold, hard cash for their efforts.

Want to hold your own programming contest on CodeChef?  Check out our CodeChef Campus Chapters or contacts us at contests@codechef.com.

Cheers,

The Chef

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.

Kitchenettes,

We’d like to thank the hundreds of users from across India who submitted thousands of solutions for our first contest.   We thought it was really exciting, with lead changes happening right until the end.   Congratulations to our winners:

1. Anshuman Singh - IIIT Hyderabad
2. Ajay Somani - IIIT Hyderabad
3. Prateek Karandikar - Indian Statistical Institute

Now we’d like your help in making CodeChef better.  We understand there were things that could be improved and we’d like to ask you a few questions in preparation for our next contest.

• We’ve heard from many users that we don’t provide enough information when an incorrect solution is submitted.  We are working on improving this.  From a functional standpoint how else can we improve the site?
• We understand there was some confusion as to when the contest was ending, as well as who will be receiving what prizes, in the next contest this will be made more clear.  Any other information we should have provided?
• In regards to the contest, was the format (5 questions with a tie-breaker) appropriate?  Was 2 weeks too long?
• Which problems did you enjoy more or less and why?

Feel free to comment below or send an e-mail to feedback@codechef.com with your responses.

This Friday and Saturday night we will be hosting IIT Roorkee’s Insomnia on CodeChef.   Full details will be announced tomorrow.  We will be back on April 1st, with another CodeChef contest.

Cheers,

The Chef

Greasy Spoons,

Hrishikesh Terdalkar from Chennai Mathematical Institute and winner of the TechFest Challenge, was nice enough to send us some photos of him and his new Nintendo Wii:

If you are a student and would like CodeChef to host a programming competition on your campus, check out our CodeChef Campus Chapters.

Happy coding!