Heuristic ([H]) or bot ([B]) contests are a killer way to improve your programming, problem-solving, and prototyping skills. It’s best to just dive in and focus on rapid improvement. Here are my notes from this tweet storm on the topic, credit to Psyho for the insights.
Getting started & mindset
- Focus on just one contest: Concentrating fully on a single contest provides deep learning, while casually participating in many yields minimal improvement.
- Believe in yourself: Sounds cheesy, but self-belief significantly impacts your motivation and performance.
- Find your motivation: Embrace the joy of self-improvement. Use other competitors as benchmarks, not targets.
Essential skills
Touch typing
Make touch typing your top priority. Spending 10-30 hours mastering this skill drastically improves prototyping speed and reduces bugs.
Quick prototyping
Your limiting factor will always be prototyping speed. Aim for a workflow that lets you rapidly iterate ideas.
Programming language choice (C++ vs. Python)
Prefer C++ due to its efficiency. Avoid Python for contests, as it’s significantly slower and more complex.
Contest types
- Heuristic (H): Quick, precise feedback and great for learning fast.
- Bot (B): Fun and interactive but requires more time and struggles with noisy feedback.
Techniques to master for heuristic contests
Essential algorithms
- Beam search & simulated annealing (SA) are foundational.
- Occasionally useful: Graph Theory, Dynamic Programming, Linear Programming, Flow Problems.
Simulated annealing (SA)
- SA usually outperforms Hill Climbing (HC). Start simple (HC), then convert to SA.
-
Recommended Temperature Schedule
t = t_start * (t_final / t_start) ^ time_passed (time_passed in 0..1)
-
Acceptance Criterion
RNG() < exp((cur_result - new_result) / t)
- Continuously track and update your best result.
- Tweak your acceptance rate to slowly decrease over time.
Handling common SA issues
-
Local optima:
- Increase temperature or acceptance rate.
- Use complex transitions, occasional kicks, soft restarts, or multiple runs.
-
Invalid states:
- Add a scoring penalty component or perform short, high-temp runs on partial subsolutions.
-
Fast evaluations:
- Ensure your RNG, exp function, and time-fetching functions aren’t bottlenecks.
Optimization & testing
- Testing Is Critical: Fast, accurate testing ensures rapid improvement.
- Local Tester: Use multithreading and relative scoring. Start with Psyho’s Tester if you don’t have one.
- External Testing (VMs): AWS/GCP/Azure can quickly and cheaply enhance testing capabilities.
- Frequent Testing: Test as often as possible to detect mistakes and gather incremental feedback.
Version control & workflow
- Avoid traditional version control systems during active prototyping to keep your workflow lean. However, save snapshots when running critical tests.
- Optimize your code only when clear performance gains are evident.
Bot contests insights
- Bot contests have a metagame dynamic and strategies often depend on other players’ actions.
- Recognize that feedback is binary (win/lose), making accurate evaluation challenging.
- Bot contests generally require more time investment due to complexity and metagame evolution.
- Develop or use a local league testing system to handle evaluation noise effectively.
Workflow tips
- Read the problem statement carefully: Memorize small details and review tester code.
- Run Extended Time Limit Tests: Before optimizing, first see if your solution benefits significantly from additional execution time.
- Merge Coordinates: Combine N-dimensional coordinates into a single dimension to optimize performance (10-30% speedup).
Differences between competitive programming (CP) and H/B
- Competitive programming (CP): Focused on worst-case scenarios, fast sprints, and large algorithmic knowledge base.
- Heuristic/Bot (H/B) contests: Focused on average cases, creative problem-solving, long-term planning, and iterative improvement.
How beginners can improve quickly
- Start with simpler competitive programming to learn syntax and basic algorithms.
- Regularly review problems and editorials even if you don’t compete.
- Experiment initially with conceptually simple solutions to build intuition.
- Increase the number of tests if results are inconsistent.
Succeeding long-term
- Aim high: Don’t waste time optimizing solutions that can’t win.
- Develop robust tools: Enhance productivity with effective local testers and automated evaluation systems.
Focus on rapid improvement of your performance and along the way you’ll discover this is also probably the best hack to significantly improve your programming, problem solving and prototyping skills.
