1.During contest, 2. In practice mode, and 3.after reading editorial. Sometimes, when I can't prove the correctness of the approach of the editorial(because the editorial says "the proof is obvious", and skips the proof entirely), and there aren't any proofs in comments section too. I can't decide how much time should be spent thinking about the proof. I think and think until and unless I am able to prove it. Is this the right thing to do, even if it takes a few days sometimes?
During contest
I try to disprove my approach with test cases instead of looking for mathematical proof.
During practice
I try to think of a proper proof, then try to disprove the proof with test cases.
Editorial I try to think of a proper proof, then try to disprove the proof with test cases.
Such an effective solution to improve logical reasoning skills! Wow
I applaud you, sir. I would have expected a LOT of downvotes.
It seems like you got what you expected.
Auto comment: topic has been updated by I_love_Captain_America (previous revision, new revision, compare).
1. During contest
I think the best thing to do is to quickly write a brute force solution and use stress testing to see if there are some counter examples with small test cases.
2. In practice mode
In this case maybe asking for a proof in the comments is good. However you can still ask someone, I think there will be at least one guy who will help you. A few guys have asked me for some problems that I had already solved and I never ignored anyone :)
3. After reading editorial
The first thing to do is to downvote the editorial. Then do the same as point 2 :)
Thanks for the advice :)
About downvoting the editorial for "the proof is obvious". I agree that it's not nice to see these words when you don't see the proof at all. But think before downvoting. Editorials can describe everything because they would be extremely long. There must be some limit what to describe/prove. For a problem about the expected value an editorialist should assume that contestants are familiar with the linearity of the expected value. It's required when you want to solve most of problems about it. The harder problem, the harder proofs should be skipped. In medium problems it's not necessary to say why two-pointers can be used — though maybe the formal proof of the monocity requires a few minutes of thinking. The same applies for proofs not related to techniques but it's harder for me to give examples.
Don't treat "the proof is easy" as the evilness or laziness of the guy who has written the editorial (it's possible though). Try to prove it by yourself and ask in comments if you don't succeed.
And about the question from the blog. If you can code fast then don't hesitate to write the brute force and run your solution (or only one function/part) against it. With more experience you will get better. You will prove harder lemmas and I guess you will have better intuition.
I ask in comments. But people only reply to those comments when its from a fresh contest, otherwise people don't even open the blog to see who commented. And sometimes the proof isn't at all obvious.
Yeah, I know we should respect each other. I rarely downvote anything, I just skip it if I don't like it unless I find something offensive.
So getting back to the question about the editorials, I agree with all that you said. For example, I should not act like "Oh man, I got nothing from the solution of Div1-E, let's downvote that so-called editorial, who the hell wrote that sh*t?!" since I am simply not experienced enough to solve Div1-E and it's not author's fault so I won't do that :)
However, the case I meant is a bit different. I have seen a few times things like "It's obvious that the following greedy algorithm works: < sth >", "We can easily observe that it's optimal to do < sth > and this solves the problem". I mean if it was that obvious, why would I read editorial and moreover why would you give that as a problem :) And yes, of course there are some exceptions, I bet almost all div2 problems look obvious to you but still a little proof won't be unnecessary :)
Proving the correctness of an algorithm (especially greedy) is difficult, since it requires some mathematics skills. However, in competitive programming we only have to provide a solution which passes all tests, not to prove it.
Here's my strategy during contest. Whenever I come up with a greedy algorithm, I try to imagine the correctness intuitively instead of proving it mathematically. If I can't hack it after 5-7 minutes, start to code it. Remember, gambling in this case is necessary, as solving problems quickly gives more points. A small trick here is, an "easy" problem is more likely to have a greedy solution, so pay attention to the number of people solved it. If I'm solving a Div.1 A problem with ~200 people solved, my greedy solution has high probability to be correct. In contrast, if I'm solving a Div.1 E problem with ~20 people solved, I should try to think again.
About after contest: If you are curious, you can read the prove or think yourself deeply about the solution. However, spend at most 30-40 minutes, as I think the main goal of solving problems is to "Accepted"
Do you have another point of view? All your comments are highly appreciated. :D
But if you can prove correctness, it shows how strong your reasoning is, because many people generally get hunches and intuitions about problem's solution, but not all those intuitions are correct.
In contest, I don't expect to be able to prove, and use intuition, like you said.
From a problem setter's p.o.v, he will have to prove his solutions before putting them in a contest. As participants, we can hit and try, but it is not the perfect way. I mean to say "understanding" proof is important part of solving.