Hello everyone,
in this blog I'm trying to convince you that editorials are useful, especially if you read them "correctly".
"Algorithm $$$1$$$" vs "Algorithm $$$2$$$"
This is what many users do when reading the editorial for one problem (let's call it "algorithm $$$1$$$"):
- Read it.
- Repeat until able to implement the solution.
- Implement the solution; possibly forget about any previous attempt to solve that problem without editorial, and any detail in the editorial that seems unrelated to the implementation of the solution.
- Possibly, read the comments trying to find out how it is possible to come up with the solution in the editorial.
This is what you should do in my opinion (let's call it "algorithm $$$2$$$"):
- Keep the editorial open until you are able to implement the solution, using both your ideas and editorial's ideas: sometimes, this just means opening the editorial for $$$1$$$ second, because you had already found most of the ideas on your own.
- Implement the solution.
- Re-read the editorial carefully, and pretend you can modify it; ask yourself which parts of the editorial you would modify.
- Possibly, read the comments to find additional insights / ideas.
(I'm not saying "algorithm $$$2$$$" is the best way to use editorials. It's just a method that works for me, and seems strictly better than "algorithm $$$1$$$". Feel free to find your own way to use editorials.)
Examples:
1909B - Make Almost Equal With Mod
Algorithm $$$1$$$:
- Read the editorial.
- Understand that, for some unintuitive reason (i.e., some math formulas), you only need to check $$$k = 2^i$$$.
- Implement the solution.
- Read the comments; find out that an alternative solution is printing $$$k = 2 \cdot \gcd(|a_i - a_{i+1}|)$$$. Convince yourself that you could come up with that by trial and error, and lots of small examples on paper (i.e., do some "proof by examples").
Algorithm $$$2$$$:
- Look at the picture for some time (between $$$1$$$ second and $$$5$$$ minutes), understand what's going on, understand the solution.
- Implement the solution.
- Re-read the editorial carefully. Read the comments and find out that an alternative solution is printing $$$k = 2 \cdot \gcd(|a_i - a_{i+1}|) =: 2g$$$. This seems a completely different solution, but let's check if you can use the editorial to prove it fast.
- We have to prove $$$f(2g) = 2$$$. But $$$f(g) = 1$$$ because all the $$$a_i$$$ modulo $$$g$$$ are the same. Then, either $$$f(2g) = 1$$$ or $$$f(2g) = 2$$$ (according to the editorial). But $$$f(2g) \neq 1$$$ because otherwise $$$\gcd(|a_i - a_{i+1}|)$$$ would be a multiple of $$$2g$$$.
With both algorithm $$$1$$$ and algorithm $$$2$$$ you would learn two solutions, but only with algorithm $$$2$$$ you would have a "full" understanding of them.
- With algorithm $$$1$$$, you could get conclusions such as "when number $$$2$$$ appears in the statement, consider binary representation" or "when $$$\text{mod}$$$ appears in the statement, consider $$$\text{gcd}$$$" which seem random and not so practical.
- With algorithm $$$2$$$, you have an intuitive visualization and an actual proof of the solution. You have also used the proof in the editorial to prove another (seemingly unrelated) solution (so proofs are not useless!). You learned the "binary" trick, but you also got better at proving stuff.
1909C - Heavy Intervals
Algorithm $$$1$$$:
- Read the editorial.
- Understand that, for some unintuitive reason (i.e., a proof which seems unnecessarily long), you need a bracket matching.
- Implement the solution.
- Read the comments; find out that many people tried to sort $$$l$$$ and $$$r$$$ in ascending order, but somehow it does not work.
Algorithm $$$2$$$:
- Look at the picture for some time (between $$$1$$$ second and $$$5$$$ minutes), understand what's going on, understand the solution.
- Implement the solution.
- Re-read the editorial carefully. Ask yourself why the proof is so long. In particular, why do we need "Keep swapping endpoints until you get the "regular" bracket matching. You can show that the process ends in a finite number of steps"? Can't you just swap a single pair of endpoints to show that intersecting segments are never optimal?
Spoiler
- Read the comments; find out that many people tried to sort $$$l$$$ and $$$r$$$ in ascending order. Realize a fun fact: sorting $$$l$$$ and $$$r$$$ in ascending order is the worst possible ordering (assuming you sort $$$c$$$ correctly).
Conclusions
Editorials are not evil! But, if you are not improving, ask yourself if you are reading them correctly.
Great tutorial!
Can someone please write a Tutorial on how to read Tutorials? I can't seem to understand this one very clearly...
My approach towards editorials is quite different from what's mentioned here, so here it is:
In this process, remember to try to adapt the solution towards your solution too, rather than just following the editorial step by step. While the editorial solution might have value as a general problem-solving pattern, it is more important to be able to come up with it on your own.
In general, also try to follow the ideas/tips in this blog.
This is a more arduous process than most people follow while reading editorials, but I believe this makes problems much more memorable and easier to learn from, and brings out the most of each editorial.
what if i get time limit
That means you still have not completely gotten to the solution yet. Most likely your time complexity is wrong — the editorial will mention the intended time complexity and how to achieve it, whenever non-obvious. If your solution (and time complexity) matches the editorial, then check your implementation and try to fix it on your own first. If it doesn't work out, look into the sample implementation (and CF comments/other people's implementations) for some tricks that make it faster.
Love this. Although I am gray af, the thing you said about adapting the editorial's solution towards your own solution is pure gold. The satisfaction/happiness when you get the editorial to fir into your own intuition model. Ah, pure Eureka.
what's your opinion and/or threshold on reading editorials at all
I accidentally read the spoiler, specifically "the process ends in a finite number of steps." In fact, it could be proven easily: a very common argument is to define a semi-invariant and show that it always increases/decreases.
In our case, the sum of the squares of the lengths of segments is the key: let's say $$$a$$$ and $$$b$$$ are the lengths. Then, $$$a^2 + b^2 = \frac12((a + b)^2 + (a - b)^2)$$$, and by increasing the difference $$$|a - b|$$$, you always increase the sum of the squares. To finish the proof, one should either notice that there is only a finite number of configurations (and therefore, a finite number of sums of the squares), or note that it is bounded and integral.
Thanks a lot for the proof! It's more elegant than I expected, and I will add it to the official editorial.
with your eyes
No need to waste time implementing the solution, save some time and move to the next editorial
I used to do that (I "solved" the entire USACO Guide Gold the month before IOI without implementing anything), but implementation became my bottleneck. Then I restarted implementing, and now I'm relatively slow at thinking.
If you are confident you are currently much better at implementing than at thinking, I think it's ok to skip implementations.
Slow ! Come on You're a grandmaster
One thing I experience is , If I thinked enough about a problem and tried various approaches understanding the editorial is most of the time not an issue , There were even numerous times in which I got the solution just by seeing 1 sentence. This isnt the case for problems I didnt thinked about enough , it feels like editorial is making random things and it only makes sense if I think on the editorial long enough. So I think the takeaway is , spend time on problems.
note : this is the case for problems with relatively hard difficulty , you can miss something in a easy problem and when you check the editorial you can get the solution even if you didnt spent much time.
Thank you for providing hints in the editorials. Editorials should do this more often. Hints improve the learning experience a lot.
From solution for B:
auto good = [&](vector<ll> a, ll k).Why not
auto good = [n, &a](ll k)?The first step is to read hints
can someone explain how does the picture and the swapping endpoints works at the last problem ? I don't understand (to show that intersecting segments are never optimal) I think that any random matching will make them intersecting. do you mean that the less intersected point the better the solution?
Atfirst I thought they are not evil, but someone changed my opinion by making them as irritating as possible, then I formed a opinion they are evil and even 1 in 10 times they are supposed to irritate, I never trusted even the other 9 times and finally i reached to the point where, if i don't understand just reading once, it is supposed to irritate me even it is supposed not to irritate me I'm just saying Editorial as an example But everything in my life is becoming same as editorial
I gofor awalk irritate me, I gofor a haor cut irritate me,If I go for a movie irritate me,If I go home irritate me,If I watch youtube irritate me,If I read newspaper irrotate me,If I watch TV irritate me,If I order something irritate me If I got to bathroom irritate me,If on the wifi irritate me,If i charge the phone irritate me,If I walk inside my house irritate me,If I just stand at my house and watch irritate me,If I read editorial irritat e me,If I comment irritate me until now they just used my eyes to irritate now using my ears to irritate and this is happening every minute everyhour every day This are called small hiccups see the big picture I dont want anything I want back my peace of Mind which I lost completely since 2 years Even before I didn't have but it better than hell If that big picture costs my peace of mind. I am happy to not even have it.Nomatter how big the picture is,whatever it may be,Nobody can replace 2 years of irritation and that worth only when one feels its worth it I am not intrested in any big picture I am done with getting irritated every second of my life
seems like a you problem. please get a mental health counsellor and/or some friends
Even things which you think are supposed to offset my irritation are also just irritating me In one sentence "Your existance itself is just irritating to me"