ICPC Brain-Buster

18May12

Yesterday the annual International Collegiate Programming Contest (ICPC), sponsored by the Association for Computing Machinery (ACM), took place in Warsaw, Poland. This is a contest for three-person teams of university students. The team-oriented nature is wonderful, but also a historical artifact: when the first ICPC contest was run back in the 1970s, there were many more registered competitors than there were available computers, so making teams was the only way for everyone to participate.

Congratulations to all of the competitors! The teams on which I previously competed, Waterloo and MIT, did pretty well, securing 9th and 22nd places respectively. Harvard was the best North American team, in 7th place. The top 4 teams were very familiar names — to me at least — since they dominate the contest perennially: St. Petersburg State U; U Warsaw; Moscow Inst. Physics & Technology; and Shanghai Jiao Tong U from 1st to 4th.

Like the IOI and its national predecessors for high-school students, the problems require both a good knowledge of how to quickly code common useful algorithms, and powerful problem-solving skills. Here is the problem I liked best this year, which is elegant and challenging, yet with a simple final solution.

Blobs. You have several blobs, of different sizes. Your opponent also has several blobs. You will play the following game with them, and the question your program must solve is, who will win if both players play optimally? On your turn you can do one of three things:

  • Merge two of your blobs. They are replaced with a new blob, and the size of the new blob is the sum of the sizes of the old blobs.
  • Attack. If you have some blob Y, and your opponent has some blob O, such that the size of Y is greater than the size of O, then you can make an attack, which destroys blob O and leaves blob Y unchanged.
  • Pass.

You win the game when your opponent has no blobs left. For example, if you (the first player) have three blobs of sizes (8, 8, 3) and your opponent has (10, 5, 5), you have a winning strategy which must begin by merging your size-8 blobs into a size-16 blob. Then, no matter what your opponent does, you can attack their blobs from largest to smallest until they are all gone.

As another example, if you have two blobs (10, 6) and your opponent has (9, 8), you again have a winning strategy, but the only winning first step is to attack one of your opponent’s blobs.

The remaining details of the problem statement are,

  • you can ignore ties: the input will make it impossible for both players to have blobs of the same size.
  • there will be at most 10000 blobs per team at the start, each of size at most one trillion.
  • your program should run in less than one second.

You can see the original wording in the problem set (look at problem L) and if you want general ideas on how to solve any of the problems you can check out Per Austrin’s guide.

Figure 1. A small blob.

 

Advertisements


No Responses Yet to “ICPC Brain-Buster”

  1. Leave a Comment

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


%d bloggers like this: