(Video lecture) Problem solving tactics for programming competitions: search and optimisation

From Site
Jump to: navigation, search

A tutorial that was part of the preparation for the South Pacific regional 2010 round of the ACM ICPC. This was one of several training sessions at The University of Western Australia that year.

Problem solving tactics for the ACM ICPC programming competition: search and optimisation from Evgeni Sergeev on Vimeo.

In this session, my goal was to provide some insight into solving medium-to-hard problems which require more than a folklore programming competition solution, such as Dijkstra's algorithm or Floyd-Warshall. Also, I avoided dynamic programming.

I am convinced that the only way to learn more about problem solving is to solve more problems. That is why the lecture is problem-driven: I provide example problems before explaining what it is they illustrate, not after. It is best if the viewer will attempt to solve each problem before I explain the solution. For the live version of this tutorial, I made a handout that contained most of the problems I was going to cover, and this was sent out to the audience a week before the event.

In arbitrary order, some of the problem solving strategies and themes:

  • Binary search, especially where it's not alluded to in the problem.
  • Thinking in terms of an invariant.
  • Hill-climbing by means of inequalities.
  • Combinatorial enumeration.
  • Greedy algorithms.
  • Optimisation by exploiting known properties of the function being optimised.
  • Sliding min.