<aside> 📣 Motto: Be honest, not polite. And read the fucking problem statement.
</aside>
How you (should, usually, other disclaimers) approach a problem, and how I can help on each step if you are stuck.
| Step | Help |
|---|---|
| Read the statement | How to read problem statements |
| Notice weird, unexpected things | |
| Make a note of limitations, especially if they are low or unexpected (ask yourself: why is this limitation here? what would change if I remove it?) | Write what you noticed, I can tell if that’s all you need |
| Build a math model of the problem | |
| Answer: what am I asked to do? | Write your math model, I can tell if it is good |
| Variants of not good: incorrect, too complicated | |
| Make observations | |
| Prove lemmas | |
| If you can’t see anything, add more limitations, and try to solve more constrained (easier) version of the problem. Is there something that works for the general case too? | Write your proofs |
| I can be an intelligent duck | |
| Duck: the process of writing down the proof to be read by someone else already helps you to make it stricter and notice mistakes | |
| Intelligent: But I can additionally check it, and suggest what to try | |
| Reduce/simplify the problem using the things you have proven | Describe the reductions to me |
| I can be an intelligent duck | |
| Repeat 2 (or 3, if the reduction was significant) previous steps until you get something you know how to solve | I can tell if you need more reduction or this is already something standard |
| Recall the whole solution from the start | |
| Make sure you understand all the reductions | |
| Calculate the complexity | |
| Reread the problem statement. Did you understand the problem correctly? | |
| Think about implementation | |
| What functions do you need? | |
| Which places are tricky? What you need to remember? | |
| Which place is the heaviest by implementation? Which place is the slowest? Can you do them better/simpler? | Existence of this point is tremendous help already, I think |
| Implement the solution | |
| If not AC: | |
| Reread the code | |
| Recall the tricky places. Did you remember to do everything to handle them? | |
| Recall the solution. Is it correct? | |
| Reread the problem statement. Did you understand the problem correctly? | Implementation and debugging can’t really be taught, so just practice |
| If that didn’t help: | |
| Write stress-test | |
| If no countertest was found: Reread the problem statement. Did you understand the problem correctly? Is your stupid solution definitely stupid? Does it use any assumptions/observations from the main solution? | |
| If a countertest was found: Debug the solution on that test. Is the solution doing what it was supposed to do? Is the problem in the code or in the idea? | |
| After fixing the bug, run stress-test again. Increase the limits and run again. | |
| Get AC. Celebrate | I can order a party hat for you |
| Reflect. What could you have done better? What areas took you more time than you would like? Are there any tricks to simplify the implementation? | We can discuss your approach |
| I can suggest improvements |