Hello everyone!
As a person who had two horrible contest, I found a common trend in both rounds. It was due to lack of good samples me believing something that felt obvious but in reality is just wrong. And I wonder, how can I avoid these mistakes in the future.
Some obvious answer, that I usually try do to on the contest, if I struggle, is stress-testing. It's a really useful tool which can really help with either finding small wrong test cases or checking some assumptions about the problem. But sometimes you can't just stress test, because I am not able to bruteforce all matrices or some other object with just absurd number of combinations. So there aren't always dumb solutions which are easy to code and somewhat efficient.
If so, then how often do you usually overcheck the assumptions that you do? I can't write down every step of my solution, as it takes too much time and after a while I'm just left confused on the mess that I've written (even though I use a tablet and technically have infinite board), but I also can't trust in every idea which comes to me (even if it feels obvious, sometimes)
May you share some ideas? Thanks in advance
Stop believing in something that is correct. Prove the correct things and disprove the incorrect.
This will become a new milestone after binary search.
my goodness what an idea how haven't I thought of that beforeIn all seriousness thanks, I guess it's the right way, and with some practise proving things becomes easier just as solving problems
Wow, first person to get > 300 upvote in comments
How to not disbelieve in something that is correct?
Seriously though, I have the exact opposite problem as yours. Sometimes, I incorrectly dismiss an idea or approach because I think it's wrong, or because I can't prove it......
Then learn how to prove things, at least give them a chance. Or stress test some idea on 10⁶ random tests if it's possible
Depending on the ratings of the problems that you work on, and also relative to your own abilities, I frequently find missing the correct ideas is not as bad. Many paths of thinking will point you to the same idea (if done sensibly), so you will look at it again sooner or later.
It is much more dangerous to incorrectly assume something is correct. If it happens early on, it corrupts all following thinking and make it impossible to recover. In particular, I am not sure which component are considered under the correct or incorrect assumption.
In short, it is not as serious of a problem.
On that note, practictall speaking a proof is only 97% valid -- you can mess up reading the statements, copying the wrong assumptions, or the proofs looks right but are subtely incorrect. There is always a risk, depending on the person it may or may not worth it to trade false negatives for false positives, but from my experience I think false positive costs way way way more.
I usually rigorously prove every step of the way after div2D (in my head), which does make me take a bit long on E and beyond but its definitely worth it
usually when i have a rough idea with the proof is when i start implementing, which starts by a few lines of comments that is the proof/algo
How do you rigorously prove all your problems? Especially greedy problems?
Hello! Have you tried not wasting time on proof? I'm very interested in what will happen if you don't prove.
wa2/wa3 and -100 delta at some point
Hello everyone!
After two horrible contests I noticed a common trend: due to lack of good samples I trusted something that felt obvious but was actually wrong.
I know stress-testing helps — writing a brute and comparing outputs can quickly reveal hidden cases. But often you can’t brute (like when objects are exponential in size). So I wonder:
How often should I double-check my assumptions? I can’t write down every step formally (too slow), but I also can’t fully trust every “obvious” idea.
For example, sometimes I assume a structure must be sorted or that $$$f(x)$$$ is monotone, but later find a counterexample.
How do you balance intuition vs. verification during contests?
Thanks in advance!