The road to December Cook-Off 2015 came through the galore of examinations and preparations. Programmers across the globe were busy honing their skills for the busy ACM ICPC season, while trying to keep up with their exams and trying hard to ensure good pointers. To add more chills to that entire setup, we had the winters in its full glory. All in all, it was a thrilling set up for an exciting two and half hour programming contest and we couldn’t have asked for more. But we got more.
The December Cook-Off 2015 was exactly the night before the ACM ICPC 2015 Amritapuri Regionals. While the teams attending the regionals were trying to stay calm before the big contest, there were participants from all over the globe raring to get their hands on the problems of Misha Chorniy. Amid that mixed batch of participants began our COOK65, the last one for the year 2015.
And what a start it was. Just like a big flashy Sunday party, the December Cook-Off started to 98 ACs out of the first 100 submissions in the contest. All this and we were 10 minutes into the contest. What’s even more exciting was the fact that all of those 100 submissions, and the next 100 to follow came on Chef and Subarrays. Perhaps, every who joined the contest that night made their first submission to Chef and Subarrays. Just to have a nice and smooth start to it. It remained the same way until lebron submitted to Chef and Queries. It was also an AC. So, if we have to sum up the first half an hour of the contest it will be like: 2 problems, lots of ACs, very few WAs, and even fewer TLEs and CEs.
As we moved into the contest, the happy start made way for the fury and rage brought onto the participants by Chef and Vectors, Chef and Tree, and Chef and LCS. If you got your hopes high on your performance into the contest after the green ticks you got on the first and second problem, it must not have felt nice trying your hands on those problems. So, do let us know how it was in the comments section below. The immaculate job by our tester Jingbo Shang ensured the right mix of difficulty levels in the problem set. What did you thought of it?
The flow of the submissions in the second half of the contest did slow down, but the intensity of the competition prevailed till the very last moment. notimesea, who made the first submission into the contest, defended his spot atop the rank tables bravely from the challengers in lebron, alex_2008, Ra16bit, and the mighty ACRush. They all had 4 problems in their account and while ACRush cracked all the problems in the first submission, CHEFVEC took two to crack. And with that, he secured the top slot in the contest. And that was our final Cook-Off for the year 2015. We hope you all enjoyed the contest as much as we did putting it up for you.
Now, let us take you through the rank table to introduce you to the winners of COOK65.
We start with the ROW top 10:
The Indian top 5:
Now, the final stats for the contest:
Congratulations to you all on your performance.
Now, let us serve you the editorials for the December Cook-Off 2015, penned by our young editorialist Pushkar Mishra. We are sure you would have tasted them by now, but if you have not, here they are for you once again.
That will be all from us all here. We hope you had a wonderful 2015 and are ready for an exciting 2016 in front of us.
Till next time, adios.
See you at the contests.
Regards,
Rudreshwar
Team CodeChef
Dear CodeCheffers,
As the time nears the declaration of the selected list of teams for the onsite, we think we must own up the mistake and issue an apology. We understand that there were some problems with the online round for ACM ICPC 2013 IIT KGP regionals. For those who missed it:
For the first issue, we investigated and found out that it was caused due to an un-optimised query that fetches you all the submissions of a particular problem in the practice section! We are in the process of fixing it, but we thought we should at least tell you what the reason is while the fix happens. To make up for it, we had extended the contest by another 10 minutes. We also eliminated all penalties for those who were affected by the slowness and ended up submitting the same solution multiple times.
The second issue impacted users much more. And we realised that we had goofed up, only after the contest. At this stage, we sat down and evaluated all the options to salvage the situation. We knew that we could not be fair to everyone from that point. No matter what we did from there, there would be one section who would be affected by this mistake of ours. Considering every possible scenario (including a re-contest), here’s what we decided to do:
Change the test data such that the solutions which solved the problem without sorting the output list also passes. This essentially also meant that the problem no longer required a DP solution to pass and became easier than what it was intended to be. We rejudged all the solutions which had not passed during the contest for this problem with the new test data, leaving aside those that had passed. This resulted in more teams now solving the problem.
Some of you are bound to feel (especially those who wasted a lot of time on this problem) that this isn’t fair. We know it, but there is not much that we can do about it. We screwed up, and we’re really sorry. Here are the other options and an explanation of why we took this approach:
While we acknowledge that we have goofed up and we regret it beyond what we can put across, we also think, that not being stuck on a problem, you are unable to solve, is among the many things that can propel your team to be a good ICPC team. A team of three wasting all their time on a single problem can cause a lot of frustration, but then that should not warrant wasting the time of so many other teams that have done well and also learnt to deal with such situations and got more efficient.
Some people will undoubtably feel like we should’ve taken one of the other approaches listed above. We’re sorry, we cannot do that. Don’t hate us. We know we have goofed up. And we did try our best to be as fair as we possibly can in the given circumstances. We wanted a good fair contest as much as you all did. We did receive some positive feedback on the problems being good as well. We have also published the editorials for the problems. We did try to do as much as we can.
For those who will not be able to make it to the onsites due to this mistake of ours, we sincerely apologise. We know, nothing can make up for it. But there is only so much we can do. Please do not get demotivated and do not give up. Please practice hard for next year. We will be around to help you all in your preparations. We assure you, that we will be extra careful next time around. We are sorry.
Anup
This is a truly interesting question, and I thought it would be a great way to have this opened to the CodeChef community so that we can get their views on various styles, as well as what works and what doesn’t. I’d also like to particularly invite other Editorialists (Anton, Shilp etc.) to describe their process and their reasoning etc.
All of these have their own unique style of Editorials.
Now, I’ll put in some of my views on what makes a good Editorial, and how I’ve learnt over the past few months.
This, I believe, is something worth striving for. Personally, I tend to often take up a very conversational tone in my Editorials (imagining that I am explaining everything from scratch). This tends to make my Editorials unnecessarily verbose. I fear that although the tone is light, I would lose the engagement of an experienced coder. And if its too verbose, I would even lose an intermediate one, while a beginner may wonder “why is this being mentioned”. Having said that, if it is made too technical, then anyone who doesn’t know what’s going on would stop reading. There needs to be a balance between what needs to be said, what is said, and what isn’t said – and striking this balance may not be easy.
In particular, I tend to provide justification after each assertion, while I think it is often better to leave the reader to try out justifying some of the things as he reads them, and if he fails, to find justification later on in the Editorial.
Try not to beat about the bush!
This is not contradictory to what I said earlier about it being non-verbose. When I say thorough, I mean that it should give a complete description of anything related to the problem. Things like “related problems”, “tutorials” on other sites, “mathematical concepts” from other sources – anything related to the problem and its solution should ideally be packaged under the one same Editorial. Imagine reading the solution to a problem on Heavy-light Decomposition. The next thing you need, is somewhere to practice. Imagine having an entire network of Related Problems from which you can shift and browse and practice one by one!!
However, the flipside is that the Editorialist needs to be aware of various resources, and should be able to call them up from memory as required. Again, calling up past problems from memory, is another personal failing (heck, in TC matches, I have often forgotten the 250 pointer by the time I get done with the 500!!).
Add as much information as possible under the one encapsulated Editorial.
Here, “Top-down” style is where the Solution starts with the problem, and then step by step talks about what is required and how each subproblem gets fixed. The “Bottom-up” style on the other hand, first describes the solutions to the subproblems and then puts them together to show you the solution to the whole problem.
Almost always, I’d say the Top-down style is better. It keeps the reader motivated instead of wondering (“why are we doing this”). It also tends to make the solution look simple. By saying “Okay, so X is the problem – that means we need Y – so how do we get it, lets say if we could have Y1, then we could get Y by Z. That just leaves getting Y1 – so lets try to do PQR…”, you are at each step making every requirement and consequent solution seem natural.
Compare that with saying, “First, let us consider Y1. To solve Y1, lets do PQR… Now, finally, you should see that you can get Y from Y1 using Z, and that means you have solved X.” Here, the reader is left wondering “whats up with Y1? Ouch, here comes PQR”.
As a concrete example, consider the following “Tutorial” on Heavy-Light Decomposition:
Problem: You have a tree, where each node has a weight. You can either change the weight of a node, or are asked to query the sum of weights on nodes along a path in the tree. You need O(logN^2) time per operation.
Bottom-up Style
First, find the size of the subtree rooted at each node. Also, we will need to answer LCA queries, so fill in information for that too.
Then, for each node, let us call the edge to the largest (by number of nodes in subtree) child a “heavy” edge. Ties are broken arbitrarily. All other edges are called “light” edges. The set of heavy edges now forms a set of disjoint paths in the tree.
We count the number of different paths from a node to the root. Since you shift from one path to another only through light edges, and since each shift atleast doubles the size of the subtree, you would have shifted only at most log(N) times.
Now, consider each path as a segment tree, so when you update the weight of a node, it takes O(logN) time. Finally, for finding the sum of weights along the path between nodes u and v, first find the LCA w, and then find the sum of weights along the path from u to w, and v to w. Since from any node there are atmost log(N) different paths, overall complexity is O(logN^2).Top-down style
Let us suppose our tree was a path. Then we could easily solve the problem using a segment tree.
Now, if instead our tree were divided into a set of disjoint paths, and consider each path as a segment, then an update will just take O(log(path_length)) time. And we know path_length <= N.
To answer a query (u, v), let us first find the LCA w, and then divide the path from u to v into u to w and w to v. Then, we just go across each of our segments and take the sum along the way.
Thus, if there are K segments along the path from u to w or v to w, we would like that K is small: since our query will take O(K logN) time.
Finally, if we were to make our segments in such a way that the largest subtree gets to continue the segment, then from any node, along the path to the root, we would shift segments only when doubling our subtree size. Hence, under this scheme, K is always O(logN).
This was to illustrate (hopefully) how the Top-down approach maintains motivation by assuming the least and filling in gaps only as they appear.
Now, I’ve noticed, atleast while learning, that when things look simple, they’re taken to be simple. And when things are taken to be simple, a lot of the intricacies are often taken for granted. In which case, the next time something like this comes up, one might not be able to reconstruct the whole picture by oneself. Thus, in cases where a technique can be applied widely, it might be better to describe it in bottom-up fashion. (One can illustrate use of Binary Indexed Tree by taking the example of dynamic prefix sums being required – or one can start with what Binary Indexed Trees are, and then show how they solve a dynamic prefix sum problem; the latter being favoured although it is bottom-up in this case).
This is just my personal opinions, and if you feel differently, do say so and explain why.
Its always nice to see the entire solution at one stretch. It gives you an overview of what to do, where you failed, how to get the whole thing, all in one picture. Thats what Quick Explanation is for. As far as possible, I’d prefer to have Quick Explanation + Detailed Explanation used. The Quick Explanation should indeed cover all aspects of the solution, and shouldn’t just be about dropping hints (that’s in some sense what “pre-requisites” is for).
In some cases however, just Explanation is good enough. These would be when either the problem is so simple that the Quick Explanation is the entire explanation, or when the problem is so hard, that the solution cannot be summarized without leaving large loopholes.
Whenever possible, Editorials should have a summarized Quick Explanation.
This idea I had picked up from a comment on one of my Editorials. It said, (paraphrased), “Often, it is easier to understand what is going on from the pseudocode rather from the explanation.” In some sense, it is saying that you can say “do this – do that” as much as you like, but it won’t hit home as well as the same thing in pseudocode. The way Mathematics has its own set of symbols: ∀. ∃, ∑ etc. which help clearly and concisely state things, Algorithms uses the language of Pseudocode to convey its ideas succinctly.
Key points of the solution should be written in pseudocode.
During the (Indian) IOI Training Camp last year (2012), we had a set of “coding commentaries” which concentrated not so much on the solution itself, as much as on the various bugs that people had made, and on all the points where the code could have been made neater and easier to debug. It would be great if we could have such sections in the CodeChef Editorials as well (they would largely help reduce the number of “what is wrong with my code” questions being posted after all).
The logistics of running this in a IOITC vs on codechef are very different: in one, you have twenty students coding in a two hour window, on the other you have hundreds-thousands of coders submitting solutions. As such, there is scope for such sections during short contests, wherein the “cooks” browse through a whole load of random submissions, spot bugs, find commonalities and add them to the Editorial. Tips on coding style are relatively harder due to the large and varied range of submissions (20 students writing varied shades of clean/dirty code is different from thousands writing varied shades of “code”: harder to classify dirt from cleanliness). In Long Contests, unless the setting panel made testcases to beat various bugs or suboptimal solutions, it is hard to browse through even “random” codes of people over 10 days and glean knowledge of bugs worth mentioning. Also, the fact that the short contests are far more high energy on the setting side during the course of the contest makes this section relatively more viable in such cases.
As important as it is to describe what works, it is also important to describe what doesn’t!
Editorials are the Editorialist’s labour of love.
Generally, when the Editorialist sees the problem, he first tries to find the solution himself. Alternately, he follows discussions between Setter and Tester and makes sense of the solution from there. Or, he looks at the codes of the Setter/Tester, and justifies what is being done from that point. And if all these aren’t enough (which is the case for the Hard problems a lot of the time), he takes the direct help of the Setter/Tester.
When he arrives at the solution himself, it is then often presented well.
However, in a lot of other times, what can happen (and what should be avoided) is that the solution is presented from the point of view of the setter. One of the comments that I got on one of my Editorials, was “This is just a description of the Setter’s code, and not a solution itself”. The point was very valid, and the fact was that since I hadn’t arrived at the solution myself, I did not outline the thought process of someone who is attacking the problem from scratch. What I had done was present justification for why what the setter had done works.
The Editorialist, by being privy to the solutions, should put in his own effort in making them palatable. His job boils down to answering “Given that this is the solution, and that I know it, how do I make someone who doesn’t know it see it?”
The use of diagrams esp. for Geometry problems, although it takes a little more effort, can speak a thousand words, and would consequently form a bond between the Editorial and the Editorialist (I always enjoy viewing my TRIQUERY Editorial, with the use of its colour-coded lines etc. and I’m sure Utkarsh would do the same for his TAACUTE Editorial).
If the Setter cooks the dishes, and the Tester tastes them, then it is the Editorialist who serves the dessert!
If you have any further suggestions on how to make Editorials better, do post them as answers in the discussion forums.
I hope this post opens discussions on what to do, and how to do all-things-editorials.
[If you merely agree/disagree with any point, post those as comments rather than separate answers].
I hope that this would grow into a “Guidelines/FAQ for Editorialists” or something in time.
Hello People,
We will be taking the site offline for some changes to the website. No, we won’t say now what changes, but we assure you all that it will be eye pleasing 
Downtime From: 16:30(IST)
Period: 5 minutes
The site will remain offline for a period of 5 minutes if every goes well. Kindly bear with us for the downtime.
-Regards,
Tojo Chacko.
We will be taking the site offline today (June 16, 2012) for scheduled maintenance at 11:00 PM (IST). The site will be offline for a duration of an hour. Please be patient and keep watching this space on what is going to come.
-Abhijeet,
Team CodeChef.
Drumroll, please…
The winners of the CodeChef Book giveaway are:
And just because we loved Ankit and Anil’s enthusiasm and contributions we will be sending them a CodeChef goody bag.
Ankit’s (ankitjain0912) tutorials:
Dynamic Programming
White Night
Anil’s (flying_ant) tutorial:
Graph Theory
Congratulations guys! Your books/merchandise will reach you soon.
On another note, there are quite a few topics on the Tutorial page that people have requested for and it would be awesome to see more of you contribute to the tutorials on the wiki.
-Shaheen
Aloo Makhnis,
Aniruddha from the CodeChef team has put together a video tutorial for Puzzle Game . We hope to start including more content including articles, podcasts and additional videos in the near future. The video is embedded below and also on our wiki:
CodeChef Video Tutorial : A Puzzle Game by Aniruddha Laud from Directi on Vimeo.
What do you guys think? Are video tutorials helpful? What other content can we produce that will help you become better programmers? Anyone want to volunteer to create additional videos or podcasts? These can be interviews, tips, tutorials, whatever you think will help people.
We will be announcing two contest for November and a “special” CodeChef project shortly, stay tuned…
Cheers,
Amit
We are constantly thinking about ways how to help people become better programmers. We recently launched the CodeChef Wiki so that people can share tips, resources and tutorials. Unfortunately, it seems people have been a little shy about contributing. To get the ball rolling, we will be giving away books to the top wiki contributors this month.
All you have to do is use the wiki as a place to note all the things you love about programming – resources, tips, tutorials, etc. At the end of October the top three contributors to the tutorials will each receive a set of The Art of Computer Programming (Volume I, II and III) and the other contributors will receive CodeChef T-shirts and laptop stickers.
How can you contribute to the wiki?
Rules:
If you have any questions, drop us a comment, email or tweet.
Hello all,
At Codechef our goal is to help people become better programmers. An integral part of this is discussion and we find that sometimes, we are the bottleneck for growth amongst the community. In an effort to promote collaboration we are thinking about making the following changes.
1. Introducing a wiki: We plan on introducing a wiki where most users will be able to edit pages related to the FAQ, Tutorials, Tips, Resources, Strategies, etc… We want to create some easily achievable task as the criteria for becoming an editor. Our plan is to let anyone who has had at least one successful submission in any of our contests will be able to edit the wiki. We feel like this will encourage greater collaboration and allow all of you to contribute meaningfully.
2. Disabling comments : We thought that commenting on problems would be a good idea, but we are finding it is not being used in the way we intended it. The comments are mainly from new comers asking questions whose answers are available elsewhere. Unless we can figure out a way to ensure that comments are used for questions related to that problem specifically, we feel that through the wiki, forums, blog, email, twitter and chat (soon coming back), there are enough options to communicate with us and each other.
3. Introducing a new forum : The current forum is not well integrated into the site and also not integrated with our authentication system. We plan on introducing a forum which integrates better and retains the same look and feel as our site. We will also create a section for high priority issues which we will monitor carefully, allowing you guys to bring up any major site or contest issues to our immediate attention.
We would like to know what you think about these new features that we plan to introduce? Do you think that disabling the comments and restricting discussions about problems to the forums is a better idea? Or would you like us to scrap the forums and keep the comments’ section as it is? Also, what do you think about the idea of the wiki editing facility being open to only those who successfully solve problems in the contests? Do leave in comments to let us know what you think
Regards,
Aniruddha.
On the 3rd of Sept 2009, I delivered a session at MPSTME, NMIMS (Mumbai), on ‘The Basic Implementation of a Search Engine’.
The crowd attending the session ranged from first year students to final year students and so I kept the session rather basic without going into the details of the subject. The students were bright and very enthusiastic, and the audience participation was simply awesome.
In the session I demonstrated a small Perl Script with a few functions to explain a Crawler, Indexer and Search Logic.
I am attaching the code to this post and below is the video of the session.
Lastly, I would like to thank Gaurav Munjal and the entire ACM MPSTME team for all their help.
This session was part of a CodeChef Campus Chapter. Register here to start a Campus Chapter in your college as well.
CodeChef Talk at MPSTME, NMIMS (Mumbai) from Directi on Vimeo.
Cheers,
Vikram
~vix on CodeChef Twitter
© 2009, Directi Group. All Rights Reserved.
