Three CS problem-solving strategies exercise sets

The preparations for the ACM ICPC World Finals 2015 in Morocco are in full swing, and so is the training for by with the 125 or so 3-person teams selected of over 30000 contestants who participated in the various selection rounds across the world. While a lot comes down to “practice, practice, practice” all the hard problems you can find, and learning more algorithms and maths, there’s also work to do on refining one’s team strategy and problem solving skills. For the latter, Steven and Felix Halim’s Competitive Programming book comes in handy (as coach at least). Instead of going back-to-back through the book and do the problems listed in the designated problems solving paradigm categories, I turned it around, and selected problems of which the students had to figure out which problem solving paradigm was the right one (Greedy, DP, ad hoc, etc., and more detailed, such as geometry, shortest path, etc.). I’ve made three sets of increasing difficulty:

1. ‘easy’, where most of them can be solved with one problem solving paradigm (also useful for those who are preparing for the Standard Bank IT Challenge ‘heats’ on May 16);
2. ‘medium’, where most of them can be solved with two problem solving paradigms combined;
3. ‘hard’, where most of the problems have appeared in a World Final.

The (direction of the) solutions are on the last page of each pdf, including the UVa Online Judge number, so you can implement and test your solution as well.

I did change some of the problem descriptions for various reasons:

• Localization of the problem description to South Africa: among others, ‘Durban prawns’ (big fat cockroaches are endemic there), ‘nuts for nuts’ (we do have squirrels on campus), ‘shopping for operas’ (Amazon gave up delivering in SA, because so much packets were lost), and some characters got different names.
• Changed story line: ‘charming canines’ (disagreeable storyline in original), and some now have female characters (cf. mostly male or none).
• To make the title an alliteration, like the other titles in the problem set: ‘colliding catamarans’ and ‘cult caps’.

Happy solving 🙂

Advertisement