cp_qs_reading
- Think in terms of a math model.
- Writing things down never hurts. It’s a good way to think.
- Shorter = better.
- Simpler = better.
- Focus on constraints.
- Nothing in the problem statement is irrelevant. (Except for the story.)
- Find patterns.
How to come up with solutions
- Remember that brute force is a solution.
- Think of the simplest solution. (It’s probably the best.)
- Think of a solution that is slightly better than the simplest solution.
- Think about special cases. (n = 1, n = 2, n = 3, n = 4, etc.)
- Suppose I did find such a solution, what would it look like? What characteristics it would have? Can we toy around with such a solution so that it remains optimal?
On the correctness of algorithms
-
Academic proofs usually tend to be as rigorous as possible, and are carefully verified by other experts in the field, to be objectively certain of its correctness. Clearly that is not a level of rigor you need while solving a Codeforces problem. You only need to prove it to yourself.
-
An easy way to sanity check your proof is. Think of every step you took while proving. If you wanted to justify to an opponent you were correct, what would the opponent try to argue against. If you think you can’t justify your reasoning over his to a jury without reasonable doubt, your proof needs to be more specific.