sdyakonov's blog

Make proofs
By sdyakonov, 7 months ago, In English

I would like to invite the authors to prove their solutions always. If you have written the following in your editorial, please write a strong proof:

"It is always possible" or "We can show that" — 1965C - Folding Strip

"The sufficiency of this condition is obvious, and the necessity is left as an exercise to the reader" — 1954B - Make It Ugly

"The optimal strategy will be" — I will not show an example, but it occurs without proof in many tasks.

and many more...

As a master, I can't understand simple things either. I also often saw grandmasters who did not understand and wrote in the comments to be explained to them. I have friends in real life who don't solve codeforces for this reason.

P.S: 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 :)

  • Vote: I like it
  • +533
  • Vote: I do not like it

»
7 months ago, # |
  Vote: I like it +70 Vote: I do not like it

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

→ Reply
»
7 months ago, # |
  Vote: I like it +34 Vote: I do not like it

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.

→ Reply
  • »
    »
    7 months ago, # ^ |
    ← Rev. 2   Vote: I like it +39 Vote: I do not like it

    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 :)

    → Reply
»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

or atleast there should be hints.

→ Reply
»
7 months ago, # |
  Vote: I like it +24 Vote: I do not like it

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)

→ Reply
»
7 months ago, # |
  Vote: I like it +61 Vote: I do not like it

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?

→ Reply
  • »
    »
    7 months ago, # ^ |
      Vote: I like it +41 Vote: I do not like it

    I always understand Tourist's or Jiangly's codes better than the ones in editorial

    → Reply
    • »
      »
      »
      7 months ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      I am also learning from Um_nik, Benq, Peter and Vercingetorix source codes.
      They write extremely clear code.

      → Reply
    • »
      »
      »
      7 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yes, sir. Gennady's code is so clean...it's a beauty to read.

      → Reply
  • »
    »
    7 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
»
7 months ago, # |
  Vote: I like it +21 Vote: I do not like it

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.

→ Reply
»
7 months ago, # |
  Vote: I like it +10 Vote: I do not like it

100% agree

→ Reply
»
7 months ago, # |
  Vote: I like it +8 Vote: I do not like it

"Это всегда возможно" — 1965C — Складывание полоски

Если ты про разбор, там же буквально в следующем предложении написано почему...

А в условии я так и вовсе не нашёл такого, или похожего предложения

Eng:

"It is always possible — 1965C"

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

→ Reply
  • »
    »
    7 months ago, # ^ |
    ← Rev. 2   Vote: I like it +43 Vote: I do not like it

    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.

    → Reply
»
7 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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.

→ Reply
»
7 months ago, # |
← Rev. 2   Vote: I like it +27 Vote: I do not like it

proved by ac

→ Reply
»
7 months ago, # |
  Vote: I like it +1 Vote: I do not like it

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?

→ Reply
  • »
    »
    7 months ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    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://mirror.codeforces.com/blog/entry/90477, where the greedy algorithm is just stated as-is, and then see lior5654's very helpful blog at https://mirror.codeforces.com/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

    → Reply
    • »
      »
      »
      7 months ago, # ^ |
        Vote: I like it +28 Vote: I do not like it

      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.

      → Reply
    • »
      »
      »
      6 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      3 years later, someone found that blog useful. Thank you hashman!

      → Reply
      • »
        »
        »
        »
        6 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        :) You're welcome!

        Thanks for writing such a nice blog!

        → Reply
  • »
    »
    7 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      7 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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...

      → Reply
»
7 months ago, # |
← Rev. 2   Vote: I like it +10 Vote: I do not like it

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.

→ Reply
»
7 months ago, # |
← Rev. 2   Vote: I like it -10 Vote: I do not like it

duck.

→ Reply
»
7 months ago, # |
  Vote: I like it +86 Vote: I do not like it

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.

→ Reply
»
6 months ago, # |
  Vote: I like it -25 Vote: I do not like it

I think writers should get less money if the editorial is unreadable or without any proof.

→ Reply
  • »
    »
    6 months ago, # ^ |
    ← Rev. 2   Vote: I like it -28 Vote: I do not like it

    They don't get any money either way. ( alright i was wrong, they do get paid MB)

    → Reply