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.
TopCoder vs Codeforces vs CodeChef
All of these have their own unique style of Editorials.
- TopCoder generally has a slightly personal touch, describing some tidbits about the match, followed by Problem by Problem solutions. Further, there is source code for most problems.
- Codeforces has a similar style, again focussing on describing the solution.
- CodeChef however, caters to the Indian community. In other words, we cater to quantity over quality, and would always like to go the extra mile in describing a solution. This Editorials here are continuously evolving, all in the goals of getting as many Indians as possible more equipped to solve harder problems contest by contest. Hence, the CodeChef Editorialist’s job is not merely to state do-this-do-that because this-implies-this-implies-that, but also to make the entire thought process simple, natural, complete and convincing.
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.
It should be concise, not verbose
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.
Try not to beat about the bush!
It should be thorough
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.
Top-down style vs Bottom-up style
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.
Quick Explanation + Detailed Explanation vs just Explanation
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.
Pseudocode
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.
Bugs/“Coding Commentary”
During the (Indian) IOI Training Camp last year (2012), we had a set of solutions 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!
The Editorialist’s Role
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 POV 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!
Conclusion
If you have any further suggestions on how to make Editorials better, do post them as answers below.
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.
