I clearly cannot write editorials (see here, here, etc.)
Can anyone please actually explain me how to write editorials properly? What I do now is just providing my thinking process to reach the solution, but it seems that most people have a very different thinking process.
UPD: after reading the comments, I think I got what's wrong in my editorials (and I tried to fix that, especially in the editorial of 2018B - Speedbreaker). One of the main issues is that I tend to skip algebraic manipulations, inequalities, etc. (i.e., steps that require simple algebra and/or mathematical logic), and it turned out that they can be the bottleneck for most people here (and maybe this is also the reason why 2018B - Speedbreaker is harder than 2018C - Tree Pruning). Lesson learned: if some numbers / variables appears from nowhere, I should try to elaborate, even if it's a single mathematical step.
For earlier problems, maybe I should also focus on how to convert the ideas into code.
Anyway, I think this comment helped me a lot to write a "better" editorial. In an ideal world, I would ask testers to read the initial version of the editorial and write similar comments, to help me "fix" the editorial. But during problem preparation, the editorial is the most neglected part for obvious reasons (there are a lot of little things that can ruin a contest, but in theory a contest can be held without even publishing an editorial), and ideally I don't want to fix the editorial 2 days after the contest end, because most people would have already read it. A solution might be just to give write access to the editorial directly to the testers and let them fix it if they had trouble understanding something?
Actually , Your editorials are nice and clear , nvm about these comments
(maybe some people works on observation methods ? , idk maybe this make it better)
First of all, the problems were very nice and I hope you create more rounds. Here is one thing that I think you should take into consideration though. I don't think it is enough to just provide your thinking process to reach the solution. Also, obviously a beginner's thinking process will be different from you. In my opinion, when you write editorials you have to consider the perspective of someone who wasn't able to solve the problem, that's why they read the editorials in the first place so that they can learn from it. So, you have to think about the reasons why someone couldn't have solved the problem and write editorials accordingly.
For example, consider the problem Div1A "cards partition". Here you have just simply stated this, "distribution is possible if the maximum number of cards of some type (x) is ≤m/s". Of course, this is a well known idea to you but this might be the first time someone is coming across this and in that case for them it isn't obvious at all and this is probably the main reason why they weren't able to solve this problem otherwise the problem is quite easy. So, I think you should have let them know that this is a standard problem and maybe give a proof or provide a link for the proof from where they can learn.(a part of the proof for this is quite tricky in my opinion).
Btw, I solved this problem relatively fast in the contest for my level but only because I came across this idea first when I saw the problem on Educational round 1954D-coloured balls, had to read the editorial for that. You can see how they wrote the editorial for that by first mentioning how this was a standard problem.
""" For a fixed set of colors, this is a standard problem with the following solution: let's denote the total number of balls as s , then the value of the set is ⌈s2⌉ ; but there is an exception in the case when there is a color with more than s2 balls, then the value is the number of balls of this color.
So the answer depends only on whether there is a color that has more balls than all the others combined."""
https://codeforces.net/blog/entry/128421
This is a good point. It seems like adding a proof is something I would have done normally (in most other crucial points there are proofs), but here I forgot because the subproblem is standard for me. I will add a proof in a few minutes.
Cool. I also think mentioning that this is a standard subproblem will help beginners to notice it and recognize it in future problems. I can explain the reason but you have explained it yourself in a comment. Took me a while to find this comment lol :)
https://codeforces.net/blog/entry/94404#comment-834632
I think for me the most important thing is not the proofs though. Proofs are why the solution works, but to improve I would like to know how to think of the solution.
Like in the last Div.1 E, I spent hours on optimizing the $$$O(n\log n)$$$ check for a fixed size and tried many ways but couldn't think of the DSU solution. When I looked up the editorial I was stunned to see that DSU was actually used to solve the problem because I had no idea how they were related.
If you just told me that I should use DSU, I guess I would probably figure out how to do it. But most of the times I can't solve a problem, it's because I literally didn't think in the right way. However I couldn't find anything helpful in that direction in the editorials.
This is a big problem in most of the editorials though (and the ones written by myself) because sometimes we don't know how we thought of an idea ourselves. But maybe adding the thinking process would help much better.
I suspect the following:
Did anyone here actually notice the DSU optimization without having encountered it before? How?
I got baited by the constraints to think of an $$$O(n^2)$$$ solution, and I kinda forced myself to think of optimizations to the check.
I had never seen the exact problem, but I've done a few "log to alpha"s before. The general idea is to make some observations to simplify the problem enough until it can be solved with DSU.
With that in mind, I tried to find some nice properties. $$$r$$$ is increasing, and our only query is global max. From there, it's not that much of a stretch to see that only suffix max matters, and the DSU solution follows from that.
My take is that the general problem of "range add, global max" is hard to solve under $$$O(\log n)$$$, and can only be done if the operations are "special" in some way, which is indeed true here.
Thanks for the explanation! I actually have done the ucup problem in contest, but I managed to squeeze a $$$O(n^2\log n)$$$ solution into the time limit, so I didn't know about the optimization :(
To me it seems a lot to ask authors to also lay out exactly how they thought about the problems. There is already inf work in preparation, having to prepare good writing as well may decrease contest frequency lower than it already is. It's always nice when author can take extra time to do do this but I hope instead we can make it easier to crowd source intuition and explanations.
There are few contests not because of the lack of authors, but because of the lack of coordinators (but I agree with the general idea of the comment anyway).
I do understand that authors are already doing a lot to prepare a contest, and I think what you have done is really fantastic. The problems in the editorial are basically just details where improvements can be made but they are already very good by now.
Basically my suggestions are typical problems in all editorials, not only for contest problems but also for most of the training problems as well. I think it's because sometimes when we are solving problems we just suddenly have an inspiration and know how to do it, while it's really hard to explain how we think of it, let alone make other people know how to think of it.
This situation is especially common for harder problems, like the AGC problems. I sometimes sit there for hours and don't know what to do, but then just a slight idea comes into mind and I'm done with the problem.
Currently I find no way to explain why this happens and I believe it would be good for the whole community if anyone could figure out a way to resolve this problem :)
When I read your editorials for problems that I already solved, they make sense and I can understand them, but when it's a problem where I'm clueless(like last div2 D), your editorials are kinda useless. It's like you kinda assume someone already has the same idea as you and you just walk them through it. many people either don't have ideas, or have very wrong ideas. So i generally think you should be a bit more detailed in explaining the basic idea of your approach. Also your contests are amazing, so please don't let this discourage you from setting more rounds!
Can you elaborate on what's missing in the editorial? Unlike in 2018A - Cards Partition, here I don't find anything clearly missing.
Let me rewrite the editorial with some comments:
At some time $$$t$$$, consider the minimal interval $$$[l, r]$$$ that contains all the cities with $$$a_i \leq t$$$ (let's call it "the minimal interval at time $$$t$$$"). If this interval has length $$$> t$$$, the answer is $$$0$$$. [I think it's easy? You have to visit all the interval no later than time $$$t$$$, and if it requires times $$$> t$$$ you lose.]
Otherwise, the answer is at least $$$1$$$. A possible construction is visiting the cities in order of $$$a_i$$$ (extending the interval until you reach the city you want to visit). In this way, at time $$$t$$$ you will have conquered all the cities in the minimal interval at time $$$t$$$ (which is short enough), and possibly other cities. [This is more tricky. Maybe I could rephrase it with "a possible construction is visiting the minimal interval at time $$$1$$$, then the minimal interval at time $$$2$$$, ..., then the minimal interval at time $$$n$$$", but is it really different?]
Starting from city $$$x$$$ is equivalent to setting $$$a_x = 1$$$. After this operation, you have to guarantee that, for each $$$t$$$, the minimal interval at time $$$t$$$ is short enough. If this interval is $$$[l, r]$$$ before the operation, $$$x$$$ must be contained in $$$[r-t+1, l+t-1]$$$. So it's enough to calculate and intersect the intervals obtained at $$$t = 1, \ldots, n$$$, and print the length of the final interval. [Intuition: for each $$$t$$$, you just have one additional city to visit, and it can modify the minimal interval at time $$$t$$$.]
Is it more clear now? Should I somehow include such comments in the actual editorial?
The first point makes sense, but you could also explain why that is with comment like, "because we won't be able to reach the left-most and right-most point before time t" or something like that, so that beginners won't actually have to think why that is.
For the second point, I am not sure what exactly "visiting cities in order of a[i]" means. Sure i know that visiting cities with low first a[i] is good, but what exactly does it mean to "extend the interval". I kinda got confused here, and it took me like 5 minutes to figure out what this means exactly.
The third point was most confusing when I read the editorial at first (admittedly, i didn't read it very thoroughly, but i think a lot of people dont), and the comment that you made does help in visualizing it and thinking about it. I'd say the comments help, because it just helps get what the intuition behind the logic is. When you say " If this interval is [l,r] before the operation, x must be contained in [r−t+1,l+t−1]", that does makes sense when you write down an example and consider it, but it's alot easier if you just give the example in brackets or something like that. Also, I do understand this problem pretty well after reading the editorial now, and being more thorough, but I kinda still have no idea how to implement that, so a note which would say "you can implement this with x and y technique" would be pretty nice. Or at least find a solution which is implemented well, and has readable code and attach it.
Can you check the editorial now? About the solution code, how to make it cleaner? (It's attached at the beginning of the editorial, in case you haven't seen. I agree this is not the most intuitive place to add solution codes, but I also don't want to add 8 links to the same folder in the editorial. Can you suggest a better way?)
The difference between the old editorial and this one is insane. I think if I read this one at first, even without being thorough, I would've gotten the whole concept of the solution without having to reread anything. Great improvement. I didn't actually notice the link with the folder with the implementations. Maybe you could just submit all the problems with the official implementations after contest ends and at the end of the solution add "You can see implementation here : link of the submission" . And about making it understandable, I'm actually not quite sure. If you don't find it a hassle, you could add a few comments, but that's about it I think.
I've just read the solution, and it makes sense and I would consider it a "clean" solution. Of course this is just my subjective opinion, so it might not be as clear to someone else, but I think it's good enough even without comments or anything.
First of all, I just want to say that unlike the editorial, I really enjoyed solving Div 2 A, B, C from last contest, so I hope you make more contests.
Now for the editorial, I think there are 3 main components for the editorial of any problem: - description of the solution ( not very useful and no beginner-friendly,) - description of at least one way to find the solution ( very useful for beginners) - proofs
I think that how to write each of these parts should depend on the problem difficulty.
For example, for a Div 2 B, - The audience are beginners, so more "how to find the solution WITH A BEGINNER MIND?" and less proofs. And if you want to write some proof, make it intuitive and use simple common language - Math is ok in moderation if you add what it means
On the other hand, for a Div 1 F, I think the editorial should be written in a completely different way because the readers are masters.
So the key is to adjust your style to the level of the interested readers, And keep asking will this be easy to follow for a person with level x? or maybe more details should be added here? how an x-rated contestant may approach this problem?
Or cooperate with other people from the targeted group.
To sum up, please explain not report. And please explain HOW to find a solution or prove sth, not WHAT is the solution or proof (especially for beginner problems). And do that keeping in mind the target audience.
Can any beginner explain how they found the solutions of B and C (and maybe D)?
For example, in problem B, did you use pen and paper / draw some small examples? If yes, I think you can see that the initial points are included in $$$n-1$$$ segments, the next ones (except one) are included in $$$2(n-2)$$$ segments, etc.
idk if you consider me a beginner, but for B, i realized that for the points in between 2 x[i], the formula is the (number of selected coordinates before)*(number of selected coordinates after), and the only edge case for me was considering the actual selected coordinates themselves, which is why it took me like an extra 10 minutes. For C, I took a random example and started writing down what I would do, and it was basically just to place all cards of highest frequency first and then build all the decks upon those. And then that failed when k couldnt "fill" the hole on the top-most row. (if you consider decks as columns and their i-th cards from the bottom rows). then i realized i can just take the sum, and then check if k can fill the row for some height of decks, and i just wrote down some examples to figure out how to check that properly and figure out the formula.
Some people like when editorials have some general idea to start with, and then this idea evolves into a solution, for instance, you come up with a simple O(n^2) dp, then you try to optimize it, then you make some segment tree, and then wow actually you don't store that dp but it was useful. Although there are some problems in which you should just have an insight and get a solution, and I don't have a clear answer how I think an editorial to such problem should look like
Indeed, in the editorials of (div2) B, C, D there are some "subtasks".
Problem B:
Problem C:
Problem D:
Are these "subtasks" enough?
I think your editorial for the recent round's D1BCD is great and I would've written the same but my view may be biased as I've solved these tasks. I wrote some generic comment not meaning to criticise any of your editorials
First of all, I love your contests. they have taught me many new concepts.
Something I've never seen before but could be a game changer is adding links to similar, easier problems. If a problem feels natural to you, it's likely because you've encountered a similar one before.
Additionally maybe, its just formatting problem, your explanation contains all the details maybe just present them in more readable structured form. Segregating the ideas at the beginning itself would help. I like how Shayan does this when explaining in videos, where he break down the facts as follows:
Fact 1: The number of segments a point belongs to is given by i*(n-i). (followed by proof & explanation)
Fact 2: ..... (proof or reason)
Fact 3: ..... (proof or reason)
Then, explain how the solution is built using these facts. This way, even if I don't fully understand something, I can pinpoint which specific fact I need to read more about. If the explanation still isn't enough, I can try a dry run or do my own research. People may complain less about entire editorial if they know what is stopping them from understanding the entire answer. It also makes it easier to ask in comment section — can someone give some links or explanation for 2nd fact of 3rd problem.
Your editorials are great.
What can be improved:
For me the main issue was I feel like some steps (sometimes small) are skipped or throwing something out of no where without proving it actually that's my only problem in most editorials
edit : sometimes the small pieces problem authors miss are not as crucial or anything but it makes it harder for the reader because he has to assume something not written in the editorial which could be very missleading even if its a really small detail so i suggest using the educational rounds style where they focus on providing every piece of information instead of a short editorial containing the big parts still they sometimes miss it up (example 1895D - XOR Construction) but still for the most part their editorials are educational and very understandable
edit 2: i'll try to give my thoughts on the problem i provided above and why it was a bad editorial in my opinion , and i believe you are going to pick up the little pieces to fix later on
they claimed that b1 will be good if it generates an array with the max < n without telling us why that is (the reason is because for each number X every different number Y generates a different X^Y value so if (max < n) and we have (n — 1) distinct Y values then every number from 0 to n — 1 appeared thus making it a permutation) if this was provided in the editorial it wouldn't have taken me over 2 hours afew months ago
later on i'll add the problem that got me writing the original comment linked above and what to be fixed in it
Write down everything, treating each substep as its own task and pretend it's the local MO contest where everything have to be proven (as long as it isn't too obvious)
I don't read editorials too often, but when I read them, it usually means that I couldn't get what others consider very obvious. So, I expect the editorials to explain that obvious part to me with even more obvious and easy facts, but in many cases the editorials also skip them in perspective of an average person who could solve it.
I struggled very hard on 2018B - Speedbreaker (I passed it in 1999 ms with a very weird binary search with multisets, which I uphacked later) and I had to read the editorials (I think I read both the old and the new version). The thing I missed was that I failed to consider that only the interval for all $$$a_i \le t$$$ matters. So when I was reading it, I hoped that the editorial would explain how we can get to the conclusion that we want to consider such intervals out of the moves the problem statement suggested. Like, I could only think of "So each time I should either move to left or right, changing $$$[l,r]$$$ to either $$$[l-1,r]$$$ or $$$[l,r+1]$$$, considering all numbers and their relative distance from the current range". The editorial kind of assumes that we somehow already have this change in perspective from our moves to the cities' allowable intervals in our mind.
The hints weren't very useful to me as well:
you can probably get someone on fiverr
1$ vs 10$ vs 100$ vs 1000$ editorial !!!
If anything, I have two rules of thumb when I write editorials:
Go through every step of the solution. I won't skip any step, even when the editorial might look too long — what I desired is that the editorial is handholding the user to the goal. Sometimes omitting obvious stuff is fine — I only do so for obvious obtainable-by-reading stuff, or handing them a definition/lemma with its Wikipedia article (and/or better reliable source) for personal self-reading later on. It feels like r/eli5 to an extent.
Claim first, prove later. And prove them thoroughly. It keeps the editorial consistently structured, and still not leaving any important parts out. Those who know or are capable to figure out with just the abstract, they can skip the proof and scroll forward. Those who don't, they can take the time reading.
I think the editorial should contain rigorous proofs at least. The intuition behind a particular approach is sometimes difficult to explain, it comes through practice I believe.
It's a minor point, but if an author includes code in the editorial, it would be good if they made the structure of the code follow the logical flow of the editorial as far as possible, along with matching variable names. Having well commented ("this part of the code implements this part of the solution") and indented code helps too. I think people give up quickly on trying to understand the code otherwise.