Я хотел бы предложить авторам доказывать свои решения. Если вы написали следующее в своей редакционной статье, пожалуйста, приведите убедительные доказательства:
"Это всегда возможно" или "Мы можем показать" — 1965C - Складывание полоски
"Достаточность этого условия очевидна, а необходимость оставлена читателю в качестве упражнения" — 1954B - Сделай его некрасивым
"Оптимальной стратегией будет" — я не буду приводить пример, но это встречается без доказательств во многих задачах.
и многое другое...
Как мастер/призер всош по информатике, я тоже не могу понять простых вещей. Я также часто видел гроссмейстеров, которые не понимали и писали в комментариях, чтобы им объяснили. У меня есть друзья в реальной жизни, которые не решают codeforces по этой причине.
Please suggest other options when the authors did not want to prove solutions.
For me, the funniest thing was — "The sufficiency of this condition is obvious, and the necessity is left as an exercise to the reader" which I gave in the blog as a basic example
Yeah, it almost always happens that someone in the comments section explains it far better than the editorial writers. I often wonder why the editorial writers can't explain their solutions in such a way.
I also did an unofficial contest as an author. link
Proofs take big time, and other things such as developing tasks and communicating with the coordinator (my friends spent a year on the official round) take a huge amount of time. Because of this, I do not condemn the authors.
This blog is like a recommendation because this problem is very common. I understand that most authors do not do the contest for money, but this problem of editorial articles can also be eliminated :)
or atleast there should be hints.
Honestly, I do really want to see the proof of the 1965C code, which was given as an example in the editorial, and I would really appreciate if someone could explain it more clearly, because the logic of the code is not obvious to me at all, even after taking into account the editorial to this problem (even more — the idea of the problem is absolutely clear and obvious to me, but not the realization given by the authors)
Another problem — unclear codes to the tasks. Besides the fact that solutions are without proofs, codes to the tasks are also bad. What's the problem to write clear, understandable code?
I always understand Tourist's or Jiangly's codes better than the ones in editorial
I am also learning from Um_nik, Benq, Peter and Vercingetorix source codes.
They write extremely clear code.
Yes, sir. Gennady's code is so clean...it's a beauty to read.
Yeah, authors need to stop using their templates in their code. I have to keep scrolling through their template to check what their variable means. Also, write meaningful variable names and add proper indentation to your code when you are writing a piece of code which will be read by thousands of people.Please follow basic software engineering principles.
Agreed. It will also be cool, if there is a discussion section per problem, where people can share their insights, observations, proofs or intuitions, just like Luogu.
100% agree
Если ты про разбор, там же буквально в следующем предложении написано почему...
А в условии я так и вовсе не нашёл такого, или похожего предложения
Eng:
If you mean editorial, the very next sentence from it explains why... If you mean problem statement, I didn't even find such sentence there
These examples were taken as the most common(I didn't want to offend these particular tasks and authors). Yes, it is explained there, but for me personally, when I read the full editorial, I thought that most of the statements are at the level of: "Trust me brother". And this problem has often occurred to me in the last nine months, when I solve more hard tasks.
I actually agree with you that 1965C is a bit unclear (around the optimality part), but you picked the worst part of the proof to criticize lol
picture
Just showing that the algorithm produces a valid string is explained very clearly.
proved by ac
Part of the issue is it's incredibly time-consuming and not very rewarding to write a very rigorous proof.
In my paper I used to have a one-page proof blowing up to five pages by filling in all the details rather than writing 'obviously' etc. In fact, I invite you to write out one of the proofs you think are insufficient in a rigorous manner and see how long and how much time it takes you.
But difficulty does not preclude good practice. Should the community devote more time to provide a clear editorial? Probably. The problem is always more like who should do the task?
I don't believe in proofs very much, but I also believe that proofs of a lot of problems (especially greedy algorithms) are severely lacking right now. They're basically like, trust me bro. Actually, I've seen a pretty helpful website called CP Notes that allows users to write their own notes (editorial) for a problem in which they think the editorial is not possible to understand. As an example, take problem D of https://codeforces.net/blog/entry/90477, where the greedy algorithm is just stated as-is, and then see lior5654's very helpful blog at https://codeforces.net/blog/entry/90476 and https://cp-notes.com/notes/fivesixfivefour/CodeForces/1521/D, which has a full proof for the greedy they use. Ok well to be fair, some people proved it in the comments, and this is a 2500, so this proof probably should be doable if you're doing 2500s, but still like, you need to have a proof (even just a sketch) for your own sake because it's really easy to trick yourself into thinking "oh this greedy obviously works" when it really doesn't and then you get an NP hard problem at problem C cough cough
I think as much I hate CodeChef, I gotta give it one thing: its editorials are really nice to read, because the author != editorialist, the editorialist is someone who specializes in writing editorials. Maybe the author doesn't have enough time, or doesn't know enough LaTeX to write a good editorial, or doesn't know English that well. That's no problem! Just hire/volunteer three or four editorialists who are reasonably experienced (maybe IM+?), and who know how to write a good editorial, know how to write LaTeX, know english, know how to write proofs that are not just "trust me bro". I'm pretty sure a lot of people would be willing to do this sort of thing, and it would really improve the quality of practice on CF.
3 years later, someone found that blog useful. Thank you hashman!
:) You're welcome!
Thanks for writing such a nice blog!
Personally, I have to know at least some intuition about how the authors came to this. But I don't like it at all when the authors just said a statement and continued the editorial.
If the authors say a statement like on CodeTON 8 F, I understand that there is a lot of mathematics to prove it. But maybe then at least write that we checked it with stress testing? And even here they can point out intuitively that the root reduces the change quite quickly.
But of course, it is necessary to prove greed, it is very important for the community so that people begin to understand how greed is built and how to use the "principle of the extreme", for example.
Intuition is even less expressible than the proof.
I can tell you that I looked at C for ten minutes and randomly guessed that the greedy works, but I am not sure that helps you -- I can only say something like I guessed the most convenient thing that, if true, helps me solve the problem, and it's not very different from trust me bro.
If it's a proof I can at least try to be rigorous. I think useful intuition is extremely hard to express...
I see an example in CodeTON Round 8 F there were 2 facts (shown as key "observations"):
One can always add floors to the square root
The square root only propagates at most 6 steps
Those 2 facts were left completely unproven in the editorial. Also the editorial is hard to read, and I can't understand it clearly, but it is not as important as the 2 unproven facts.
duck.
Absolutely agree! And also when newcomers see such lines, they get a feeling that it is not that important to prove their solutions, and it is ok to guess which doesn't lead them good places.
I think writers should get less money if the editorial is unreadable or without any proof.
They don't get any money either way. ( alright i was wrong, they do get paid MB)