Let's make a silly experiment.
For every like this post receives in the next 24 hours, I will post one tip for heuristic/bot programming contests.
I will start posting these as a thread in ~1h from now.
I could talk about those things for days, so bring it on!
For every like this post receives in the next 24 hours, I will post one tip for heuristic/bot programming contests.
I will start posting these as a thread in ~1h from now.
I could talk about those things for days, so bring it on!
This is going to be a long ride 😅
Small disclaimer first: I'm limited to 280 characters per tip. Sometimes it's going to be hard to squeeze 15 years of experience into a single tweet. A lot of details are going to be left out, etc.
Small disclaimer first: I'm limited to 280 characters per tip. Sometimes it's going to be hard to squeeze 15 years of experience into a single tweet. A lot of details are going to be left out, etc.
#0: Free tip
Everyone is unique & has different background. Each one of us struggles with different subjects.
Not every piece of advice is going to be applicable for you, but I'll try making all tips as general as possible & mention if something is situation specific.
Everyone is unique & has different background. Each one of us struggles with different subjects.
Not every piece of advice is going to be applicable for you, but I'll try making all tips as general as possible & mention if something is situation specific.
#1: In a week-long contest there's enough to do ALL of the research during the contest.
No matter how inexperienced you are, if you put a lot of effort into a single contest. You have a chance of winning it. This is in contrast to CP contests where you have to train for years.
No matter how inexperienced you are, if you put a lot of effort into a single contest. You have a chance of winning it. This is in contrast to CP contests where you have to train for years.
#2: You never need any advanced math.
There is always alternative of writing simulation code. In ~200 contests I've done, I can recall a single instance someone performed better due to math knowledge. Exception: Bayes' theorem. For reference: I don't know calculus 😅
There is always alternative of writing simulation code. In ~200 contests I've done, I can recall a single instance someone performed better due to math knowledge. Exception: Bayes' theorem. For reference: I don't know calculus 😅
#3: In heuristic ([H] from now on) contests there are only two common techniques that are worth knowing: Beam Search & Simulated Annealing.
Rarely, it's useful to have decent experience with Graph Theory, Dynamic Programming, Linear Programming & Flow Problems.
Rarely, it's useful to have decent experience with Graph Theory, Dynamic Programming, Linear Programming & Flow Problems.
#4: Touch typing is extremely important. If you can't that should be your #1 priority. It takes roughly 10-30h for most.
Touch typing gives you an ability to think about other things while coding. Reduces number of bugs, smooths out prototyping, etc.
Touch typing gives you an ability to think about other things while coding. Reduces number of bugs, smooths out prototyping, etc.
#5: H (Heuristic) vs B (Bot) contests, which ones are better?
Other than different set of standard techniques, the main difference is that H contests give you fast & precise feedback, while B are generally more fun.
You'll learn at much faster pace in H contests.
Other than different set of standard techniques, the main difference is that H contests give you fast & precise feedback, while B are generally more fun.
You'll learn at much faster pace in H contests.
#6: The best sites for contests:
H: Topcoder (marathon), AtCoder (AHC)
B: CodinGame (there's a contest going on right now!)
All sites feature good problems, fair evaluation system & community that talks about solutions post-contest.
Some sites might be rough on the UI side ;)
H: Topcoder (marathon), AtCoder (AHC)
B: CodinGame (there's a contest going on right now!)
All sites feature good problems, fair evaluation system & community that talks about solutions post-contest.
Some sites might be rough on the UI side ;)
#7: [H] Googling about the problem is generally a waste of time*
Good problem design (above sites) means that problem writers made sure that the problems are unique.
*there are rare exceptions; it might be useful to research a particular subproblem that exist
Good problem design (above sites) means that problem writers made sure that the problems are unique.
*there are rare exceptions; it might be useful to research a particular subproblem that exist
#8: For most people, the most limiting skill is prototyping speed.
With some experience, you'll always have dozens of ideas that you want to implement. The limiting factor is how quickly can you iterate through them. The faster you go, the quicker you learn about the problem
With some experience, you'll always have dozens of ideas that you want to implement. The limiting factor is how quickly can you iterate through them. The faster you go, the quicker you learn about the problem
#9: Best way to get good quickly is to focus on a single contest instead of half-assing many.
You won't learn much by only doing basic solutions. The proper learning period starts when you hit a wall and don't know how to proceed. You have to push yourself to get results.
You won't learn much by only doing basic solutions. The proper learning period starts when you hit a wall and don't know how to proceed. You have to push yourself to get results.
I'm done with food, let's go for some quick Simulated Annealing (SA) tips now:
#10: All local-search alternatives to SA are (almost always) bad.
Genetic Algorithms, Tabu Search, Ant Colony, etc. Just forgot them. They are not only less effective, but slower to implement.
#10: All local-search alternatives to SA are (almost always) bad.
Genetic Algorithms, Tabu Search, Ant Colony, etc. Just forgot them. They are not only less effective, but slower to implement.
#11: Why SA?
- You can start with Hill Climbing (HC) and convert to SA with 2 additional lines.
- Gives you ability of fast dynamic evals
- When tweaked properly has higher potential (due to fast evels) than other methods
- Allows for very fast iterations
- You can start with Hill Climbing (HC) and convert to SA with 2 additional lines.
- Gives you ability of fast dynamic evals
- When tweaked properly has higher potential (due to fast evels) than other methods
- Allows for very fast iterations
#12: Standard SA:
temp schedule: t = t_start * (t_final / t_start) ^ time_passed, where time_passed is in 0..1
acceptance (when min is better): RNG() < exp((cur_result - new_result) / t), where RNG() returns 0..1 uniformly
It's the best starting point in almost all cases
temp schedule: t = t_start * (t_final / t_start) ^ time_passed, where time_passed is in 0..1
acceptance (when min is better): RNG() < exp((cur_result - new_result) / t), where RNG() returns 0..1 uniformly
It's the best starting point in almost all cases
#13: Good SA temperature schedule is such where the acceptance rate slowly decreases.
If it's stuck on the same acceptance rate value for a long time, it won't be effective.
If it's stuck on the same acceptance rate value for a long time, it won't be effective.
#14: Things to do when it's easy to stuck in a local optimum
- very high temperatures / acc rate
- complex transition states
- (rarely) kicks
- (rarely) soft restarts (restarting temp schedule without solution)
- (rarely) multiple runs
- very high temperatures / acc rate
- complex transition states
- (rarely) kicks
- (rarely) soft restarts (restarting temp schedule without solution)
- (rarely) multiple runs
#15: Things to do when a lot of states are invalid (due to restrictions)
a) add an additional scoring component based on number of collisions that has initial weight 0 and a final weight of infinity
b) (if possible) do many short SA runs with high temp on a partial subsolution
a) add an additional scoring component based on number of collisions that has initial weight 0 and a final weight of infinity
b) (if possible) do many short SA runs with high temp on a partial subsolution
#16: Things to do when your eval is very fast:
- make sure your RNG is not a bottleneck
- make sure your exp function is not a bottleneck
- make sure your function that gets current time is not a bottleneck
That happens way more often than you may think
- make sure your RNG is not a bottleneck
- make sure your exp function is not a bottleneck
- make sure your function that gets current time is not a bottleneck
That happens way more often than you may think
#17: Overall priorities for SA:
- prototype different transition functions
- make eval function very fast (= make it dynamic)
- find proper temp schedule (usually 3-4 runs are enough)
- test a lot
- only when you're done with the above move to other things
- prototype different transition functions
- make eval function very fast (= make it dynamic)
- find proper temp schedule (usually 3-4 runs are enough)
- test a lot
- only when you're done with the above move to other things
#18: Make sure that you constantly update your best result and return your best instead of the final one.
I can't tell how many times I saw this mistake. Constantly updating your best results allows you to have a much higher final temperature.
I can't tell how many times I saw this mistake. Constantly updating your best results allows you to have a much higher final temperature.
#19: When SA is not great
- it's very easy to get stuck in local optima: check #14 for hints
- you mix simple transitions with complex ones: have a separate acceptance function for each transition
- your eval is very erratic during transtions: you're out of luck
- it's very easy to get stuck in local optima: check #14 for hints
- you mix simple transitions with complex ones: have a separate acceptance function for each transition
- your eval is very erratic during transtions: you're out of luck
Ok, enough about SA.
Contests are essentially simple feedback loops:
a) do stuff
b) get results
c) extract information
You can get better by improving any of those areas. The most neglected area by everyone is (b).
Let's focus on testing now
Contests are essentially simple feedback loops:
a) do stuff
b) get results
c) extract information
You can get better by improving any of those areas. The most neglected area by everyone is (b).
Let's focus on testing now
#20: Testing is the most neglected aspect of contests by almost everyone.
Testing is your way of getting feedback. If your testing is slow you're going to progress very slowly. If your testing is inaccurate, it's going to be very hard to figure out correct next steps.
Testing is your way of getting feedback. If your testing is slow you're going to progress very slowly. If your testing is inaccurate, it's going to be very hard to figure out correct next steps.
This will mostly focus on H, as testing in B is very hard and quite often nearly unfeasible.
#21: [H] Use a local tester.
If you're only using provisional testing for evaluation, you're making everything extremely hard for yourself. You're not saving time, you're wasting it.
#21: [H] Use a local tester.
If you're only using provisional testing for evaluation, you're making everything extremely hard for yourself. You're not saving time, you're wasting it.
#22: [H] Use a good local tester.
The absolute minimum are two functionalities:
- multithreading (ability to run multiple tests on separate threads)
- relative scoring (which is a standard on topcoder).
If you don't have your own, use mine: github.com/FakePsyho/mmte…
The absolute minimum are two functionalities:
- multithreading (ability to run multiple tests on separate threads)
- relative scoring (which is a standard on topcoder).
If you don't have your own, use mine: github.com/FakePsyho/mmte…
#23: Testing speed is often a limiting factor.
When your solution is compact and easy to extend, you can add/remove features in matter of seconds. That means at some point in the contest, testing different versions of your solutions is going to be main bottleneck.
When your solution is compact and easy to extend, you can add/remove features in matter of seconds. That means at some point in the contest, testing different versions of your solutions is going to be main bottleneck.
#24: Use external VMs for quick testing.
If you don't have a powerful machine, you can use AWS/GCP/Azure for quick testing. It takes around 1-2h to learn if you have linux knowledge. With spots, for 5$ you can get an equivalent of your laptop running for a week.
If you don't have a powerful machine, you can use AWS/GCP/Azure for quick testing. It takes around 1-2h to learn if you have linux knowledge. With spots, for 5$ you can get an equivalent of your laptop running for a week.
#25: Run your tests as often as you can.
You have a built-in end to end testing coming with your contest.
Testing is your magical command that detects that you've made a mistake somewhere. It also gives you feedback on every possible incremental change you're able to add.
You have a built-in end to end testing coming with your contest.
Testing is your magical command that detects that you've made a mistake somewhere. It also gives you feedback on every possible incremental change you're able to add.
Let's go back to general tips:
#26: Version control is bad.
You may be very experienced with git and you may feel that it doesn't slow you down. And that might be true. That being said, if you feel it's useful for you then you're bad at prototyping. Fix your prototyping skills.
#26: Version control is bad.
You may be very experienced with git and you may feel that it doesn't slow you down. And that might be true. That being said, if you feel it's useful for you then you're bad at prototyping. Fix your prototyping skills.
#27: Version control is bad. Except when running tests.
When you run tests, it's useful to save your current source files. This mostly functions as a sanity-check when you get unexpected results. Just a make short .sh/.bat script that saves source files when testing.
When you run tests, it's useful to save your current source files. This mostly functions as a sanity-check when you get unexpected results. Just a make short .sh/.bat script that saves source files when testing.
#28: If you're ever wondering if it's worth optimizing your code, you run your solution while extending the time limit.
This is a simple trick that gets used very often. Don't optimize your code if potential gains are very low.
This is a simple trick that gets used very often. Don't optimize your code if potential gains are very low.
#29: Language choice: C++ is the lone king*.
If you know what you're doing you can squeeze much more out of C++ than any other language, while macros can fix many of C++'s problems.
*I don't have experience with rust + very complex topic, so don't take this as golden standard
If you know what you're doing you can squeeze much more out of C++ than any other language, while macros can fix many of C++'s problems.
*I don't have experience with rust + very complex topic, so don't take this as golden standard
I need a break. I'll be back later though.
I won't lie, I wasn't expecting that many likes. I'm never getting to 400 tips because at that point I won't even remember what I wrote earlier 😅
In the meantime, please check out current contest on CG: codingame.com/contests/fall-…
I won't lie, I wasn't expecting that many likes. I'm never getting to 400 tips because at that point I won't even remember what I wrote earlier 😅
In the meantime, please check out current contest on CG: codingame.com/contests/fall-…
#30: You should prioritize removing bugs over anything else.
When you have bugs, your solution doesn't work the way you believe it does. This means that every time your tests run, you're getting incorrect results. Your intuition for the problem won't properly develop.
When you have bugs, your solution doesn't work the way you believe it does. This means that every time your tests run, you're getting incorrect results. Your intuition for the problem won't properly develop.
Very Important One:
#31: Every time you suddenly get results that do not align with your intuition you should investigate.
Either you have a bug (see above) or your intuition is off. For latter, you should treat this as a learning experience and figure out why you were wrong.
#31: Every time you suddenly get results that do not align with your intuition you should investigate.
Either you have a bug (see above) or your intuition is off. For latter, you should treat this as a learning experience and figure out why you were wrong.
#32: Try to keep your solution small.
More code means:
- more bugs
- remembering full solution is much more mentally demanding
- (usually) more dependencies -> costly refactoring
Most of the winning solutions are around 400-1000 lines of code.
More code means:
- more bugs
- remembering full solution is much more mentally demanding
- (usually) more dependencies -> costly refactoring
Most of the winning solutions are around 400-1000 lines of code.
#33: Read editorials after every contest you participate in.
In all of the platforms I have mentioned, (nearly) all of the top competitors describe their solution after the contest is finished. It's an incredible waste of opportunity to compete and then not read what others did.
In all of the platforms I have mentioned, (nearly) all of the top competitors describe their solution after the contest is finished. It's an incredible waste of opportunity to compete and then not read what others did.
Now, let's talk about why some people are consistently good in those contests while others consistently struggle:
#34: The obvious one first. It takes time to develop a good solution.
There's no magic trick or workaround. Over time, you'll get faster though.
#34: The obvious one first. It takes time to develop a good solution.
There's no magic trick or workaround. Over time, you'll get faster though.
#35: Execution > Idea.
You may wonder, why you often find many different approaches at the top, but all of them achieve similar scores. Executing your idea well is generally way more important than the having the perfect idea.
You may wonder, why you often find many different approaches at the top, but all of them achieve similar scores. Executing your idea well is generally way more important than the having the perfect idea.
#36: Reread the problem statement until you remember every small detail of it. Read the tester code as well.
There are often small details that you may have missed on your first reading. Read the supplied code as well, especially if it involves non-trivial logic.
There are often small details that you may have missed on your first reading. Read the supplied code as well, especially if it involves non-trivial logic.
#37: Find what motivates you.
The biggest driving factor for most competitors is the joy of self-improvement. H&B contests are mostly a solitary game where future you tries to be better than past you. Treat others competitors as a benchmark and not as your goal.
The biggest driving factor for most competitors is the joy of self-improvement. H&B contests are mostly a solitary game where future you tries to be better than past you. Treat others competitors as a benchmark and not as your goal.
#38: Don't waste your time on solutions that can't get you far.
If you know that the current solution is not able to achieve good results, there's no point in squeezing maximum value out of it.
The easiest way to end up at the top of the leaderboard is to aim high and fail.
If you know that the current solution is not able to achieve good results, there's no point in squeezing maximum value out of it.
The easiest way to end up at the top of the leaderboard is to aim high and fail.
#39: Tools increase your productivity. By a lot.
For H it's mainly a local tester. For B it's a local league system (although it's less reliable). My estimate is that after polishing my local tester (linked before) I'm spending around 30-40% less time on contests.
For H it's mainly a local tester. For B it's a local league system (although it's less reliable). My estimate is that after polishing my local tester (linked before) I'm spending around 30-40% less time on contests.
#40: Good competitors never run out of ideas.
You can get more inspiration by running tests, looking at the visualizer (H) / games (B). You get ideas by working on your solution. At the start, even the best people have no clue what's the best solution is going to be.
You can get more inspiration by running tests, looking at the visualizer (H) / games (B). You get ideas by working on your solution. At the start, even the best people have no clue what's the best solution is going to be.
Switching up again. Since a lot of people from CodeForces joined in (thanks Mike😁), let's talk about differences between your classic competitive programming (CP) and H/B contests.
For the record, while I no longer do classic CP, I was ranked 4th at topcoder at some point.
For the record, while I no longer do classic CP, I was ranked 4th at topcoder at some point.
#41: CP and H/B contests require completely different skills.
CP is a sprint, requires insane concentration and a large knowledge base
H/B are marathons, it's mostly long-term planning and creative thinking/problem solving
CP is a sprint, requires insane concentration and a large knowledge base
H/B are marathons, it's mostly long-term planning and creative thinking/problem solving
#42: In CP, your "opponent" is the problem setter. In H/B (but mostly H) your opponent is the past you.
In H/B you're never done with the problem and solving is an ongoing process. You have to fit your life between the coding sessions. It's very hard to switch between problems.
In H/B you're never done with the problem and solving is an ongoing process. You have to fit your life between the coding sessions. It's very hard to switch between problems.
#43: In CP you care about the worse case. In H/B you care about the average case.
This opens a complete new class of techniques:
- randomized algorithms
- different versions for quickly handling special cases
- pruning (early exits)
This opens a complete new class of techniques:
- randomized algorithms
- different versions for quickly handling special cases
- pruning (early exits)
#44: Being experienced in CP gives you a solid foundation for H/B contests.
While algorithmic knowledge from CP is only somewhat useful, CP is wonderful for practicing your programming language & writing bug-free code as it provides very quick iteration cycles.
While algorithmic knowledge from CP is only somewhat useful, CP is wonderful for practicing your programming language & writing bug-free code as it provides very quick iteration cycles.
#45: CP will land you a job, H/B will make you good at your job😁
A lot of companies use programming puzzles during hiring process, but beyond that CP isn't that useful. H/B contests are similar to small-scale research that you may often encounter if you join any AI company.
A lot of companies use programming puzzles during hiring process, but beyond that CP isn't that useful. H/B contests are similar to small-scale research that you may often encounter if you join any AI company.
And now tips for beginners:
#46: If you're very new to the programming I would not recommend H/B contests.
Try CP first, learn syntax of your language, learn simple algorithms like BFS/DFS, 1D DP etc. You need faster feedback cycle in order to quickly go through basics.
#46: If you're very new to the programming I would not recommend H/B contests.
Try CP first, learn syntax of your language, learn simple algorithms like BFS/DFS, 1D DP etc. You need faster feedback cycle in order to quickly go through basics.
#47: Find a contest, reserve some time for it and try to do your best.
Most probably you'll fail and that's ok. Failing is how you learn and winning teaches you nothing. Make a mental note of all the reasons why you think you didn't perform well. Find spots where you struggle.
Most probably you'll fail and that's ok. Failing is how you learn and winning teaches you nothing. Make a mental note of all the reasons why you think you didn't perform well. Find spots where you struggle.
#48: It's useful to read problems even if you don't compete in them.
When you see a new contest that looks familiar to the one you've seen before, read all of the editorials and see if anything could be applied.
By far the easiest way to perform well with little experience.
When you see a new contest that looks familiar to the one you've seen before, read all of the editorials and see if anything could be applied.
By far the easiest way to perform well with little experience.
#49: At the start of the contest focus on experimenting with (conceptually) simple solutions.
Your goal should be to develop your intuition about the problem, not to score some quick points. Quick adrenaline boost is nice, but gets you nowhere in the long term.
Your goal should be to develop your intuition about the problem, not to score some quick points. Quick adrenaline boost is nice, but gets you nowhere in the long term.
#50: Good way of evaluating potential approaches is to try to think about what kind of steps do they have to perform in order to end with a good answer.
If you believe it's not possible or very improbable then probably it's not a good approach.
If you believe it's not possible or very improbable then probably it's not a good approach.
#51: Focus on small incremental changes. Avoid rewriting your solution.
Small incremental changes = fast feedback cycle, fewer bugs, better motivation. For the record, I never rewrite my solution and rarely I'm going for longer than 10-15 minutes without testing it.
Small incremental changes = fast feedback cycle, fewer bugs, better motivation. For the record, I never rewrite my solution and rarely I'm going for longer than 10-15 minutes without testing it.
#52: Code optimization can turn bad solution into a great one.
With most iterative approaches (like SA) you need some critical number of iterations/steps before that approach yields good results. Sometimes code optimization opens up a completely new possibility.
With most iterative approaches (like SA) you need some critical number of iterations/steps before that approach yields good results. Sometimes code optimization opens up a completely new possibility.
#53: If you feel you're getting inconsistent results from your tests/games, it's usually a tell to increase the number of tests/games.
While your solution improves, you'll require more tests in order to have good testing accuracy. It's not uncommon to use 2-5K tests per run.
While your solution improves, you'll require more tests in order to have good testing accuracy. It's not uncommon to use 2-5K tests per run.
#54: Don't use python for contests.
Python is great for some uses, but it's roughly 100x slower for normal operations. You'll have to get very creative with coding/algorithms in order to get reasonable speed which means your code is going to be much more complex. Never worth it.
Python is great for some uses, but it's roughly 100x slower for normal operations. You'll have to get very creative with coding/algorithms in order to get reasonable speed which means your code is going to be much more complex. Never worth it.
Going to sleep now. I'll continue tomorrow in the same thread. For sure, I won't be able to get to 500+ tips, but I'll try to make this going for a little bit longer so stay tuned.
If you have any questions or topics that you'd like for me answer/talk about, please let me know.
If you have any questions or topics that you'd like for me answer/talk about, please let me know.
Short break for quick Q&A (not counting them):
Definitely not reviving blog, as I felt that consistent writing is my something I don't enjoy. I thought about doing some standalone articles (medium and/or github) about code optimzation & prototyping.
Definitely not reviving blog, as I felt that consistent writing is my something I don't enjoy. I thought about doing some standalone articles (medium and/or github) about code optimzation & prototyping.
https://twitter.com/aryanc403/status/1605755162215292928?s=20&t=Afw9RCoVy4Jbez_RTYsO_w
Sadly, those are luckfests and it's hard to be consistent in them
- go high risk high reward: early commit to a random idea
- full team helps
- one person focusing on test analysis might be a good idea
- single codebase, if you can
- go high risk high reward: early commit to a random idea
- full team helps
- one person focusing on test analysis might be a good idea
- single codebase, if you can
https://twitter.com/Kimi5407/status/1605811161936498688?s=20&t=Afw9RCoVy4Jbez_RTYsO_w
Use the temp schedule I've posted in #12. Start with very low temperatures and slowly increase them. The moment it starts getting worse that's your decent candidate for starting temperature.
SA is better in almost every problem. Try basic TSP.
SA is better in almost every problem. Try basic TSP.
https://twitter.com/bminaiev/status/1605747887811485696?s=20&t=Afw9RCoVy4Jbez_RTYsO_w
Not sure if you're talking about a single long running contest or participating in many different contests throughout the year.
But my answer is "I don't know". I've been burned out plenty of times. But: More experience -> More effective -> slower burnout
But my answer is "I don't know". I've been burned out plenty of times. But: More experience -> More effective -> slower burnout
https://twitter.com/BartoszKostka/status/1605752748464652288?s=20&t=Afw9RCoVy4Jbez_RTYsO_w
The times where I didn't win are usually more memorable for me, but that's just my nature.
In terms of contests, the most memorable were Challenge24 finals (either amazing or complete disasters), but sadly they are discontinued right now😥
In terms of contests, the most memorable were Challenge24 finals (either amazing or complete disasters), but sadly they are discontinued right now😥
https://twitter.com/aryanc403/status/1605750107458392065?s=20&t=Afw9RCoVy4Jbez_RTYsO_w
That was about "Version Control is useless".
In a nutshell, good prototyping means your code is structured into reusable components and you modify your solution by adding/removing components.
Git doesn't solve any problem that isn't solvable via⬆️
In a nutshell, good prototyping means your code is structured into reusable components and you modify your solution by adding/removing components.
Git doesn't solve any problem that isn't solvable via⬆️
https://twitter.com/cosminnegruseri/status/1605818216692871168?s=20&t=UObHSzXXiW_XPQ_ekYuqpA
I forgot about the cheesiest tip ever.
#55: Believe in yourself.
It's very hard to stay motivated if you'll just blindly assume that you won't perform well and it's out of your reach. I met many people that suddenly performed well just because they changed their mindset.
#55: Believe in yourself.
It's very hard to stay motivated if you'll just blindly assume that you won't perform well and it's out of your reach. I met many people that suddenly performed well just because they changed their mindset.
Time for more practical tips, let's move to common tricks for code optimization.
#56: There's no theorycrafting with code optimization. You have to run code on your target machine and measure it.
Different compiler version, different OS, different processor have huge effect.
#56: There's no theorycrafting with code optimization. You have to run code on your target machine and measure it.
Different compiler version, different OS, different processor have huge effect.
#57: Merge N-dimensional coordinates into 1D.
This is very common. Imagine you have 2D grid and you perform BFS on it. Instead of using (row, column), merge them into a single value. Reduces memory footprint, number of operations & code itself. It's usually a 10-30% speedup.
This is very common. Imagine you have 2D grid and you perform BFS on it. Instead of using (row, column), merge them into a single value. Reduces memory footprint, number of operations & code itself. It's usually a 10-30% speedup.
#58: Memory allocation is extremely slow.
Unless you're experienced with memory pooling, you generally want to have all your arrays allocated only once. Function with O(N) time & memory complexity can be up to 10-50x slower if you reallocate memory each call.
Unless you're experienced with memory pooling, you generally want to have all your arrays allocated only once. Function with O(N) time & memory complexity can be up to 10-50x slower if you reallocate memory each call.
#59: The only data structure that you really need is an array. It's very rare that you can't replace all your data with simple arrays.
That being said, data structure optimization can be considered pre-mature optimization, since it can increase complexity.
That being said, data structure optimization can be considered pre-mature optimization, since it can increase complexity.
#60: Modulo is surprisingly slow.
Honestly, I don't know why. But that's how it is.
Switching:
x = (x + y) % m
to
x += x + y
x -= x >= m ? m : 0
(assuming y < m, y > 0, m > 0)
is quite often faster
Honestly, I don't know why. But that's how it is.
Switching:
x = (x + y) % m
to
x += x + y
x -= x >= m ? m : 0
(assuming y < m, y > 0, m > 0)
is quite often faster
#61: Pre-compute everything you can and store those values in arrays.
It's not always better, but some operations might be slower than you think. For example, precalculating "x ^ y" is quite often faster than calculating it on the fly.
It's not always better, but some operations might be slower than you think. For example, precalculating "x ^ y" is quite often faster than calculating it on the fly.
#62: For large arrays, use smaller variable types if it's enough.
Memory copying/clearing only cares about the number of bytes. This also improves overall cache efficiency. Don't do it for single variables.
Memory copying/clearing only cares about the number of bytes. This also improves overall cache efficiency. Don't do it for single variables.
#63: Use "Fast-Clearing Array".
Imagine you need a boolean array with 3 different operations:
set(pos, value)
check(pos)
clear() - clears full array
Naive implementation is O(1)+O(1)+O(N), but you can use int array with a counter (clear -> counter++) to make it O(1)+O(1)+O(1).
Imagine you need a boolean array with 3 different operations:
set(pos, value)
check(pos)
clear() - clears full array
Naive implementation is O(1)+O(1)+O(N), but you can use int array with a counter (clear -> counter++) to make it O(1)+O(1)+O(1).
#64: Extend "Fast-Clearing Array".
- If each clear increases your counter by x -> you can store values in 0..x-1
- if collisions are acceptable, in many cases this can replace your sets/maps
- If each clear increases your counter by x -> you can store values in 0..x-1
- if collisions are acceptable, in many cases this can replace your sets/maps
#65: Adding special guardians/boundaries in your graphs can reduce the number of operations during pathfinding.
For example, when you run BFS on 2D grid, you can extend the grid by 1 in all directions to avoid checking for boundary condition (stepping outside of grid).
For example, when you run BFS on 2D grid, you can extend the grid by 1 in all directions to avoid checking for boundary condition (stepping outside of grid).
#66: The most important speedup you'll commonly perform is to make your algorithm dynamic.
For example if you apply SA to TSP (Traveling Salesman Problem) and your transition is move a city to another point in path, your eval should be O(1), because you only care about delta.
For example if you apply SA to TSP (Traveling Salesman Problem) and your transition is move a city to another point in path, your eval should be O(1), because you only care about delta.
#67: Measuring time is (often) costly.
The fastest way is to call rdtsc, but some sites use different way of measuring time. Commonly used gettimeofday() in c++ is a system call and on some platforms those are very expensive. There was one time when 1K calls took over 1s.
The fastest way is to call rdtsc, but some sites use different way of measuring time. Commonly used gettimeofday() in c++ is a system call and on some platforms those are very expensive. There was one time when 1K calls took over 1s.
#68: Use pruning / early exits / simplified calculations.
This doesn't happen very often, but there are cases where you simply skip some calculations. This mostly happens with your eval function where some transitions completely ruin your score and you can quickly tell that.
This doesn't happen very often, but there are cases where you simply skip some calculations. This mostly happens with your eval function where some transitions completely ruin your score and you can quickly tell that.
*awkward pause*
#69: If you're doing very heavy code optimization mirror the "judge" machine.
Having the exact version of gcc is way more important than anything else.
That being said, I generally don't advise fighting for <5% speed ups. Parameter optimization is way easier.
#69: If you're doing very heavy code optimization mirror the "judge" machine.
Having the exact version of gcc is way more important than anything else.
That being said, I generally don't advise fighting for <5% speed ups. Parameter optimization is way easier.
#70: SIMD/auto-vectorization is very powerful.
I never really use this nowadays, but it's still a powerful tool. Using SSE/AVX instruction set feels like solving mini puzzles. It's easy to outperform the best compilers, and you can get 2-20x speed up in critical places.
I never really use this nowadays, but it's still a powerful tool. Using SSE/AVX instruction set feels like solving mini puzzles. It's easy to outperform the best compilers, and you can get 2-20x speed up in critical places.
#71: [gcc] You can (mostly) override compiler flags via "#pragma GCC optimize (...)"
I have "Ofast,omit-frame-pointer,inline,unroll-all-loops". In theory, "omit-frame-pointer" is included in -O1, but it was faster 🤷. You can do HC on compiler flags 😅
I have "Ofast,omit-frame-pointer,inline,unroll-all-loops". In theory, "omit-frame-pointer" is included in -O1, but it was faster 🤷. You can do HC on compiler flags 😅
https://twitter.com/_spolsh/status/1605984379867496448?s=20&t=eEBjRCIaJQP8uJa7-AEsYw
I haven't really talked too much about bot contests specifically. Let's change that.
It's worth mentioning that B contests can have wildly different format and wildly different problems. I'll focus on CodinGame (CG) it's the only site with frequent contests.
It's worth mentioning that B contests can have wildly different format and wildly different problems. I'll focus on CodinGame (CG) it's the only site with frequent contests.
#72: There's a new concept in bot games: metagame. What is the best strategy often depends on the dominating strategies of other players. This is especially problematic in games with imperfect information.
Forget about decent evaluation of your solution.
Forget about decent evaluation of your solution.
#73: Each "test" is essentially a single 2-player game with binary outcome. Either you win or lose, no matter how big your advantage/disadvantage was.
Forget about decent evaluation of your solution.
Forget about decent evaluation of your solution.
#74: In order to be able to perform viable local tests, you need a wide spectrum of different approaches that's representative of bots on the leaderboard.
Forget about decent evaluation of your solution.
Forget about decent evaluation of your solution.
#75: Remember #20? Contests are feedback loops. When you can't effectively evaluate your solution, it's hard to quickly develop your intuition.
In bot contests you get a lot of noisy feedback and you have to make very wild guesses about the next steps.
In bot contests you get a lot of noisy feedback and you have to make very wild guesses about the next steps.
#76: Bot contests require much bigger time investment than heuristic contests.
- very weak feedback mechanism
- constantly evolving metagame
- access to all replays means that everyone has access to how your bot plays (and they can counter it)
- (often) more complex rules
- very weak feedback mechanism
- constantly evolving metagame
- access to all replays means that everyone has access to how your bot plays (and they can counter it)
- (often) more complex rules
#77: Due to interactivity they tend to be way more fun than similar heuristic contests. Despite that, I generally don't recommend bot contests as a good learning platform for newcomers.
Feedback loop is ineffective so it's harder to associate your actions with the outcome.
Feedback loop is ineffective so it's harder to associate your actions with the outcome.
#78: Most of the skills & wisdom gained from H are applicable to B contests.
Prototyping. Good workflow. Code optimization. Many of the algorithms & techniques are still applicable (beam search is still useful).
Prototyping. Good workflow. Code optimization. Many of the algorithms & techniques are still applicable (beam search is still useful).
#79: Most of the techniques fall into two types: complex state eval (aka heuristics) functions and search (beam search, rollouts, MCTS).
It highly depends on the problem which one is more viable, but you have to master both to succeed. Extreme form of state evals are NNs.
It highly depends on the problem which one is more viable, but you have to master both to succeed. Extreme form of state evals are NNs.
#80: Because the evaluation is very noisy it's often a good idea to ignore it altogether and focus on a solution that you believe will work.
Search-based solutions tend to be more metagame agnostic. You can also develop a local league system for automatic state eval adjustemnts.
Search-based solutions tend to be more metagame agnostic. You can also develop a local league system for automatic state eval adjustemnts.
Not really a tip, but I've been working on a simple local league system that would do automatic matchmaking. Somewhat similar tool to mmtester but for bot contests.
Hopefully in the near future this will be published as a PyPI package.
Hopefully in the near future this will be published as a PyPI package.
#81: [CG-specific] Usually time limit for the first turn is 1s, while it's only 50ms for future turns. It's very often useful to use the first turn to "think" for the next 2-3 turns if opponent have very limited actions.
#82: Chasing current metagame and imitating top players might give you good placement, but won't teach you too much in the long-term.
If your goal is self-improvement, try avoiding those approaches.
If your goal is self-improvement, try avoiding those approaches.
I think I have touched all of the aspects that I wanted to. Obviously, those takes are shallow compared to how much wisdom there is to share, but I'll never be able to do that with a twitter thread.
I'll leave the rest for Q&A (pls ask questions!) and maybe wrap-up.
Going 💤
I'll leave the rest for Q&A (pls ask questions!) and maybe wrap-up.
Going 💤
I don't believe I tried this anywhere recently. My past experience was that the tiny change to the loop might drastically affect how auto-vectorization is done. Because of that, I'd lean towards directly writing SIMD instrinsics. For contests, that is.
https://twitter.com/_spolsh/status/1605993720905547776?s=20&t=KQz9jhZcjP_SvJfp-_hnXA
• • •
Missing some Tweet in this thread? You can try to
force a refresh
