How to win the South Pacific ACM ICPC regional
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
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.
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.)
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.
- 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.