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):
Prateek Karandikar was nice enough to come into our Bangalore office to pick up his prize:
Congratulations once again. Our April Challenge starts on April 1st at 15:00 IST. Best of luck to everyone!
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:
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:
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.
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:
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.
We’re happy to announce a new contest held in conjunction with IIT Roorkee – Insomnia. There are two rounds:
Check out the contest landing pages for details. Winners will receive cold, hard cash for their efforts.
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.
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:
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.
Feel free to comment below or send an e-mail to firstname.lastname@example.org 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.
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.