If you are a contestant, you can be relaxed and you can do anything (except for cheating). It's perfectly fine if you just guess the solution and submit it without knowing why (though personally I don't find it very beautiful). However, if you are a writer, you need to prove your solution. Here is the list of things you have to prove:
1. Correctness.
Does your solution always return correct answers for all possible valid inputs?
- GOOD: Strict proof.
- BAD: My intuition tells that this is correct!
- BAD: I tried really hard to come up with counterexamples, but I couldn't. It must be correct!
2. Time Complexity.
Does your solution always run in time for all possible valid inputs?
- GOOD: It's O(n2) and the constraints say n ≤ 1000. It should work.
- GOOD: For this problem we can prove that the slowest case is xxx. Experimentally, my solution works for the input xxx under the given TL.
- BAD: I tried really hard to generate various testcases, and my solution passed all cases!
3. Randomized Algorithms.
Randomized algorithms are not hackish ways of solving problems. The writers should prove that for any valid input, the intended solution works correctly with very high probability. Please check here for an example of such proof. Another example is Rolling Hash: please check here. Note that, for example when we compute 105 hashes for strings of lengths 105, you need four hashes of prime modulo around 109, not two. (Practically two works but we can't prove that).
4. Precision.
Especially in geometry problems, we sometimes use epsilons. However writers should be careful about the use of epsilons.
- GOOD: We know |b| and |d| are up to 104. Let's use eps = 10 - 9 for comparing two fractions a / b and c / d.
- BAD: Let's use eps = 10 - 9! (without reasons)
When the intended solution uses complicated double operations (like sqrt, trigonometry, log, lots of fractions, etc.) such analysis may be hard. In this case, one possible way is to add constraints like "even if we move a point by up to 10 - 3, the answer doesn't change".
