How to win the South Pacific ACM ICPC regional

From Site
Jump to: navigation, search


A note on scheduling

Suppose we represent each problem as needing a multiple of 20 minutes of a competitor's work. The competition is 15×20 minutes, and there are three on a team.

For example, represent each 20 minutes by a character (this is optimistic, for a very good team):

A          20 minutes
B          20 minutes 
cCC        1 hour
dDDD       1 hour 20
eeeeEEEEE  3 hours
fffffFFFF  3 hours
ggggGG     2 hours
hhhHH      1 hour 40
II         40 minutes
jjjJ       1 hour 20
kkkkkKKKK  3 hours

This represents the time spent working on each problem, including computer time, in upper case.

The point is: will it be necessary to get one of the three hard problems in order to win? If so, then work on one of them has to start early, by one person. You're not going to get either of E, F, K out if you start on it in the last hour.

However, if the other (11-3) problems are sufficiently hard, then the goal is to get them all out as quickly as possible, and the scheduling strategy changes. Picking this strategy requires good judgement.

Example schedule:

111222333444555
AjjjJIIhhhHH
BdDDDggggGG
cCCkkkkkKKKK

That gets out 9 problems.

(Ignore the overlapping computer time for the purposes of this discussion. In practice, people leave problems and then come back to them, to use computer time optimally, but this would obscure the idea I'm trying to illustrate.)

What might actually happen is:

111222333444555
AdDDDhhhHH
BIIjjjJ
cCCggggGG

That gets out 8 problems, and there is no way to fit in one of the hard problems. However, note that if the second contestant didn't do B, then they could have just gotten out one of the hard problems later.

Can we get 10?

111222333444555
IIjjjJkkkkkKKKK
BcCCdDDDggggGG
AhhhHHfffffFFFF

Yes, but only just. It's so compact, that we needn't worry about this possibility in practice. This is in the realm of extreme risk.

Take away: after the problems have all been read by one person (before the 2 hour mark), a decision needs to be made about which problems are attempted, and whether the team is going for one of the difficult problems. If yes, then work on it needs to begin immediately. (This feels risky at that point in the contest, but, as we have seen above, could be critical for victory.)

Real life

When we won it in 2009, in hindsight it turned out that we followed a strategy similar to the above idea. Except that there was no such planning at the time. It was an ad hoc process. I did the easy B, with some trouble, and then started on E, because that seemed to be the easiest of the two problems without a plan at that stage, and I suspected that it might be medium. Actually, it turned out to be hard, and it took me over an hour of working, and then some coding, to get it done. Meanwhile, Peter and Alex took care of a series of medium problems, and did that brilliantly. I can't remember much debugging being done that day. Everything that was coded fell into place and worked. I can clearly recall that happen only one other time: the training session before that regional.

Don't forget:

  • Chocolates, like TimeOuts or Flakes.
  • Ear plugs help me sometimes.
  • Large paper.
  • Coloured pens.
  • Pseudocode for 20 most common algorithms. Preparing it, you will become wiser.