[Math] How to get better at algorithmic thinking

Question

I have been practising for a an upcoming algorithmic thinking competition but have always found that when doing the past papers, I have never had enough time left to finish. I can do basically all of the questions but it just takes me a long time.

This competition doesn't test programming. Instead, it tests how you can create your own algorithms and think computationally to solve a problem.

Here are a couple of sample problems.

]4

So, do you have any tips that might help when doing these competitions or any advice that I could use while practising?

Thank you 🙂

Answer 1

user1952009 is correct that to get better at doing such questions you ultimately need to understand how to construct algorithms and prove them correct and implement them (whether on paper or in a program). However, since no one has answered this question, I'll give some answers. Note that my answers are a mix of both standard algorithms and mathematical tricks, which is not at all surprising. Developing efficient algorithms always involve mathematics.

Grid question

Look for patterns. The initial grid has at most two '1's in every row and column, but has a row with only one '1' and a column with only one '1'. That eliminates all possible answers except one. Done!

Game question

This requires a proper grasp of quantifiers. A position is losing if every move leads to a winning position for the opponent, and is winning if some move leads to a losing position for the opponent. Since the game is player-symmetric, we can discard the turn information and just look at the number of counters left of each colour. The optimal strategy is simply to choose a move to a winning position if possible. Notice that the rules enable you to make the number of white counters the same modulo $4$ as after your previous turn, and similarly for the number of black counters modulo $3$. Unravelling two moves ahead shows that you can ensure both. Since the final winning position is $(0,0)$, you can win if you can get there modulo $(4,3)$ on the very first move. If you cannot, the analysis is slightly more tricky but not hard to figure out if you think about it (simply build the game tree bottom-up from $(0,0)$; if you don't know what bottom-up is, read up on dynamic programming).

Maze question

This is a standard single-source shortest path problem, which is additionally trivial to implement on paper!