19 August 2005

TopCoder games

Consider the following problems (from topcoder):

  • Partition an integer multiset in as few parts as possible such that the sum of each part is at most 20. The multiset has at most 10 elements, each between 1 and 10 (inclusive).
  • How many maximal cliques are there in a graph with at most 20 nodes?
  • How many integers less than N whose decimal representation does not contain three consecutive equal digits are there?
  • Two players play with two custom dice: they have six faces but the values are integers between 1 and 100 inclusive. The first player throws his dice A times, and the second player throws his dice B times (1 <= A, B <= 200). The one with the greatest sum wins. Given A, B and the numbers written on dice faces find the win probabilities.

What do they have in common?

Each can be solved using multiple alternative strategies. But what struck me recently is the fact that all can be solved mechanically by viewing them as games. I knew that before. I was amazed, however, how long it took me to recognize that a large portion of topcoder problems are game problems.

How do you solve a game problem mechanically?

You begin by identifying state and legal moves. Then you assign values to states and decide how to compute the value of a state from the values of subsequent states, i.e. you decide how to combine values. And you're done. All you need is a recursive function that takes a state and outputs the value.

Not really. Sometimes speed is good. To that purpose you memoize the function (remember chess programs' "hash tables"?). Also you may need to exploit symmetries by normalizing the state representation; if you do this it should be the first thing to do in your function, before even checking the cache. Another way to speed things is to avoid some calls completely; this can be done for certain modes of combining values and some classic ways are branch-and-bound and alpha-beta prunning. But this later type of optimizations are seldom possible/needed in topcoder problems.

Now try to do that for the problems above.

No comments:

Post a Comment

Note: (1) You need to have third-party cookies enabled in order to comment on Blogger. (2) Better to copy your comment before hitting publish/preview. Blogger sometimes eats comments on the first try, but the second works. Crazy Blogger.