2015 Pacific Northwest Regional Post-mortem

Post date: Nov 15, 2015 9:08:38 AM

While our corpses are fresh we might as well figure out what happened to UBC! at regionals. (I'm going to discuss problems freely here, so if you want to do the problem set for practice without having seen it, you should probably stop reading now.)

What went right:

// TODO: fill this in

What went wrong:

OK, maybe this isn't the best method.

We'll start with a quick timeline.

The first 40 minutes run smoothly. We identify C, D, and E as the easy problems and solve them easily. At this point every team is doing these problems, and we are perhaps a little behind on time but still doing quite well.

I start working on A, and identify it as a flow with a neat transformation. Wenyi helps with some of the steps here. We submit and after a couple wrong submissions, discover that the problem requires an all-pairs shortest path preprocessing. Another wrong submission and finally we have an AC at 2:22 into the contest.

We then solve G (Paul and Wenyi) and H (me) at some point in the last hour, and I start coding J with 20 minutes left and don't get to a submission before time runs out.

So by myself individually, here's where I screwed up (which may or may not have been influenced by me playing Magic with friends the night before and getting to bed at 3 AM):

-Three WAs on A were bonehead errors, where the all-pairs shortest path was the only algorithmically incorrect part of our original solution: one was typing "n" instead of "m", one was putting in a special case where there wasn't one, and one was mixing up the shortest path preprocessed array with the actual distance array.

-It basically took me two hours to do H, which was partially due to swapping between coding/debugging on paper and on the computer frequently with Paul as he coded G, but ultimately I was just slow. I also should have used long doubles instead of ints for indices, which would have been a very low risk (time and memory limits were almost certainly not in jeopardy) for a very high reward (getting an AC on the first submission, instead of an initial WA which took another few minutes for me to scan the code, decide long doubles for ints was the only possible improvement, and resubmit for a correct answer).

-I was coding a backtracking solution to J which 99% would not have run in time, so that was a waste of time - but with 20 minutes left there wasn't much I could do. With better accuracy on A and H, I could have been working/helping on another problem.

-I could have noticed problem I was familiar, and told Paul, who had solved a similar problem in the past.

Nasa trusted me to manage what the three of us were working on, and I made a list of his advice. We'll go through that:

-Read all the problems first; everyone should have a decent idea of what to do for each problem: We did this well enough, although we may not have thought enough about every problem - more on that later.

-Prefer at least one person to have no knowledge of a specific solution, so they can look at it with a fresh pair of eyes, hopefully spotting any bugs: We also did this decently, although it didn't really come into play at any point - again more on that later.

-Don't let Paul be Paul: This one actually happened on its own. I have to actually give props to Paul here because he made two submissions and got two ACs (while I went 4 for 9...).

-Never get stuck on a problem for more than half an hour; take a break, work on a different problem, and come back to it at a later time: Well, here's where things went wrong.

You'd have to ask them for more details, but Wenyi and Paul spent approximately four hours on B, combined. We didn't solve it in the end, so these man-hours were spent with zero gain. It was my responsibility to force them off the problem and make them work on easier problems (like G and H, and I and K) but I, like them, was convinced they were a mere few minutes away from a valid solution.

I don't believe it was incorrect to start working on B. We made decent progress on it through the contest, but it just took far too long. At some point we should have realized that we were going to have to go for total number of problems solved, rather than time, in which case it's clearly optimal to ditch hard problems for easier problems and come back to the former later. But with many teams solving H, and no teams solving B, it would have been prudent to at least temporarily switch (which likely would also have given me more time at the end). Solving G and H simultaneously was fine, but we should have been doing that an hour or two before.

I (the problem) was easy according to Paul, in retrospect. (I, the person, like to think I have decent morals.) We had come up with an initial solution of brute-force checking each pair for whether they could be connected by a circle, and adding the size of their respective connected components together, but this quickly failed when we saw the first test case where four circles were joined together. We somehow just thought for a minute, decided it was too hard, and didn't come back to it. Later, with a few minutes' thought on the Skytrain, Paul figured out a relatively easy solution.

K was also manageable, but backtracking definitely was not the intended solution. I and/or Paul might have figured this out if I had more time.

J was "free" according to Andrew Henrey, and there were teams solving it, so we probably could've gotten that as well.

Overall, if we had ditched B for good a couple hours in, we likely would have solved at least an additional two problems. It was also not impossible, as it was solved in the end by a couple teams, so if we had gotten a little lucky we would have gotten it correct and moved on to other problems. (In a rather strange coincidence, something very similar happened to me in my first year of ACM: my team got stuck on problem B, and I didn't make them do easier problems. We're 28th here.)

We probably need a conclusion of some sort, preferably with some lessons learned:

-Silly things like the host of errors courtesy of yours truly are fixed with simple practice.

-Problem B wasn't problematic in itself, as it were; if we were strong enough we would have simply solved it. Ultimately it was a combination of being unlucky and choosing the wrong problem to solve, and not looking at the scoreboard to see the problems that should be solved.

-The last thing, and probably the most important: moving off problems is not something we were accustomed to, so we didn't do it. This isn't really solvable by individual practice, where we solve some set of problems and share solutions at the end. Practice as a team (and on sufficiently difficult problem sets) is mandatory for learning when to make the decision of ditching a problem and working on easier ones. It's difficult to stop working on a problem, especially when your gut tells you you're so very close to solving it, but if you've gone from easy problems to problems that require 30-40 minutes to get a partial solution, you're probably not working on the correct problems. Also, discussing what each person did over the course of five hours, the meta-problem solving if you will, would be prudent. That is, figuring out how long each person spent on each problem would go a long way towards cutting down on that time.

Lastly, the practising as a team is difficult when tryouts aren't until late September/early October, with regionals coming in November. If we want to be serious about being competitive in our region and getting to World Finals, we'd need to have at least one team start practicing together at least starting in the summer - which obviously is a huge commitment but necessary nowadays. It's too late for me, as I've done five years of regionals. I guess I can start practising for Google Code Jam...